【凸优化】外点以及内点法

一文完全搞懂凸优化中的外点法和内点法算法流程。

外点法

考虑优化问题

%20%5C%5C%0A%5Ctext%20%7B%20s.t.%20%7D%20%5Cquad%20%26g%7Bi%7D(%5Cboldsymbol%7Bx%7D)%20%5Cgeq%200%2C%20i%3D1%2C%20%5Ccdots%2C%20m%20%5C%5C%0A%5Cquad%20%26h%7Bj%7D(%5Cboldsymbol%7Bx%7D)%3D0%2C%20j%3D1%2C%20%5Ccdots%2C%20l%0A%5Cend%7Baligned%7D%20%5Ctag%7B1%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Cmin%20%5Cquad%20%26f%28%5Cboldsymbol%7Bx%7D%29%20%5C%5C%0A%5Ctext%20%7B%20s.t.%20%7D%20%5Cquad%20%26g%7Bi%7D%28%5Cboldsymbol%7Bx%7D%29%20%5Cgeq%200%2C%20i%3D1%2C%20%5Ccdots%2C%20m%20%5C%5C%0A%5Cquad%20%26h%7Bj%7D%28%5Cboldsymbol%7Bx%7D%29%3D0%2C%20j%3D1%2C%20%5Ccdots%2C%20l%0A%5Cend%7Baligned%7D%20%5Ctag%7B1%7D%0A&id=x7orC)

对于约束项，我们定义辅助函数为：

%20%3D%20%5Csum%7Bi%3D1%7D%5Em%20%5B%5Cmax%5C%7B0%2C%20-g_i(%5Cboldsymbol%7Bx%7D)%5C%7D%5D%5E%5Calpha%20%2B%20%5Csum%7Bj%3D1%7D%5El%20%7Chj(%5Cboldsymbol%7Bx%7D)%7C%5E%5Cbeta%20%5Ctag%7B2%7D%0A#card=math&code=P%28%5Cboldsymbol%7Bx%7D%29%20%3D%20%5Csum%7Bi%3D1%7D%5Em%20%5B%5Cmax%5C%7B0%2C%20-gi%28%5Cboldsymbol%7Bx%7D%29%5C%7D%5D%5E%5Calpha%20%2B%20%5Csum%7Bj%3D1%7D%5El%20%7Ch_j%28%5Cboldsymbol%7Bx%7D%29%7C%5E%5Cbeta%20%5Ctag%7B2%7D%0A&id=sU6bv)

其中 通常取 2。因此，定义惩罚函数为：

%3Df(%5Cboldsymbol%7Bx%7D)%2B%5Csigma%5Cleft%5B%5Csum%7Bi%3D1%7D%5Em%20%5B%5Cmax%5C%7B0%2C%20-g_i(%5Cboldsymbol%7Bx%7D)%5C%7D%5D%5E%5Calpha%20%2B%20%5Csum%7Bj%3D1%7D%5El%20%7Chj(%5Cboldsymbol%7Bx%7D)%7C%5E%5Cbeta%5Cright%5D%20%5Ctag%7B3%7D%0A#card=math&code=F%28%5Cboldsymbol%7Bx%7D%2C%5Csigma%29%3Df%28%5Cboldsymbol%7Bx%7D%29%2B%5Csigma%5Cleft%5B%5Csum%7Bi%3D1%7D%5Em%20%5B%5Cmax%5C%7B0%2C%20-gi%28%5Cboldsymbol%7Bx%7D%29%5C%7D%5D%5E%5Calpha%20%2B%20%5Csum%7Bj%3D1%7D%5El%20%7Ch_j%28%5Cboldsymbol%7Bx%7D%29%7C%5E%5Cbeta%5Cright%5D%20%5Ctag%7B3%7D%0A&id=oKcvK)

其中 是一个很大的正数，称为惩罚因子。那么问题（1）就能转化为一个无约束问题：

