2019—2020 学年期末真题（2018 级）

Views: --
#真题

试卷封面写“2020 年 6 月 20 日”，正文注意事项写“2020 年 6 月 16 日 9:00—12:00”，两处日期不一致。这里据正文课程名与学年，将其记为 2019—2020 学年期末卷。

一、线性规划对偶（20 分）

min⁡8x1+6x2+3x3+6x4s.t.x1+2x2+x4≥3,3x1+x2+x3+x4≥6,x3+x4≥2,x1+x3≥2,x1,x2,x3,x4≥0.\begin{aligned} \min\quad &8x_1+6x_2+3x_3+6x_4\\ \text{s.t.}\quad &x_1+2x_2+x_4\ge3,\\ &3x_1+x_2+x_3+x_4\ge6,\\ &x_3+x_4\ge2,\\ &x_1+x_3\ge2,\\ &x_1,x_2,x_3,x_4\ge0. \end{aligned}
  1. 写出对偶问题。
  2. 已知原问题最优解 x∗=(1,1,2,0)Tx^*=(1,1,2,0)^T，用互补松弛求对偶最优解。
查看解析

对偶为

max⁡3y1+6y2+2y3+2y4s.t.y1+3y2+y4≤8,2y1+y2≤6,y2+y3+y4≤3,y1+y2+y3≤6,y1,y2,y3,y4≥0.\begin{aligned} \max\quad &3y_1+6y_2+2y_3+2y_4\\ \text{s.t.}\quad &y_1+3y_2+y_4\le8,\\ &2y_1+y_2\le6,\\ &y_2+y_3+y_4\le3,\\ &y_1+y_2+y_3\le6,\\ &y_1,y_2,y_3,y_4\ge0. \end{aligned}

第四条原约束在 x∗x^* 处有严格松弛，故 y4=0y_4=0。x1,x2,x3>0x_1,x_2,x_3>0，前三个相应对偶约束取等号：

y1+3y2=8,2y1+y2=6,y2+y3=3.y_1+3y_2=8,\qquad 2y_1+y_2=6,\qquad y_2+y_3=3.

解得

y∗=(2,2,1,0)T.\boxed{y^*=(2,2,1,0)^T}.

原、对偶目标值均为 2020。

二、参数二次规划（20 分）

min⁡12x12+12x22−x1−2x2s.t.x1+x2−κ≥0,x1,x2≥0,\begin{aligned} \min\quad &\frac12x_1^2+\frac12x_2^2-x_1-2x_2\\ \text{s.t.}\quad &x_1+x_2-\kappa\ge0,\\ &x_1,x_2\ge0, \end{aligned}

其中 κ∈R\kappa\in\mathbb R。

  1. 证明 κ=4\kappa=4 时 (1.5,2.5)T(1.5,2.5)^T 最优。
  2. 求最优解位于可行域内点时的 κ\kappa 范围、解和最优值。
  3. 求最优解位于边界时的 κ\kappa 范围、解和最优值。
  4. 取 D={x∣x1,x2≥0}D=\{x\mid x_1,x_2\ge0\}，写出对偶问题。
查看解析

无主约束时，目标的唯一极小点为 (1,2)T(1,2)^T，目标值 −5/2-5/2。因此：

  • κ<3\kappa<3 时它是可行域内点；
  • κ=3\kappa=3 时它恰在主约束边界；
  • κ>3\kappa>3 时主约束必须活动。

边界情形令乘子 λ≥0\lambda\ge0，

L=f−λ(x1+x2−κ).L=f-\lambda(x_1+x_2-\kappa).

驻点给出 x1=1+λ,x2=2+λx_1=1+\lambda,x_2=2+\lambda，再用 x1+x2=κx_1+x_2=\kappa：

λ=κ−32,x∗=(κ−12,κ+12)T.\lambda=\frac{\kappa-3}{2},\qquad x^*=\left(\frac{\kappa-1}{2},\frac{\kappa+1}{2}\right)^T.

最优值为

f∗=κ2−6κ−14.f^*=\frac{\kappa^2-6\kappa-1}{4}.

κ=4\kappa=4 时即得 (3/2,5/2)T(3/2,5/2)^T，且问题为严格凸规划，KKT 点就是唯一全局最优解。

在集约束 DD 上的对偶函数为

q(λ)=λκ−(1+λ)22−(2+λ)22,λ≥0,q(\lambda)=\lambda\kappa-\frac{(1+\lambda)^2}{2} -\frac{(2+\lambda)^2}{2},\qquad\lambda\ge0,

对偶问题是 max⁡λ≥0q(λ)\max_{\lambda\ge0}q(\lambda)。

三、单纯形法与右端变化（20 分）

