约束优化算法

古典罚函数法和内点罚函数法

约束优化问题是最优化中另一类重要的研究分支。求解约束问题的一类重要思想为将约束问题转化为无约束优化问题，我们称之为罚函数法。本节知识点有外点罚函数法、针对不等式约束问题的内点罚函数法的算法构造。难点为外点罚函数法、内点罚函数法的倒数罚项函数或对数罚项函数构造。

内点罚函数法，对于只有不等式约束的问题

\[\begin{aligned} \min \quad & f(\boldsymbol{x}) \\ \text{s.t.} \quad & g_i(\boldsymbol{x}) \ge 0 \end{aligned}\]

基本思想是在函数上引入一个关于约束的障碍项，当迭代点由内部接近边界时，障碍项会趋于无穷大。

常用的障碍函数

\[B(x) = \sum_{i=1}^n \frac{1}{g_i(\boldsymbol{x})}\] \[B(x) = - \sum_{i=1}^n \ln g_i(\boldsymbol{x})\]

定义罚函数 \(F(\boldsymbol{x},\mu) = f(\boldsymbol{x}) + \mu B(\boldsymbol{x})\)

外点罚函数法

广义乘子法

由于外点罚函数法需要罚因子趋向于无穷， 再这样的情形下，可能导致海塞阵奇异等。因而需要克服罚因子趋向罚因子的问题。 本节我们将讲述广义乘子法。 本节知识点有等式约束问题、不等式约束问题及混合约束问题的广义乘子法推导和算法。难点在于各类问题的罚函数构造及拉格朗日乘子的迭代公式。