最优化理论
最优化研究的是，在现实问题上，使用数学模型建模，并在若干约束的条件下，求问题的最优解。
它的一般形式如下：
optimization-formular
g和h函数为约束函数，求函数f的最值
概念
设计变量
- 常量：对函数预先设定的值
- 决策变量：由优化过程，不断更新的变量
目标函数
-
单目标优化问题
f函数只由一个优化问题组成
-
多目标优化问题
f函数由多个优化问题，根据一定的比重，加权组成。
通常写成：f = w1*f1 + w2*f2 ...
等值线/等值超曲面
如下图，一个立体面，使用一个平面把立体面切开，并投影到x y而得到的曲线，称为等值面
optimization-line
梯度
偏导数
optimization-piandao
方向导数
optimization-direct
假设f(x1, x2)，那么对f对X的方向导数如图所示
先对函数在(x1, x2)进行x1求偏导，然后再在(x1+e, x2)求偏导。e趋向零
最速上升/下降方向
对函数f(x)求方向导数，当在x点，沿方向导数相同或相反方向，为最速方向
多元函数泰勒展开式
optimization-taile
分别对函数f进行一阶求导和二阶求导，可以对函数进行二次展开。其中二阶求导公式为Hessian矩阵
无约束优化问题极值条件
- 函数f的一阶导数为零
- 二阶导数大于零，为极小值
- 二阶导数小于零，为极大值
凸优化
凸集
在集合内的任意两点，如果它们的连线都落在集合内，那么称集合为凸集
optimization-tuji
凸函数
optimization-tuhanshu
optimization-tuhanshutu
如图所示，如果函数上的任意两点连线，都高于两点内的函数值，称为凸函数
最优解
optimization-formular
对于问题，如果f，g，h都为凸函数
那么局部极小点，必为全局最优解
因为在连续空间内，函数必然呈现单峰性，要么单调下降，要么单调上升，要么先下降，后上升
约束问题的极值条件
optimization-tug
optimization-feitug
以上两图分别表示了凸函数的极值和非凸函数的极值情况
Kuhn-Tucker条件(K-T条件)
optimization-formular
单约束KT条件
那么有下图
optimization-kt1
- 任意在g取一个点x，对g取导数，对f取导数
- 如果导数相同，那么为极值点
- 否则取如图方向，进行x+u进行探索。其中u为沿可用方向的值
双约束KT条件
optimization-kttwo
如图，可以看出如果f的负导数如果与约束条件的导数线性相关，则得到极值点
否则可以进行迭代优化
线性相关
optimization-lagelangri
f导数与约束条件导数线性相关为，上式得到的系数都为正数
图形意义如下
optimization-lineconnective
分析
可以看出，KT条件可以在每一步，通过选取一个下降的方向，得到一个更优值，所以对于凸函数，得到的极值点，一定为全局最优点。
但是如果对于非凸函数，那么得到的极值点，有可能不是全局最优解
优化的基本思想
优化步骤
- 搜索
- 迭代
- 逼近
optimization-diedai
通过选取方向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.
那么情况有可能是
-
x_left<m_mid_left<m_mid_right<x_right
那么极值点必然在区间外的左边
-
x_left>m_mid_left>m_mid_right>x_right
那么极值点必然位于区间外的右边
-
x_left> m_mid_left > m_mid_right < x_right
那么极值点必然位于x_mid_left和x_right之间
此时可以消除不可能的区间，从而得到一个更小的搜索范围，进行迭代搜索
黄金分割法
optimization-0.618
其中为了得到中间的两个点，如果采取每次选取的区间的比例都相等
optimization-0.618_formular
可以得到系数刚好为0.618
特性
- 计算简单
- 不需要求导数
- 收敛速度慢
- 没有使用函数的特性
无约束优化方法
共轭方向法
optimization-gonge
optimization-gonger
梯度法
通过计算函数f的导数，取反，得到方向S，然后x沿S方向前进u长，得到一个更优解
使用
一般来说在远离极值点时，收敛比较快，由于梯度比较大。
但是在临近极值点的时候，梯度会趋向与零，导致收敛速度迅速减慢。
此时需要结合具有二次收敛的共轭方向法，迅速逼近极值点
牛顿法
optimization-niutun
根据泰勒展开式，任意函数都能展开为二阶的二次函数
而二次函数为凸函数，可以通过对二次泰勒展开式对x求导，并导数为零，得到二次函数的极值点x_k，然后再在x_k，对f函数进行泰勒展开，并继续求导，不断逼近极值点
optimization-niutun-formular
特性分析
optimization-niutun_tu
- 通过求导，得到方向S
- 如果总是取步长为1，那么有可能搜索效率偏低
- 但是步长过大，又有可能使得得到的下一个值更差
- 如果函数不能二次求导，则牛顿法无法进行
- 计算二次导数，使得计算困难
优化
- 通过在S方向，通过一维搜索，得到一个极小值点，
使用
由于计算复杂，一般在工程上不直接使用牛顿法来计算极值
而是通过它的变种，简化计算复杂度，来应用于工程，例如下面的变尺度法
变尺度法
optimization-bgfs
通过牛顿法，公式有上图
如果设置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矩阵
- 使得算法从梯度法不断的向牛顿法逼近
- 从而得到极值点
约束优化方法
复合形法
optimization-fuhexing
步骤
- 对于函数，有若干个约束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只能落在可行域的条件