%20%5Ctag%7B4%7D%0A#card=math&code=%5Cmin_%7B%5Cboldsymbol%7Bx%7D%7D%20F%28%5Cboldsymbol%7Bx%7D%2C%5Csigma%29%20%5Ctag%7B4%7D%0A&id=b3CNd)

当 足够大的时候，最小化问题（4）必然会使 满足约束，从而解决问题（1）。

在实际计算过程中，惩罚因子的选择十分重要。如果一开始选的太大了，则惩罚函数就不太好优化，如果选的太小了，惩罚函数的极小点会原理原始问题的最优解，计算不准。因此，一般策略是取一个趋向无穷大的严格递增正数列 ，从某个 开始对每个 求解

%20%2B%20%5Csigmak%20P(%5Cboldsymbol%7Bx%7D)%0A#card=math&code=%5Cmin%7B%5Cboldsymbol%7Bx%7D%7D%20f%28%5Cboldsymbol%7Bx%7D%29%20%2B%20%5Csigma_k%20P%28%5Cboldsymbol%7Bx%7D%29%0A&id=cZzWG)

从而得到一个极小点的序列 ，在特定条件下，这个序列会逐渐收敛到问题（1）的最优解。这样通过求解一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法（SUMT）。

因此，外点法计算步骤如下：

1. 给定初始点 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%280%29%7D&id=pOugT)，初始惩罚因子 ，方大系数 ，允许误差 ，置 。
2. 以 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%28k-1%29%7D&id=yLLyo) 为初始点，求解无约束问题，假设其极小点为 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D&id=rb4Ac) %20%2B%20%5Csigmak%20P(%5Cboldsymbol%7Bx%7D)%0A#card=math&code=%5Cmin%7B%5Cboldsymbol%7Bx%7D%7D%20f%28%5Cboldsymbol%7Bx%7D%29%20%2B%20%5Csigma_k%20P%28%5Cboldsymbol%7Bx%7D%29%0A&id=T7iCc)
3. 若 %7D)%20%3C%20%5Cepsilon#card=math&code=%5Csigmak%20P%28%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D%29%20%3C%20%5Cepsilon&id=dGXi8)，则停止计算，得到点 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D&id=mRqlO)；否则，令 ，置 ，返回步骤 2。

外点法是逐渐从违反约束的地方逐渐往不违反约束的最优解靠近，因此称为外点法。

内点法

内点法是从内点出发，并保持在可行域内部进行搜索。这类方法只适用于只有不等式约束的问题。

考虑优化问题

%20%5C%5C%0A%5Ctext%20%7B%20s.t.%20%7D%20%5Cquad%20%26g%7Bi%7D(%5Cboldsymbol%7Bx%7D)%20%5Cgeq%200%2C%20i%3D1%2C%20%5Ccdots%2C%20m%20%0A%5Cend%7Baligned%7D%20%5Ctag%7B1%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%5Cmin%20%5Cquad%20%26f%28%5Cboldsymbol%7Bx%7D%29%20%5C%5C%0A%5Ctext%20%7B%20s.t.%20%7D%20%5Cquad%20%26g%7Bi%7D%28%5Cboldsymbol%7Bx%7D%29%20%5Cgeq%200%2C%20i%3D1%2C%20%5Ccdots%2C%20m%20%0A%5Cend%7Baligned%7D%20%5Ctag%7B1%7D%0A&id=OfD9H)

保持迭代点含于可行域内部的方法是定义障碍函数

%3Df(%5Cboldsymbol%7Bx%7D)%20%2B%20rB(%5Cboldsymbol%7Bx%7D)%5Ctag%7B2%7D%0A#card=math&code=G%28%5Cboldsymbol%7Bx%7D%2Cr%29%3Df%28%5Cboldsymbol%7Bx%7D%29%20%2B%20rB%28%5Cboldsymbol%7Bx%7D%29%5Ctag%7B2%7D%0A&id=evIoL)

