在无约束最优化问题的基础上，我们可以进一步来求解约束最优化问题。约束最优化问题的一般形式为：
$$
\begin{aligned}
&\min f(x) \\
&s.t. \quad g_i(x)\ge0, i=1,...,m
\end{aligned}
$$

先考虑$g_i(x)$均为线性函数的情况，此时问题与线性规划的约束条件相同，仅仅是目标函数变成了非线性的。我们可以用泰勒展开对目标函数进行近似，将它线性化。将$f(x)$在$x_k$处展开，有
$$
f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k)
$$
故原问题近似于
$$
\begin{aligned}
&\min f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k) \\
&s.t.\quad x \in S
\end{aligned}
$$
其中$S$为线性约束构成的可行域。去掉常量后，问题可以写为
$$
\begin{aligned}
&\min f(x)\approx \nabla f(x_k)^Tx \\
&s.t.\quad x \in S
\end{aligned}
$$
设此问题的最优解为$y_k$，则直观上$d_k=y_k-x_k$ 应当为原问题的可行下降方向。沿着此方向做一维搜索则可进行一次迭代。为了防止一维搜索的结果超出可行域，我们限制步长$0\leq\lambda\leq1$。注意到线性规划的可行域为凸集，由于$x_k$和$y_k$均为可行点，它们确定的连线均在可行域中。限制步长$0\leq\lambda\leq1$保证了一维搜索的结果在可行域中。
继续阅读 →