最优化理论

最优化研究的是，在现实问题上，使用数学模型建模，并在若干约束的条件下，求问题的最优解。

它的一般形式如下：

g和h函数为约束函数，求函数f的最值

• 常量：对函数预先设定的值
• 决策变量：由优化过程，不断更新的变量

• 单目标优化问题

f函数只由一个优化问题组成

• 多目标优化问题

f函数由多个优化问题，根据一定的比重，加权组成。

通常写成：f=w1*f1 + w2*f2 ...

如下图，一个立体面，使用一个平面把立体面切开，并投影到x y而得到的曲线，称为等值面

假设f(x1, x2)，那么对f对X的方向导数如图所示

先对函数在(x1, x2)进行x1求偏导，然后再在(x1+e, x2)求偏导。e趋向零

对函数f(x)求方向导数，当在x点，沿方向导数相同或相反方向，为最速方向

分别对函数f进行一阶求导和二阶求导，可以对函数进行二次展开。其中二阶求导公式为Hessian矩阵

• 函数f的一阶导数为零
• 二阶导数大于零，为极小值
• 二阶导数小于零，为极大值

在集合内的任意两点，如果它们的连线都落在集合内，那么称集合为凸集

如图所示，如果函数上的任意两点连线，都高于两点内的函数值，称为凸函数

对于问题，如果f，g，h都为凸函数

那么局部极小点，必为全局最优解

因为在连续空间内，函数必然呈现单峰性，要么单调下降，要么单调上升，要么先下降，后上升

以上两图分别表示了凸函数的极值和非凸函数的极值情况

那么有下图

- 任意在g取一个点x，对g取导数，对f取导数 - 如果导数相同，那么为极值点 - 否则取如图方向，进行x+u进行探索。其中u为沿可用方向的值

如图，可以看出如果f的负导数如果与约束条件的导数线性相关，则得到极值点

否则可以进行迭代优化

f导数与约束条件导数线性相关为，上式得到的系数都为正数

图形意义如下

可以看出，KT条件可以在每一步，通过选取一个下降的方向，得到一个更优值，所以对于凸函数，得到的极值点，一定为全局最优点。

但是如果对于非凸函数，那么得到的极值点，有可能不是全局最优解

• 搜索
• 迭代
• 逼近

通过选取方向S，进行a步长的探索，求得一个f_k+1，如果选取的方向正确和步长适当，那么函数f，就会再下一个迭代得到一个更优解

• 点距准则：|x_k+1 - x_k}|
• 值差准则：|f_k+1 - f_k|, |f_k+1 - f_k|/|f_k|
• 梯度准则：导数小于u

一般来说，选取其中一个终止条件即可

有时可能需要结果点距和值差准则来判断是否终止

对于凸函数f(x)无约束优化，函数值必然呈现高低高的分布

那么我么可以任意选取两个点x_left, x_right，然后再在中间选取两个点 x_mid_left, m_mid_right.

那么情况有可能是

1. x_left<m_mid_left<m_mid_right<x_right

那么极值点必然在区间外的左边

1. x_left>m_mid_left>m_mid_right>x_right

那么极值点必然位于区间外的右边

1. x_left> m_mid_left > m_mid_right < x_right

那么极值点必然位于x_mid_left和x_right之间

此时可以消除不可能的区间，从而得到一个更小的搜索范围，进行迭代搜索

其中为了得到中间的两个点，如果采取每次选取的区间的比例都相等

可以得到系数刚好为0.618

• 计算简单
• 不需要求导数
• 收敛速度慢
• 没有使用函数的特性

通过计算函数f的导数，取反，得到方向S，然后x沿S方向前进u长，得到一个更优解

一般来说在远离极值点时，收敛比较快，由于梯度比较大。

但是在临近极值点的时候，梯度会趋向与零，导致收敛速度迅速减慢。

此时需要结合具有二次收敛的共轭方向法，迅速逼近极值点

根据泰勒展开式，任意函数都能展开为二阶的二次函数

而二次函数为凸函数，可以通过对二次泰勒展开式对x求导，并导数为零，得到二次函数的极值点x_k，然后再在x_k，对f函数进行泰勒展开，并继续求导，不断逼近极值点

- 通过求导，得到方向S - 如果总是取步长为1，那么有可能搜索效率偏低 - 但是步长过大，又有可能使得得到的下一个值更差 - 如果函数不能二次求导，则牛顿法无法进行 - 计算二次导数，使得计算困难

• 通过在S方向，通过一维搜索，得到一个极小值点，

由于计算复杂，一般在工程上不直接使用牛顿法来计算极值

而是通过它的变种，简化计算复杂度，来应用于工程，例如下面的变尺度法

通过牛顿法，公式有上图

如果设置H_k为单位矩阵，那么公式则为梯度法

如果H_k是Hession举证，则为牛顿法

有没有办法，可以通过迭代，让H_k从单位矩阵逼近Hession矩阵

那么有H_k+1=H_k + C，其中H_1为

根据泰勒展开式，进行二阶展开，并令导数为零，使用x_k, x_k+1，代入展开式，求得C的表示

那么既可以在每次迭代的时候，通过修正，不断逼近Hession矩阵

• 开始的时候，H为单位矩阵，通过梯度法逼近极值
• 随着H的递推公式，H不断逼近Hession矩阵
• 使得算法从梯度法不断的向牛顿法逼近
• 从而得到极值点

• 对于函数，有若干个约束g
• 在可行域内任意选三个点
• 计算三个点的函数值，并比较
• 对三个点画三角形
• 取方向如图，得到新的点x_k
• 循环上述过程，直到逼近极值点

• 对于凸函数，可以得到最优解
• 对于非凸函数，有可能得到的x_k在可行域外，需要重新选择点
• 没有利用函数的特性
• 计算简单，不需要求导
• 收敛慢

通过构造函数，使得约束优化问题转化为无约束优化问题。从而简化优化算法

如果初始点在可行域内

可以对函数f(x)，g(x)<=0构造函数

p(x)=f(x) - r/g(x)

由于初始点x在可行域内，那么必然x满足g

使用无约束优化求解极值，当x越接近边界g(x)时，g(x) -> 0

会导致1/g -> 无穷大

使得p(x)越来越大

所以这会迫使函数的极值与边界有一段距离

通过不断使得r的值变小，可以让极值点不断逼近边界值

当r趋于零时，p(x)的极值点与f(x)的极值点重合

如果初始点在可行域外

可以建立公式

p(x)=f(x) + M{max(g(x), 0)}

其中st: g(x)<0

当x不满足g时，那么g>0

此时M就会对函数进行惩罚

通过无约束优化的方法

会让不在可行域的点，不断的向可行域拉回来

通过迭代M from 1 to no limit

会迫使函数的极值点落在可行域内

通过把内罚函数和外罚函数结合

可以得到内外罚函数

从而打破x只能落在可行域的条件