其中 #card=math&code=B%28%5Cboldsymbol%7Bx%7D%29&id=NpmCv) 是连续函数，当点趋近于可行域边界时 %5Crightarrow%20%2B%5Cinfty#card=math&code=B%28%5Cboldsymbol%7Bx%7D%29%5Crightarrow%20%2B%5Cinfty&id=cCP2S)。#card=math&code=B%28%5Cboldsymbol%7Bx%7D%29&id=FH1Uc) 中两种重要的形式包括：

%3D%5Csum%7Bi%3D1%7D%5Em%20%5Cfrac%7B1%7D%7Bg_i(%5Cboldsymbol%7Bx%7D)%7D%0A#card=math&code=B%28%5Cboldsymbol%7Bx%7D%29%3D%5Csum%7Bi%3D1%7D%5Em%20%5Cfrac%7B1%7D%7Bg_i%28%5Cboldsymbol%7Bx%7D%29%7D%0A&id=KExio)

%3D-%5Csum%7Bi%3D1%7D%5Em%20%5Clog%7Bg_i(%5Cboldsymbol%7Bx%7D)%7D%0A#card=math&code=B%28%5Cboldsymbol%7Bx%7D%29%3D-%5Csum%7Bi%3D1%7D%5Em%20%5Clog%7Bg_i%28%5Cboldsymbol%7Bx%7D%29%7D%0A&id=IpYVz)

此外， 是一个很小的正数，称为惩罚因子。由于 #card=math&code=B%28%5Cboldsymbol%7Bx%7D%29&id=VWOfg) 会自动阻拦优化过程，因此直接对 #card=math&code=G%28%5Cboldsymbol%7Bx%7D%2Cr%29&id=Fll15) 进行优化就行了。那么优化问题可以转化为：

%20%5Ctag%7B3%7D%0A#card=math&code=%5Cmin_%7B%5Cboldsymbol%7Bx%7D%7D%20G%28%5Cboldsymbol%7Bx%7D%2Cr%29%20%5Ctag%7B3%7D%0A&id=q3yxa)

根据障碍函数的定义， 的取值越小，问题（3）的最优解越接近问题（1）。但是太小了又不好算。因此，我们依然可以采用序列无约束极小化方法，取一个严格单调减且趋于零的惩罚因子（障碍因子）数列 ，对每个 ，从内部出发，求解问题

%0A#card=math&code=%5Cmin_%7B%5Cboldsymbol%7Bx%7D%7D%20G%28%5Cboldsymbol%7Bx%7D%2Cr_k%29%0A&id=Bnrss)

那么，序列 %7D%5C%7D#card=math&code=%5C%7B%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D%5C%7D&id=SJf4Q) 会逐渐收敛到问题（1）的最优解上。则内点法计算步骤如下：

1. 给定初始点 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%280%29%7D&id=i5sRE) 满足约束条件，初始惩罚因子 ，缩小系数 ，允许误差 ，置 。
2. 以 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%28k-1%29%7D&id=Zjukp) 为初始点，求解无约束问题，假设其极小点为 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D&id=V76ta) %20%2B%20rk%20B(%5Cboldsymbol%7Bx%7D)%0A#card=math&code=%5Cmin%7B%5Cboldsymbol%7Bx%7D%7D%20f%28%5Cboldsymbol%7Bx%7D%29%20%2B%20r_k%20B%28%5Cboldsymbol%7Bx%7D%29%0A&id=bHUFK)
3. 若 %7D)%20%3C%20%5Cepsilon#card=math&code=rk%20B%28%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D%29%20%3C%20%5Cepsilon&id=lowUp)，则停止计算，得到点 %7D#card=math&code=%5Cboldsymbol%7Bx%7D%5E%7B%28k%29%7D&id=LmP8J)；否则，令 ，置 ，返回步骤 2。