Lagrangian approach
对于带等式约束的最优化问题。
标准形式
见下述原始问题。
泛函形式
The problem of finding the local maxima and minima subject to constraints can be generalized to finding local maxima and minima on a differentiable manifold
见https://www.jianshu.com/p/cf8965c7b46b中对泛函优化问题的讨论。
KKT approach
KKT是Lagrangian 的泛化。
KKT condition给了大部分nonlinear programing 问题的统一解析解法。
这里直接给出定理，具体证明与公式可以参见refer
原始问题：
[1]
且：与
在
上连续可微 [2]
将带约束的问题转化为无约束问题（原问题）：
引入拉格朗日(KKT)乘子： [12]
定理:如果)
为)
的saddle point，则
为原优化问题的一个optimal
当满足一定条件时（见下方KKT使用条件，SC，LICQ等）
求解方程组，偏导数为0:
（对于，有n维的偏导）
KKT互补松弛条件[6]：
,
以及原约束：
,
KKT使用条件：
1、strong duality（ Slater's condition ； Linearity constraint qualification）[10][16]=> 满足kkt条件的解为最优解[15]
2、拓展CQ [13] => 满足kkt条件的解为最优解
如果不满足，那么Lagrange dual problem只能当作search for lower bound【强对偶才为等价最优解：greatest lower bound（最大下界）】
Sufficient conditions
通常，满足KKT condition只是必要条件，而非充分条件。
通常，充分条件都要二阶导数的信息，例如，对于非线形问题的SC条件[17]
Basis in Vector Space：
1、凸集定义：欧式空间中，对于集合中的任意两点的连线，连线上任意一点都在集合中，我们就说这个集合是凸集。
2、凸函数定义：对于任意属于[0,1]的a和任意属于凸集的两点x, y，有f( ax + (1-a)y ) <= a * f(x) + (1-a) * f(y)，几何上的直观理解就是两点连线上某点的函数值，大于等于两点之间某点的函数值。凸函数的任一局部极小点也是全局极小点
3、半正定矩阵的定义：特征值大于等于0的实对称矩阵。半正定矩阵的充要条件：行列式（n阶顺序主子式）等于0，行列式的i阶顺序主子式>=0，i从1到n-1
4、凸函数的充要条件：如果f(x)在开凸集S上具有二阶连续偏导数，且f(x)的海塞矩阵（多元函数，二阶偏导的矩阵）在S上处处半正定，则f(x)为S上的凸函数。
5、仿射函数：从到
的映射：
称为仿射变换（affine transform），A为
的矩阵，b为
的向量。当m=1时，称之为仿射函数。
Refer：
[1]：对于条件可以等价为
and
[2]: 后续的KKT条件中，需要对目标函数求偏导，所以要求
连续可微（多元函数中，可[全]微一定可偏导）
[3]:这个条件是说，一定是有可行域的，不然一定无解
[4]:对偶问题的由来：https://www.zhihu.com/question/58584814
[5]:KKT condition:https://blog.csdn.net/dpengwang/article/details/88355744
[6]:对于互补松弛条件，即：当最优解本身就在
的区域内时，解得的
，否则最优解应该在
的边界上，两者合起来即是
[7]:infimum= greatest lower bound；supremum= least upper bound
[9]：slater条件成立时，strong duality holds，对偶问题的解就是原问题的解，这个时候我们称duality gap为零，否则的话，对偶问题的解始终是原问题的解的下界，这个时候duality gap不等于零
[10] :这两个条件是strong duality 的充分条件：
Slater's condition ：对于一个凸优化问题( convex)，如果存在一个点x，使得所有约束都成立（strict feasibility），则最优解处KKT条件成立（原问题为凸优化）
Linearity constraint qualification：如果约束等式和不等式都是线性（譬如线性规划，SVM），则最优解处KKT条件成立。
https://en.wikipedia.org/wiki/Strong_duality#:~:text=Strong%20duality%20is%20a%20condition,than%20or%20equal%20to%20zero).
[11]:除开kkt approach，其他一些相关方法综述：https://en.wikipedia.org/wiki/Constrained_optimization#:~:text=In%20mathematical%20optimization%2C%20constrained%20optimization,of%20constraints%20on%20those%20variables.包括LP，NLP，以及Russian doll search这种DP类思路的算法。
[12]:其实等式的条件才叫lagrangian multiplier，不等式constraints的乘子叫kkt conditions，其实就是拉格朗日乘子的一个泛化。
[13]:除了strong duality，KKT 的CQ包含一些constraint qualifications的细则:https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
[14]:Operation Research(Taha) :18 Classical Optimization Theory
[15]:强对偶条件下，kkt最优，且dual problem 为凸优化问题。
[16]:convex function：二阶可微，其Hesse matrix 半正定。
[17]https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions 中的 Sufficient conditions
网友评论