最优化方法——乘子法和外点罚函数法

2021-05-28

此题摘自文件最优化方法第三章（乘子法） 13/24

【题目】分别用外点法和乘子法求等式约束问题

$\mathrm{min} \quad \frac{1}{2}x^2_1+\frac{1}{6}x^2_2 \\ \mathrm{s.t.} \quad x_1+x_2=1$

【解】（外点罚函数法）① 构造罚函数

$F(x,M_k)=\frac{1}{2}x^2_1+\frac{1}{6}x^2_2+M_k(x_1+x_2-1)^2$

② 求偏导

$\frac{\partial F}{\partial x_1}=x_1+2M_k(x_1+x_2-1)=0 \tag{1}$

$\frac{\partial F}{\partial x_1}=\frac{1}{3}x_2+2M_k(x_1+x_2-1)=0 \tag{2}$

③ 联立两个偏导式，求驻点，并得到 $x_1$ 和 $x_2$ 的表达式

联立 $(1)$ 和 $(2)$ ，得到

$x_2=3x_1 \tag{3}$

将 $(3)$ 代回 $(1)$ ，得到

$\begin{aligned} x_1+2M_k(4x_1-1)&=0 \\ \Rightarrow (1+8M_k)x_1&=2M_k \\ \Rightarrow x_1&=\frac{2M_k}{1+8M_k} \end{aligned}$

根据 $(3)$ ，得到

$x_2=3x_1=\frac{6M_k}{1+8M_k}$

将 $x_1$ 和 $x_2$ 的表达式改写为

$x^*=\begin{bmatrix} \frac{2}{\frac{2}{M_k}+8}&\frac{6}{\frac{2}{M_k}+8} \end{bmatrix}^\mathrm{T} \tag{4}$

④ 令 $M_k \to \infty$ ，得到结果

$x^*=\begin{bmatrix} \frac{1}{4}&\frac{3}{4} \end{bmatrix}^\mathrm{T}$

【总结】

解题步骤如下：

① 构造罚函数；

② 求出对 $x_1$ 和 $x_2$ 的罚函数偏导；

③ 联立两个偏导式，求出驻点，并代回偏导式，得到 $x^k_1$ 和 $x^k_2$ 的表达式；

④ 令 $M_k$ 趋近无穷，得到 $x^*$ 。

【解】（乘子法）

① 写出增广Lagrange函数；

$\varphi(x,v^k)=\frac{1}{2}x^2_1+\frac{1}{6}x^2_2+v^k(x_1+x_2-1)+\frac{c_k}{2}(x_1+x_2-1)^2$

② 用解析法求驻点；

$\frac{\partial \varphi}{\partial x_1} = x_1+v^k+c(x_1+x_2-1)=0 \tag{5}$

$\frac{\partial \varphi}{\partial x_2} = \frac{1}{3}x_1+v^k+c(x_1+x_2-1)=0 \tag{6}$

联立 $(5)$ 和 $(6)$ ，得到

$x_2=3x_1 \tag{7}$

将 $(7)$ 代入 $(5)$ 中，得到

$\begin{aligned} x_1+v^k+c(x_1+3x_1-1) &= 0 \\ \Rightarrow (4c+1)x_1+(v^k-c) &= 0 \\ \Rightarrow x_1 &= \frac{c-v^k}{4c+1} \end{aligned}$

那么， $x_2$ 为

$x_1 = \frac{3(c-v^k)}{4c+1}$

③ 根据乘子迭代公式求下一步的 $v^{k+1}$

根据乘子迭代公式，有

$\begin{aligned} v^{k+1} &= v^k+c(x_1+x_2-1) \\ & = v^k + c(\frac{4c-4v^k}{4c+1}+\frac{4c+1}{4c+1}) \\ & = v^k + c(\frac{1+4v^k}{4c+1}) \end{aligned}$

④ $c$ 取任意值，解出 $v^k$ 的值；

令 $c=1$ ，且 $v^k \to \infty$ ，得到

$\begin{aligned} v^* &= v^* - \frac{1+4v^*}{5} \\ \Rightarrow v^* &= -0.25 \end{aligned}$

⑤ 将 $c$ 和 $v^k$ 代入点 $x^k$ 中，得出结果

$x^k_1 = \frac{1+\frac{1}{4}}{5}=\frac{1}{4},\quad x^k_2 = 3x^k_1 = \frac{3}{4}$

即

$x^*=\begin{bmatrix} \frac{1}{4} & \frac{3}{4} \end{bmatrix}^\mathrm{T}$