内点法

文字理解

数学定义

算法步骤

1. 取初始惩罚因子\(r^{(0)}>0\)，允许误差\(\epsilon>0\)；
2. 在可行域\(D\)内选取初始点\(X^{(0)}\)，令\(k=1\)；
3. 构造惩罚函数\(\varphi (X, r^{(k)})\)，从\(X^{(k-1)}\)点出发用无约束优化方法求惩罚函数\(\varphi (X, r^{(k)})\)的极值点\((X^{*}, r^{(k)})\)；
4. 检查迭代终止准则：如果满足\[\|X^{*} r^{(k)}-X^{*} r^{(k-1)}\|\leq\epsilon_{1}=10^{-5}-10^{-7}\]或者\[\|\frac{\varphi (X^{*} ,r^{(k)})-\varphi (X^{*}, r^{(k-1)})}{\varphi (X^{*}, r^{(k-1)})}\|\leq\epsilon_{2}=10^{-3}-10^{-4}\]则停止迭代计算，并以\((X^{*}, r^{(k)})\)作为原目标函数\(f(X)\)的约束最优解，否则转入下一步；
5. 取\(r^{(k+1)}=cr^{(k)}\)，\(X^{(0)}=X^{*}r^{(k)}\)，\(k=k+1\)，转向步骤3。递减系数\(c=0.1-0.5\)，通常取0.1。

内点惩罚函数法特点及其应用

• 惩罚函数定义于可行域内，序列迭代点在可行域内不断趋于约束边界上的最优点（这就是称为内点法的原因）
• 只适合求解具有不等式约束的优化问题

内点法求解案例

用内点法求下面约束优化问题的最优解，取迭代初始\(X^0 = [0, 0]^{\mathrm{T}}\)，惩罚因子的初始值\(r^0 = 1\)，收敛终止条件\(\|X^k – X^{k-1}\| \leq \varepsilon\)，\(\varepsilon = 0.01\)

\[\min f(X) = x_1^2 + x_1^2 – x_1x_2 – 10x_1 – 4x_2 + 60\]

\[\mathrm{s.t.}\; g(X) = x_1 + x_2 -8 \leq 0\]

1. 构造内惩罚函数：\(\varphi(X, r) = x_1^2 + x_1^2 – x_1x_2 – 10x_1 – 4x_2 + 60 -r\ln(x_1 + x_2 -8)\)
2. 用解析法求内惩罚函数的极小值

\[\nabla\varphi(X, r) = [2x_1 – x_2 – 10 – \frac{r}{x_1 + x_2 – 8} \quad 2x_2 – x_1 – 4 – \frac{r}{x_1 + x_2 – 8}]\]

令\(\nabla \varphi(X, r) = 0\)得：\(\begin{align}2x_1 – x_2 – 10 – \frac{r}{x_1 + x_2 – 8} = 0 \\ 2x_2 – x_1 – 4 – \frac{r}{x_1 + x_2 – 8} = 0\end{align}\)

解得：

\(X^*_1(r) = \begin{bmatrix}\frac{13 + \sqrt{9+2r}}{2} & \frac{9 + \sqrt{9+2r}}{2}\end{bmatrix}^{\mathrm{T}}\)

\(X^*_2(r) = \begin{bmatrix}\frac{13 – \sqrt{9+2r}}{2} & \frac{9 – \sqrt{9+2r}}{2}\end{bmatrix}^{\mathrm{T}}\)

\(\because g(X^*_1(r)) > 0\)

\(\therefore\) 舍去\(X^*_1(r)\)

\(\because \varphi(X, r)\)为凸函数

\(\therefore\) 无约束优化问题的最优解为\(X^*(r) = X^*_2(r) = \begin{bmatrix}\frac{13 – \sqrt{9+2r}}{2} & \frac{9 – \sqrt{9+2r}}{2}\end{bmatrix}^{\mathrm{T}}\)

1. 求最优解

当\(r^0 = 1\)时，\(X^*(r^0) = \begin{pmatrix}4.8417 & 2.8417\end{pmatrix}^{\mathrm{T}}\)，\(\|X^*(r^0) – X^0\| = 5.6140 > \varepsilon\)

当\(r^1 = 0.1\)时，\(X^*(r^1) = \begin{pmatrix}4.9834 & 2.9834\end{pmatrix}^{\mathrm{T}}\)，\(\|X^*(r^1) – X^*(r^0)\| = 0.2004 > \varepsilon\)

当\(r^2 = 0.01\)时，\(X^*(r^2) = \begin{pmatrix}4.9983 & 2.9983\end{pmatrix}^{\mathrm{T}}\)，\(\|X^*(r^2) – X^*(r^1)\| = 0.0211 > \varepsilon\)

当\(r^3 = 0.01\)时，\(X^*(r^3) = \begin{pmatrix}4.9998 & 2.9998\end{pmatrix}^{\mathrm{T}}\)，\(\|X^*(r^3) – X^*(r^2)\| = 0.0021 < \varepsilon\)

即\(X^*(r^3)\)为最优解