第 11 周作业：直接方法与可行方向法

#作业

本周原 PDF 是我的手算，前半是 Powell 直接法，后半是线性约束下的可行方向与 KKT 判断。

题目（根据扫描还原）

完成题 11-4、12-2、12-3：从给定初值用 Powell 直接法迭代；在边界点寻找可行下降方向和最大可行步长；建立并求解 Zoutendijk 可行方向子问题。可辨认的函数、约束和初值随解答一起保留。

查看还原题面与解答

题 11-4：Powell 方法

目标函数为

f(x)=32x12+12x22−x1x2−2x1,f(x)=\frac32x_1^2+\frac12x_2^2-x_1x_2-2x_1,

从 x(1,0)=(−2,4)Tx^{(1,0)}=(-2,4)^T 和坐标方向开始。

第一轮沿 e1e_1 精确搜索得到步长 44：

x(1,1)=(2,4)T.x^{(1,1)}=(2,4)^T.

再沿 e2e_2 搜索得到步长 −2-2：

x(1,2)=(2,2)T.x^{(1,2)}=(2,2)^T.

净位移方向为

d(1,3)=x(1,2)−x(1,0)=(4,−2)T.d^{(1,3)}=x^{(1,2)}-x^{(1,0)}=(4,-2)^T.

沿净位移方向作精确搜索。把

x(λ)=(2,2)T+λ(4,−2)Tx(\lambda)=(2,2)^T+\lambda(4,-2)^T

代入目标并令一阶导数为零，得到

λ3=−217.\boxed{\lambda_3=-\frac{2}{17}}.

因此源作答记录

x(2,0)=(26/17,38/17)T.x^{(2,0)}=(26/17,38/17)^T.

第二轮更新方向组并重复，最终得到

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

直接代入梯度

∇f=(3x1−x2−2,x2−x1)T\nabla f=(3x_1-x_2-2, x_2-x_1)^T

可验证该点为驻点；Hessian

[3−1−11]≻0,\begin{bmatrix}3&-1\\-1&1\end{bmatrix}\succ0,

故它是唯一全局最优点。

题 12-2：在边界点找可行下降方向

这一页没有完整抄录原题，只能可靠辨认目标梯度、活动约束的一阶方向条件和最后选择的方向。源作答先写出

∇f(x)=(2x1+x2−6, x1+4x2−2, −12)T,\nabla f(x)= (2x_1+x_2-6,\ x_1+4x_2-2,\ -12)^T,

并在题目给定点 x^\hat x 算得

∇f(x^)=(−3,3,−12)T.\nabla f(\hat x)=(-3,3,-12)^T.

活动约束给出可行方向条件

d1+d2+d3≤0,d3≥0.d_1+d_2+d_3\le0,\qquad d_3\ge0.

手写稿选择

d=(0,−1,0)T.\boxed{d=(0,-1,0)^T}.

逐项核对：

d1+d2+d3=−1≤0,d3=0≥0,d_1+d_2+d_3=-1\le0,\qquad d_3=0\ge0,

且

∇f(x^)Td=(−3,3,−12)(0,−1,0)T=−3<0.\nabla f(\hat x)^Td =(-3,3,-12)(0,-1,0)^T =-3<0.

所以它既满足扫描中可辨认的线性化可行条件，又是严格下降方向。由于源页没有完整题面，我不反推缺失的目标常数或约束表达式。

题 12-3：Zoutendijk 方向子问题

源页没有完整抄录原约束，但两轮梯度、方向与步长均可辨认。目标梯度写为

∇f(x)=(2x1−34, 8x2−32)T.\nabla f(x)=(2x_1-34,\ 8x_2-32)^T.

第一轮从

x(1)=(1,2)Tx^{(1)}=(1,2)^T

出发，得到

∇f(x(1))=(−32,−16)T,d(1)=(1,0)T.\nabla f(x^{(1)})=(-32,-16)^T, \qquad \boxed{d^{(1)}=(1,0)^T}.

手写方向子问题旁还能辨认出系数记录

a^=(−2,1,0)T,b^=(−2,−1,−2)T,\hat a=(-2,1,0)^T,\qquad \hat b=(-2,-1,-2)^T,

但缺少原题上下文，不能据此重新编造完整约束。扫描明确给出的最大可行步长为

dmax⁡=1.\boxed{d_{\max}=1}.

于是取一步到

x(2)=x(1)+1⋅d(1)=(2,2)T.x^{(2)}=x^{(1)}+1\cdot d^{(1)}=(2,2)^T.

第二轮重新计算

∇f(x(2))=(−30,−16)T,\nabla f(x^{(2)})=(-30,-16)^T,

再解方向子问题得到

d(2)=(0,0)T.\boxed{d^{(2)}=(0,0)^T}.

这里完整梯度并不为零；停止的原因是约束下的方向子问题已找不到非零可行下降方向。源作答据此记录

x∗=(2,2)T,f∗=−112.x^*=(2,2)^T,\qquad f^*=-112.

正规流程是：

  1. 识别当前活动约束；
  2. 解 min⁡∇fTd\min\nabla f^Td，并用盒约束归一化；
  3. 方向目标为负则前进；
  4. 先算最大可行步长，再在区间内做一维搜索；
  5. 方向子问题最优值为零时，用其对偶乘子验证 KKT。

作业自检

  • Powell 每轮的新方向是净位移，不是最后一次坐标方向。
  • 可行方向只由活动约束的一阶条件决定。
  • 最大可行步长还要检查当前非活动约束何时碰到边界。
  • 得到 d=0d=0 后应说明它与 KKT 的联系，而不是只写“停止”。

评论