优化作业5

1

PI(x,σ)=x12+x22+12σ[(min⁡{2−2x1−x2,0})2+(min⁡{x2−1,0})2]={x12+x22++x12+x22+12σ(2−2x1−x2)2−+x12+x22+12σ(x2−1)2+−x12+x22+12σ[(2−2x1−x2)2+(x2−1)2]−−\begin{aligned} P_I(x,\sigma) &= x_1^2+x_2^2+\frac 1 2 \sigma [(\min\{2-2x_1-x_2,0\})^2+(\min\{x_2-1,0\})^2]\\ &=\begin{cases}x_1^2+x_2^2 &++\\ x_1^2+x_2^2+\frac 1 2\sigma(2-2x_1-x_2)^2 & -+\\ x_1^2+x_2^2+\frac 1 2 \sigma (x_2-1)^2&+-\\ x_1^2+x_2^2+\frac 1 2\sigma[(2-2x_1-x_2)^2+(x_2-1)^2]&-- \end{cases} \end{aligned}

∂PI∂x1={2x1++(2+4σ)x1+2σx2−4σ−+2x1+−(2+4σ)x1+2σx2−4σ−−\frac{\partial P_I}{\partial x_1} = \begin{cases} 2x_1&++\\ (2+4\sigma)x_1 + 2\sigma x_2-4\sigma&-+\\ 2x_1 &+-\\ (2+4\sigma)x_1 + 2\sigma x_2-4\sigma&-- \end{cases}

∂PI∂x2{2x2++(2+σ)x2+2σx1−2σ−+(2+σ)x2−σ+−(2+2σ)x2+2σx1−3σ−−\frac{\partial P_I}{\partial x_2}\begin{cases} 2x_2 &++\\ (2+\sigma)x_2 + 2\sigma x_1-2\sigma&-+\\ (2+\sigma)x_2 -\sigma&+-\\ (2+2\sigma)x_2 + 2\sigma x_1-3\sigma&-- \end{cases}

在 +−+- 和 −+-+ 中计算:

{x1=8σ2+4σ10σ2+9σ+2,x2=2σ2σ+2−+x1=0,x2=σ2+σ+−\begin{cases} x_1 = \frac{8\sigma^2+4\sigma}{10\sigma^2+9\sigma+2},x_2=\frac{2\sigma}{2\sigma+2}&-+\\ x_1 = 0, x_2 = \frac{\sigma}{2+\sigma}&+- \end{cases}

let σ→∞\sigma \to \infty : x=(0,1)x = (0,1)

2

BL(x,μ)=2x1+3x2−μln⁡(1−2x12−x22)B_L (x,\mu) = 2x_1+3x_2 - \mu\ln (1-2x_1^2-x_2^2)

∂BL∂x1=2+μ4x11−2x12−x22=0∂BL∂x2=3+μ2x21−2x12−x22=0\frac{\partial B_L}{\partial x_1} = 2+\mu\frac{4x_1}{1-2x_1^2-x_2^2} = 0\\ \frac{\partial B_L}{\partial x_2} = 3+\mu\frac{2x_2}{1-2x_1^2-x_2^2} =0

x=μ±μ2+1111(1,3)x = \frac{\mu\pm\sqrt{\mu^2+11}}{11}(1,3)

let μ→0\mu\to 0

x=−1111(1,3)x = -\frac{\sqrt{11}}{11}(1,3)

3

一阶必要条件,即KKT条件.

min⁡f(x)s.t.  c(x)−s2=0\min f(x)\\ \mathrm{s.t. }\; c(x) - s^2 = 0

Φˉ(x,s,λ,σ)=f(x)−λ(c(x)−s2)+12σ(c(x)−s2)2x∗,s∗=arg⁡min⁡xmin⁡sΦˉ(x,s,λ,σ)\bar\Phi(x,s,\lambda,\sigma) = f(x) - \lambda (c(x)-s^2) +\frac 1 2\sigma (c(x)-s^2)^2\\ x^*,s^* = \arg\min_x\min_s \bar\Phi(x,s,\lambda,\sigma)

∂Φˉ∂s2=λ−σc(x)+σs2=0∴λ∗=σ(c(x∗)−s∗2)∇xΦˉ∣x∗=∇f(x∗)−λ∗a(x∗)+σa(x∗)c(x∗)−σa(x∗)s2=∇f(x∗)=0\frac{\partial \bar \Phi}{\partial s^2} = \lambda - \sigma c(x) + \sigma s^2 = 0 \\ \therefore \lambda^* = \sigma(c(x^*)-{s^*}^2)\\ \begin{aligned} \nabla_x\bar\Phi|_{x^*} &= \nabla f(x^*) -\lambda^* a(x^*) + \sigma a(x^*)c(x^*) - \sigma a(x^*)s^2\\ &=\nabla f(x^*)\\ &=0 \end{aligned}

所以是原最优化问题的解，故满足必要条件。

4

G=[222]h=0AT=[12−11−11]b=[4−2]G = \begin{bmatrix}2 & &\\& 2 &\\& & 2\end{bmatrix}\quad h=0\quad A^T = \begin{bmatrix}1 & 2 & -1\\1&-1&1\end{bmatrix}\quad b = \begin{bmatrix}4\\-2\end{bmatrix}

  1. 变量消去法：
    B={2,3},N={1}:x2=2−2x1,  x3=−3x1B = \{2,3\},N=\{1\}: \quad x_2 =2-2x_1,\;x_3 = -3x_1

q^(xN)=14x12−8x1+4\hat q (x_N) = 14x_1^2-8x_1+4

x1∗=27x∗=(27,107,−67)Tx_1^* = \frac 2 7\quad x^* = (\frac 2 7, \frac {10}{7},-\frac 6 7)^T
2. Lagrange方法：

[200−1−1020−210021−1−1−2100−11−100][x1x2x2λ1λ2]=[000−42]\begin{bmatrix} 2 &0&0 &-1&-1\\0& 2 &0 &-2&1\\0&0 & 2&1 &-1\\-1 &-2 &1 &0 &0 \\ -1 &1 & -1 &0 &0 \end{bmatrix} \begin{bmatrix} x_1\\x_2\\x_2\\\lambda_1\\\lambda_2 \end{bmatrix}= \begin{bmatrix} 0\\0\\0\\-4\\2 \end{bmatrix}

得到同上x∗=(27,107,−67)Tx^* = (\frac 2 7, \frac {10}{7},-\frac 6 7)^T

5

min⁡12(x−a)T(x−a)=min⁡12xTx−aTx+12aTa  ⟺  min⁡12xTIx−aTx\min\frac 1 2 (x-a)^T(x-a) =\min \frac 1 2 x^Tx - a^Tx + \frac 1 2 a^Ta\\ \iff \min \frac 1 2 x^T I x - a^T x

Lagrange方法:

[I−AT−A0][xλ]=[a−b]\begin{bmatrix}I &-A^T\\-A &0\end{bmatrix}\begin{bmatrix}x\\\lambda\end{bmatrix} = \begin{bmatrix} a \\-b\end{bmatrix}

解方程即得证：

Ix−ATλ=a−Ax=−bAX−AATλ=Aab−AATλ=Aaλ∗=(AAT)−1(b−Aa)x∗=a+AT(AAT)−1(b−Aa)Ix - A^T\lambda= a\\ -Ax = -b\\ AX - AA^T \lambda = Aa\\ b - AA^T\lambda = Aa\\ \lambda^* = (AA^T)^{-1}(b-Aa)\\ x^* = a +A^T(AA^T)^{-1}(b-Aa)

6

f(x)=12xT[2−1−14]x+[−34]xa1T=(3,−2),a2T=(1,0),a3T=(0,1)b1=−6,b2=0,b3=0f(x) = \frac 1 2 x^T \begin{bmatrix}2 &-1\\-1 &4\end{bmatrix}x + \begin{bmatrix}-3\\4\end{bmatrix}x\\ a_1^T = (3,-2),a_2^T = (1,0), a_3^T= (0,1)\\ b_1 = -6,b_2 =0,b_3 =0

  1. Round 1
    let x1=(0,0),A={2,3}x_1 = (0,0),\mathscr{A}= \{2,3\} , solve:

min⁡q^(d)=d12+2d22−d1d2−3d1+4d2s.t.  d1=d2=0\min \hat q (\bold d) = d_1^2+2d_2^2-d_1d_2-3d_1+4d_2\\ \mathrm{s.t.}\;d_1 = d_2 =0

[2−1−14][00]+[−34]=λ2(1)[10]+λ3(1)[01]\begin{bmatrix}2 &-1\\-1 & 4\end{bmatrix}\begin{bmatrix}0\\0\end{bmatrix} + \begin{bmatrix}-3\\4\end{bmatrix}= \lambda_2^{(1)}\begin{bmatrix}1\\0\end{bmatrix}+\lambda_3^{(1)}\begin{bmatrix}0\\1\end{bmatrix}

d1=(0,0),λ2(1)=−3,λ3(1)=4\bold d_1 = (0,0),\lambda_2^{(1)} = -3,\lambda_3^{(1)} = 4 丢弃最小的对应的约束，即约束2. A:=A\{q}={3}\mathscr{A} := \mathscr{A}\backslash \{q\}=\{3\}
solve:

min⁡q^(d)=d12+2d22−d1d2−3d1+4d2s.t.  d2=0\min \hat q (\bold d) = d_1^2+2d_2^2-d_1d_2-3d_1+4d_2\\\mathrm{s.t.}\;d_2 =0

d1=(32,0)T≠0\bold d_1 = (\frac 3 2 ,0)^T\neq 0 Calculate α1\alpha_1:

α1=min⁡{1,min⁡i∉A,aiTd1≤0bi−aiTx1aiTd1}=1\begin{aligned}\alpha_1 &= \min \left\{1,\min_{i\notin\mathscr A ,a_i^T\bold d_1 \leq 0 }\frac{b_i - a_i^Tx_1}{a_i^T \bold d_1}\right\} \\&=1\end{aligned}

x2=x1+α1d1=(32,0),A:={3}x_2 = x_1 +\alpha_1 \bold d_ 1 = (\frac 3 2 ,0), \mathscr A := \{3\}
2. Round 2
x2=(32,0),A={3}x_2 = (\frac 3 2,0 ), \mathscr A = \{3\}
solve:

min⁡q^(d)=d12+2d22−d1d2−3d1+4d2s.t.  d2=0\min \hat q (\bold d) = d_1^2+2d_2^2-d_1d_2-3d_1+4d_2\\ \mathrm{s.t.}\;d_2 =0

d2=(0,0)\bold d_2 = (0,0)

[2−1−14][20]+[−34]=λ3(2)[01]\begin{bmatrix}2 &-1\\-1 & 4\end{bmatrix}\begin{bmatrix}2\\0\end{bmatrix} + \begin{bmatrix}-3\\4\end{bmatrix}=\lambda_3^{(2)}\begin{bmatrix}0\\1\end{bmatrix}

λ3(2)=4≥0∴x∗=x2=(32,0)\lambda_3^{(2)} =4 \geq 0 \therefore x^* = x_2=(\frac 3 2 ,0)

7

序列二次规划方法求解一般约束优化问题的的算法步骤

min⁡f(x),s.t.  ci(x)=0,i∈Eci(x)≥0,i∈I\begin{aligned}\min &f(x),\\\mathrm{s.t.}\;&c_i(x) = 0,i\in E\\&c_i(x)\geq 0,i \in I\end{aligned}

  1. Step 1
    给定初始点x0x_0，计算Lagranian L(x,λ)=f(x)−λTc(x)L(x,\lambda) = f(x) -\lambda^Tc(x) 的初始Hesse阵近似W0W_0，初始梯度近似g0g_0
  2. Step 2
    解二次规划子问题

min⁡  12dTWkd+gkTd+fk,s.t.  ci(xk)+ai(xk)Td=0,i∈Eci(xk)+ai(xk)Td≥0,i∈I\begin{aligned}\min \;&\frac 1 2 d^TW_kd+ g_k^Td +f_k,\\ \mathrm{s.t.}\; &c_i(x_k)+a_i(x_k)^Td = 0, i\in E\\ &c_i(x_k)+a_i(x_k)^Td \geq 0, i\in I\end{aligned}

得到新xk+1x_{k+1}
3. Step 3
用BFGS或者DFP公式修正WkW_k，检查停止准则。goto Step 2

Learn
优化作业5
https://blog.jacklit.com/2024/12/17/优化作业5/
作者
Jack H
发布于
2024年12月17日
许可协议