min⁡x1+x2−3x3s.t.x1−2x2+x3≤11,2x1+x2−4x3≥3,x1−2x3=1,x1,x2,x3≥0.\begin{aligned} \min\quad &x_1+x_2-3x_3\\ \text{s.t.}\quad &x_1-2x_2+x_3\le11,\\ &2x_1+x_2-4x_3\ge3,\\ &x_1-2x_3=1,\\ &x_1,x_2,x_3\ge0. \end{aligned}
  1. 用单纯形法求最优解。
  2. 若右端向量从 (11,3,1)T(11,3,1)^T 变为 (−2,3,1)T(-2,3,1)^T，求新最优解。
查看解析

原问题用大 MM 法建立初始基，依次换入能改善目标的变量。最终基变量为 x3,x2,x1x_3,x_2,x_1，读得

x∗=(9,1,4)T,f∗=−2.\boxed{x^*=(9,1,4)^T},\qquad \boxed{f^*=-2}.

代回三条约束分别得到 11,3,111,3,1，全部可行。

右端变化后，原最优表的检验数不变，但基本变量值中出现负数，适合从原表继续用对偶单纯形法。一次换基后得到

x′=(1,3/2,0)T,f′=5/2.\boxed{x'=(1,3/2,0)^T},\qquad \boxed{f'=5/2}.

代回新约束：第一条为 1−3=−21-3=-2，第二条为 2+3/2≥32+3/2\ge3，等式为 11，所以新解可行。

四、参数与局部最优（20 分）

min⁡(x1−1)2+x22s.t.x1−x22β=0,\begin{aligned} \min\quad &(x_1-1)^2+x_2^2\\ \text{s.t.}\quad &x_1-\frac{x_2^2}{\beta}=0, \end{aligned}

其中 β>0\beta>0。讨论 (0,0)T(0,0)^T 是否为局部最优解。

查看解析

沿约束消去 x1=x22/βx_1=x_2^2/\beta。令 t=x22≥0t=x_2^2\ge0，目标成为

ϕ(t)=(tβ−1)2+t=1+(1−2β)t+t2β2.\phi(t)=\left(\frac t\beta-1\right)^2+t =1+\left(1-\frac2\beta\right)t+\frac{t^2}{\beta^2}.

t=0t=0 是单侧局部极小点，当且仅当一次项系数非负：

1−2β≥0.1-\frac2\beta\ge0.

所以

β≥2 时 (0,0)T 是局部最优解；\boxed{\beta\ge2\text{ 时 }(0,0)^T\text{ 是局部最优解；}} 0<β<2 时不是。\boxed{0<\beta<2\text{ 时不是。}}

β=2\beta=2 时一次项消失，但二次项为正，仍为严格局部最小。

五、既约梯度（20 分）

考虑

min⁡f(x),Ax=b.\min f(x),\qquad Ax=b.

令 A=(B,N)A=(B,N)，BB 可逆，x=(xB,xN)Tx=(x_B,x_N)^T，并定义

rN=∇Nf−(B−1N)T∇Bf,r_N=\nabla_Nf-(B^{-1}N)^T\nabla_Bf, dN=−rN,dB=−B−1NdN.d_N=-r_N,\qquad d_B=-B^{-1}Nd_N.

证明：若 d≠0d\ne0，则 dd 是下降可行方向；且 d=0d=0 当且仅当 xx 是等式约束问题的 KKT 点。

查看证明

可行性来自

Ad=BdB+NdN=−BB−1NdN+NdN=0.Ad=Bd_B+Nd_N =-BB^{-1}Nd_N+Nd_N=0.

所以 x+αdx+\alpha d 对任意充分小 α\alpha 仍满足等式约束。

再计算方向导数：

∇fTd=∇BfTdB+∇NfTdN=[∇Nf−(B−1N)T∇Bf]TdN=rNT(−rN)=−∥rN∥2.\begin{aligned} \nabla f^Td &=\nabla_Bf^Td_B+\nabla_Nf^Td_N\\ &=\left[\nabla_Nf-(B^{-1}N)^T\nabla_Bf\right]^Td_N\\ &=r_N^T(-r_N)=-\lVert r_N\rVert^2. \end{aligned}

若 d≠0d\ne0，则 rN≠0r_N\ne0，方向导数严格为负，故 dd 是下降可行方向。

若 d=0d=0，则 rN=0r_N=0。令

λ=−B−T∇Bf,\lambda=-B^{-T}\nabla_Bf,

便有 ∇Bf+BTλ=0\nabla_Bf+B^T\lambda=0；rN=0r_N=0 又给出 ∇Nf+NTλ=0\nabla_Nf+N^T\lambda=0，合起来即

∇f+ATλ=0,Ax=b,\nabla f+A^T\lambda=0,\qquad Ax=b,

所以 xx 是 KKT 点。

反过来，若存在 λ\lambda 满足上述 KKT 条件，则从基变量部分得 λ=−B−T∇Bf\lambda=-B^{-T}\nabla_Bf，代入非基变量部分正好得到 rN=0r_N=0，进而 d=0d=0。

评论