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

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

题 11-4：Powell 方法

目标函数为

$$f(x)=\frac32x_1^2+\frac12x_2^2-x_1x_2-2x_1,$$

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

第一轮沿 $e_1$ 精确搜索得到步长 $4$：

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

再沿 $e_2$ 搜索得到步长 $-2$：

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

净位移方向为

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

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

$$x(\lambda)=(2,2)^T+\lambda(4,-2)^T$$

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

$$\boxed{\lambda_3=-\frac{2}{17}}.$$

因此源作答记录

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

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

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

直接代入梯度

$$\nabla f=(3x_1-x_2-2, x_2-x_1)^T$$

可验证该点为驻点；Hessian

$$\begin{bmatrix}3&-1\\-1&1\end{bmatrix}\succ0,$$

故它是唯一全局最优点。

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

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

$$\nabla f(x)= (2x_1+x_2-6,\ x_1+4x_2-2,\ -12)^T,$$

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

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

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

$$d_1+d_2+d_3\le0,\qquad d_3\ge0.$$

手写稿选择

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

逐项核对：

$$d_1+d_2+d_3=-1\le0,\qquad d_3=0\ge0,$$

且

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

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

题 12-3：Zoutendijk 方向子问题

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

$$\nabla f(x)=(2x_1-34,\ 8x_2-32)^T.$$

第一轮从

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

出发，得到

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

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

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

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

$$\boxed{d_{\max}=1}.$$

于是取一步到

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

第二轮重新计算

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

再解方向子问题得到

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

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

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

正规流程是：

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

作业自检

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