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

【题目】分别用外点法和乘子法求等式约束问题 m i n 1 2 x 1 2 + 1 6 x 2 2 s . t . x 1 + x 2 = 1 \mathrm{min} \quad \frac{1}{2}x^2_1+\frac{1}{6}x^2_2 \\ \mathrm{s.t.} \quad x_1+x_2=1 min21​x12​+61​x22​s.t.x1​+x2​=1 【解】（外点罚函数法）① 构造罚函数 F ( x , M k ) = 1 2 x 1 2 + 1 6 x 2 2 + M k ( x 1 + x 2 − 1 ) 2 F(x,M_k)=\frac{1}{2}x^2_1+\frac{1}{6}x^2_2+M_k(x_1+x_2-1)^2 F(x,Mk​)=21​x12​+61​x22​+Mk​(x1​+x2​−1)2 ② 求偏导 ∂ F ∂ x 1 = x 1 + 2 M k ( x 1 + x 2 − 1 ) = 0 (1) \frac{\partial F}{\partial x_1}=x_1+2M_k(x_1+x_2-1)=0 \tag{1} ∂x1​∂F​=x1​+2Mk​(x1​+x2​−1)=0(1)

∂ F ∂ x 1 = 1 3 x 2 + 2 M k ( x 1 + x 2 − 1 ) = 0 (2) \frac{\partial F}{\partial x_1}=\frac{1}{3}x_2+2M_k(x_1+x_2-1)=0 \tag{2} ∂x1​∂F​=31​x2​+2Mk​(x1​+x2​−1)=0(2)

③ 联立两个偏导式，求驻点，并得到 x 1 x_1 x1​和 x 2 x_2 x2​的表达式

联立 ( 1 ) (1) (1)和 ( 2 ) (2) (2)，得到 x 2 = 3 x 1 (3) x_2=3x_1 \tag{3} x2​=3x1​(3) 将 ( 3 ) (3) (3)代回 ( 1 ) (1) (1)，得到 x 1 + 2 M k ( 4 x 1 − 1 ) = 0 ⇒ ( 1 + 8 M k ) x 1 = 2 M k ⇒ x 1 = 2 M k 1 + 8 M k \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} x1​+2Mk​(4x1​−1)⇒(1+8Mk​)x1​⇒x1​​=0=2Mk​=1+8Mk​2Mk​​​ 根据 ( 3 ) (3) (3)，得到 x 2 = 3 x 1 = 6 M k 1 + 8 M k x_2=3x_1=\frac{6M_k}{1+8M_k} x2​=3x1​=1+8Mk​6Mk​​ 将 x 1 x_1 x1​和 x 2 x_2 x2​的表达式改写为 x ∗ = [ 2 2 M k + 8 6 2 M k + 8 ] T (4) x^*=\begin{bmatrix} \frac{2}{\frac{2}{M_k}+8}&\frac{6}{\frac{2}{M_k}+8} \end{bmatrix}^\mathrm{T} \tag{4} x∗=[Mk​2​+82​​Mk​2​+86​​]T(4) ④ 令 M k → ∞ M_k \to \infty Mk​→∞，得到结果 x ∗ = [ 1 4 3 4 ] T x^*=\begin{bmatrix} \frac{1}{4}&\frac{3}{4} \end{bmatrix}^\mathrm{T} x∗=[41​​43​​]T 【总结】

解题步骤如下：

① 构造罚函数；

② 求出对 x 1 x_1 x1​和 x 2 x_2 x2​的罚函数偏导；

③ 联立两个偏导式，求出驻点，并代回偏导式，得到 x 1 k x^k_1 x1k​和 x 2 k x^k_2 x2k​的表达式；

④ 令 M k M_k Mk​趋近无穷，得到 x ∗ x^* x∗。

【解】（乘子法）

① 写出增广Lagrange函数； φ ( x , v k ) = 1 2 x 1 2 + 1 6 x 2 2 + v k ( x 1 + x 2 − 1 ) + c k 2 ( x 1 + x 2 − 1 ) 2 \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 φ(x,vk)=21​x12​+61​x22​+vk(x1​+x2​−1)+2ck​​(x1​+x2​−1)2 ② 用解析法求驻点；

∂ φ ∂ x 1 = x 1 + v k + c ( x 1 + x 2 − 1 ) = 0 (5) \frac{\partial \varphi}{\partial x_1} = x_1+v^k+c(x_1+x_2-1)=0 \tag{5} ∂x1​∂φ​=x1​+vk+c(x1​+x2​−1)=0(5)

∂ φ ∂ x 2 = 1 3 x 1 + v k + c ( x 1 + x 2 − 1 ) = 0 (6) \frac{\partial \varphi}{\partial x_2} = \frac{1}{3}x_1+v^k+c(x_1+x_2-1)=0 \tag{6} ∂x2​∂φ​=31​x1​+vk+c(x1​+x2​−1)=0(6)

联立 ( 5 ) (5) (5)和 ( 6 ) (6) (6)，得到 x 2 = 3 x 1 (7) x_2=3x_1 \tag{7} x2​=3x1​(7) 将 ( 7 ) (7) (7)代入 ( 5 ) (5) (5)中，得到 x 1 + v k + c ( x 1 + 3 x 1 − 1 ) = 0 ⇒ ( 4 c + 1 ) x 1 + ( v k − c ) = 0 ⇒ x 1 = c − v k 4 c + 1 \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} x1​+vk+c(x1​+3x1​−1)⇒(4c+1)x1​+(vk−c)⇒x1​​=0=0=4c+1c−vk​​ 那么， x 2 x_2 x2​为 x 1 = 3 ( c − v k ) 4 c + 1 x_1 = \frac{3(c-v^k)}{4c+1} x1​=4c+13(c−vk)​ ③ 根据乘子迭代公式求下一步的 v k + 1 v^{k+1} vk+1

根据乘子迭代公式，有 v k + 1 = v k + c ( x 1 + x 2 − 1 ) = v k + c ( 4 c − 4 v k 4 c + 1 + 4 c + 1 4 c + 1 ) = v k + c ( 1 + 4 v k 4 c + 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} vk+1​=vk+c(x1​+x2​−1)=vk+c(4c+14c−4vk​+4c+14c+1​)=vk+c(4c+11+4vk​)​ ④ c c c取任意值，解出 v k v^k vk的值；

令 c = 1 c=1 c=1，且 v k → ∞ v^k \to \infty vk→∞，得到 v ∗ = v ∗ − 1 + 4 v ∗ 5 ⇒ v ∗ = − 0.25 \begin{aligned} v^* &= v^* - \frac{1+4v^*}{5} \\ \Rightarrow v^* &= -0.25 \end{aligned} v∗⇒v∗​=v∗−51+4v∗​=−0.25​ ⑤ 将 c c c和 v k v^k vk代入点 x k x^k xk中，得出结果 x 1 k = 1 + 1 4 5 = 1 4 , x 2 k = 3 x 1 k = 3 4 x^k_1 = \frac{1+\frac{1}{4}}{5}=\frac{1}{4},\quad x^k_2 = 3x^k_1 = \frac{3}{4} x1k​=51+41​​=41​,x2k​=3x1k​=43​ 即 x ∗ = [ 1 4 3 4 ] T x^*=\begin{bmatrix} \frac{1}{4} & \frac{3}{4} \end{bmatrix}^\mathrm{T} x∗=[41​​43​​]T 【总结】

解题步骤如下：

① 写出增广Lagrange函数；

② 用解析法求驻点；

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

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

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