最优化方法——罚函数法
最优化方法
罚函数法
最优性条件告诉我们，什么时候有最优解，但实际应用往往受到非线性、非凸性、不可导的限制。
罚函数法的基本思想是将原始优化问题加上一个罚项，将约束问题转化为无约束问题。这个罚项惩罚了不满足约束条件的解，使得最优解在满足约束的同时尽量接近原问题的最优解。罚函数法的优势在于可以处理一些不光滑、非凸、不可导的约束问题，并且在迭代的过程中逐渐逼近约束条件。
内点法
内点法一般只适用于不等式约束的优化问题： \[ \begin{align} \min &f(x),x\in R^n\\ \text{s.t. }g_i(x)&\geq 0,i=1,\cdots,m \end{align} \] 其中，记可行域 \(D=\{x\in R^n:g_i(x)\geq 0,i=1,\cdots,m\}\)
内点法也属于罚方法的范畴，其基本思想是保持每一个迭代点 \(x_k\) 是可行域 \(D\) 的内点, 可行域的边界被筑起一道很高的“围墙”作为障碍，当迭代点靠近边界时，增广目标函数值骤然增大，以示“惩罚”，并阻止迭代点穿越边界。
因此，内点法也称为内罚函数法或障碍函数法，它只是用于可行域的内点集非空的情形，即 \[ D=\{x\in R^n:g_i(x)\geq 0,i=1,\cdots,m\}\neq \emptyset \] 我们需要构造一个增广目标函数 \[ H(x,\tau)=f(x)+\tau\bar{H}(x) \] 其中，\(\bar{H}(x)\) 是障碍函数，它需要满足如下性质：当 \(x\) 在 \(D\) 中趋向于边界时，至少有一个 \(g_i(x)\) 趋向于 0，而 \(\bar{H}(x)\) 要趋向于无穷大。
故一般来说我们会取约束函数的对数或倒数，即 \[ \bar{H}(x)=-\sum^m_{i=1}\ln g_i(x)\newline \bar{H}(x)=\sum^m_{i=1}\frac{1}{g_i(x)} \] 这样就将原问题近似成了障碍问题。
会有人问，为什么要做这样的近似（降级），我直接解原问题不就完事了？
对于内点法这样是不适用的。例如，解 KKT 条件的时候，矩阵不一定满秩。
此近似问题的近似精度会随着 \(\tau\) 减小而不断改进，并可以证明当 \(\tau\) 趋向 0 时近似问题与原问题的解是一样的。
例如含不等式的约束问题 \[ \begin{align} \min &f(x)=-x\newline \text{s.t. } &c(x)=x+1\leq 0 \end{align} \] 取障碍函数 \(\bar{H}(x)=-\frac{1}{x+1}\)，则罚函数为 \[ H(x,\tau)=-x-\frac{\tau}{x+1} \] 则原问题近似为求解无约束问题 \[ \min H(x,\tau) \] 求导 \[ \frac{\partial{H}}{\partial{x}}=-1+\frac{\tau}{(x+1)^2}=0 \] 可得 \[ \bar{x}(\tau)=-1-\sqrt{\tau} \] 那么有 \[ \lim_{\tau\to0}\bar{x}(\tau)=\lim_{\tau\to0}(-1-\sqrt{\tau})=-1=x^* \] 下面给出内点法的详细算法步骤
由上述算法可以看出，内点法的优点是结构简单，适应性强。 但是随着迭代过程的进行，罚参数 \(\tau_k\) 将变得越来越小，趋向于零，使得增广目标函数的病态性越来越严重，这给无约束子问题的求解带来了数值实现上的困难，以致导致迭代的失败。 此外，内点法的初始点 \(x_0\) 要求是一个严格的可行点，一般来说这也是比较麻烦甚至困难的。
外点法（外罚函数法）
对于有约束的极值点问题 \[ \begin{align} \min &f(x),x\in R^n\\ \text{s.t. }g_i(x)&\geq 0,i=1,\cdots,m\\ h_j(x)&= 0,j=1,\cdots,l \end{align} \] 记可行域为 \[ D=\left\{x\middle|\begin{align} g_i(x)&\geq 0,i=1,\cdots,m\\ h_j(x)&= 0,j=1,\cdots,l \end{align}\right\} \] 构造罚函数 \[ \bar{H}(x)=\sum^l_{i=1}h_i^2(x)+\sum^m_{i=1}[\min\{0,g_i(x)\}]^2 \] 和增广目标函数 \[ H(x,\tau)=f(x)+\tau\bar{H}(x) \] 不难发现，当 \(x\in D\) 时，即 \(x\) 为可行点时，\(H(x,\tau)=f(x)\)，此时目标函数没有受到额外惩罚；只有当 \(x\) 为不可行点时，目标函数受到了额外的惩罚，其中 \(\tau\) 越大，惩罚越重。
故当 \(\tau>0\) 充分大时，要使得 \(H(x,\tau)\) 极小，罚函数 \(\bar{H}(x)\) 也需要充分小才行。故通过这样的方式逼近极小值点。
与内点法相反，是求取 \(\lim_{\tau\to\infin}\bar{x}(\tau)\)。
由上述算法可知，外罚函数法结构简单，可以直接调用无约束优化算法的通用程序，因而容易编程实现。 缺点是：
- \(x_k\) 往往不是可行点，这对于某些实际问题是难以接受的
- 罚参数 \(\tau_k\) 的选取比较困难，取的过小，可能起不到“惩罚”的作用，而取得过大则可能造成 \(H(x,\tau)\) 的海森阵的条件数很大，从而带来数值技术上的困难
- 注意到 \(\bar{H}(x)\) 一般是不可微的，因而难以直接使用利用导数的优化算法，从而收敛速度缓慢。
乘子法
由于外罚函数法中的罚参数 \(\tau_k\to\infin\)，因此增广目标函数变得“越来越病态”。
增广目标函数的这种病态性质是外罚函数法的主要缺点，而这种缺陷在乘子法中由于引入拉格朗日函数及加上适当的罚函数而得以有效的克服。
考虑等式优化问题 \[
\begin{align}
\min &f(x),x\in R^n\\
\text{s.t. }h_j(x)&= 0,j=1,\cdots,l
\end{align}
\] 那么对于拉格朗日函数 \[
L(x,\lambda)=f(x)-\lambda^Th(x)
\] 一定有 KT 点 \((x^*,\lambda^*)\) 等价原问题为 \[
\begin{align}
\min &L(x,\lambda^*),x\in R^n\\
\text{s.t. }h_j(x)&= 0,j=1,\cdots,l
\end{align}
\] 此时便可以使用外点法求解问题，其增广目标函数为 \[
H(x,\lambda^*,\tau)=L(x,\lambda^*)+\frac{\tau}{2}\|h(x)\|^2
\] 