18.2.7 不等式类型约束下问题的梯度法

如果问题

$$\begin{array}{}\text{(18.95)}& f\left(\underset{―}{\mathbf{x}}\right)=min!,\text{约束条件为}{g}_i\left(\underset{―}{\mathbf{x}}\right)\le 0\text{,}\end{array}$$

需要采用如下类型的迭代法求解:

$$\begin{array}{}\text{(18.96)}& {\underset{―}{\mathbf{x}}}^{k+1}={\underset{―}{\mathbf{x}}}^k+{\alpha }_k{\underset{―}{\mathbf{d}}}^k\left(k=1,2,\cdots \right),\end{array}$$

那么由于有界可行集, 必须考虑另两个附加规则:

(1) 方向 ${\underset{―}{d}}^k$ 必须是 ${\underset{―}{x}}^k$ 处的可行下降方向.

(2) 步长 ${\alpha }_k$ 必须使得 ${\underset{―}{\mathbf{x}}}^{k+1}$ 在 $M$ 中.

基于公式 (18.96) 的各种方法的差别仅在于构造方向 ${\underset{―}{\mathbf{d}}}^k$ 的不同. 为了确保序列 $\left\{{\underset{―}{\mathbf{x}}}^k\right\}\subset M$ 的可行性, ${\alpha }_k^{\prime }$ 和 ${\alpha }_k^{\prime \prime }$ 按如下方式确定:

${\alpha }_k^{\prime }$ 从 $f\left({\underset{―}{\mathbf{x}}}^k+\alpha {\underset{―}{\mathbf{d}}}^k\right)=min!,\alpha >0$ 确定.

$$\begin{array}{}\text{(18.97)}& {\alpha }_k^{\prime \prime }=\left\{\alpha \in \mathbb{R}:{\underset{―}{\mathbf{x}}}^k+\alpha {\underset{―}{\mathbf{d}}}^k\in M\right\}.\end{array}$$

然后, 我们得到

$$\begin{array}{}\text{(18.98)}& {\alpha }_k=min\left\{{\alpha }_k^{\prime },{\alpha }_k^{\prime \prime }\right\}.\end{array}$$

如果在某一步 $k$ 没有可行方向 ${\underset{―}{\mathbf{d}}}^k$ ,则 ${\underset{―}{\mathbf{x}}}^k$ 是平稳点.

18.2.7.1 可行方向方法

1. 方向搜索程序

点 ${\underset{―}{x}}^k$ 处的可行下降方向 ${\underset{―}{d}}^k$ 可以通过求解下列优化问题予以确定:

$$\begin{array}{}\text{(18.99)}& \sigma =min!\end{array}$$$$\begin{array}{}\text{(18.100a)}& \mathrm{\nabla }{g}_i{\left({\underset{―}{\mathbf{x}}}^k\right)}^{\mathrm{T}}\underset{―}{\mathbf{d}}\le \sigma ,i\in I_0\left({\underset{―}{\mathbf{x}}}^k\right),\end{array}$$$$\begin{array}{}\text{(18.100b)}& \mathrm{\nabla }f{\left({\underset{―}{\mathbf{x}}}^k\right)}^{\mathrm{T}}\underset{―}{\mathbf{d}}\le \sigma ,\end{array}$$$$\begin{array}{}\text{(18.100c)}& \parallel \underset{―}{\mathbf{d}}\parallel \le 1\end{array}$$

如果 $\sigma <0$ ,则 (18.100a) 确保该方向搜索程序结果 $\underset{―}{d}={\underset{―}{d}}^k$ 的可行性,而 (18.100b) 确保 ${\underset{―}{\mathbf{d}}}^k$ 的下降性质. 根据规格化条件 (18.100c),该方向搜索程序所得可行集是有界的. 如果 $\sigma =0$ ,则 ${\underset{―}{x}}^k$ 是平稳点,因为在 ${\underset{―}{x}}^k$ 没有可行的下降方向.

由(18.100a,18.100b,18.100c)定义的方向搜索程序有可能引起序列 $\left\{{\underset{―}{\mathbf{x}}}^k\right\}$ 的锯齿形行为,而为避免这样的行为发生,只需将标号集 $I_0\left({\underset{―}{\mathbf{x}}}^k\right)$ 代之以

$$\begin{array}{}\text{(18.101)}& I_{{\epsilon }_k}\left({\underset{―}{\mathbf{x}}}^k\right)=\left\{i\in \{1,\cdots ,m\}:-{\epsilon }_k\le g_i\left({\underset{―}{\mathbf{x}}}^k\right)\le 0\right\},{\epsilon }_k\ge 0,\end{array}$$

即代之以在 ${\underset{―}{x}}^k$ 处的所谓 ${\epsilon }_k$ 主动约束. 于是从 ${\underset{―}{x}}^k$ 出发的局部下降方向被排除,并且越来越接近由 ${\epsilon }_k$ 主动约束组成的 $M$ 的边界 (图 18.7).

如果 $\sigma =0$ 是(18.100a,18.100b,18.100c)在这样修正后的解,那么仅当 $I_0\left({\underset{―}{\mathbf{x}}}^k\right)=I_{{\epsilon }_k}\left({\underset{―}{\mathbf{x}}}^k\right)$ 时, ${\underset{―}{\mathbf{x}}}^k$ 是平稳点. 否则, ${\epsilon }_k$ 必须减少,从而方向搜索程序必须重复下去.

2. 线性约束的特殊情形

如果 $g_i\left(\underset{―}{\mathbf{x}}\right)$ 是线性的,即 $g_i\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{a}}}_i^{\mathrm{T}}\underset{―}{\mathbf{x}}-b_i$ ,则可以建立一种比较简单的方向搜索程序:

$$\begin{array}{}\text{(18.102)}& \sigma =\mathrm{\nabla }f{\left({\underset{―}{\mathbf{x}}}^k\right)}^{\mathrm{T}}\underset{―}{\mathbf{d}}=min!,\end{array}$$

其中

$$\begin{array}{}\text{(18.103a)}& \mathrm{\nabla }{\underset{―}{\mathbf{a}}}_i^{\mathrm{T}}\underset{―}{\mathbf{d}}\le 0,i\in I_0\left({\underset{―}{\mathbf{x}}}^k\right)\text{ 或 }i\in I_{{\epsilon }_k}\left({\underset{―}{\mathbf{x}}}^k\right),\end{array}$$$$\begin{array}{}\text{(18.103b)}& \parallel \underset{―}{\mathbf{d}}\parallel \le 1\end{array}$$

选择不同范数 $\parallel \underset{―}{\mathbf{d}}\parallel =max\left\{\left|d_i\right|\right\}\le 1$ 或 $\parallel \underset{―}{\mathbf{d}}\parallel =\sqrt{{\underset{―}{\mathbf{d}}}^{\mathrm{T}}\underset{―}{\mathbf{d}}}\le 1$ 的影响示于图 18.8(a), (b).

在某种意义上,范数 $\parallel \underset{―}{\mathbf{d}}\parallel =\parallel \underset{―}{\mathbf{d}}{\parallel }_2=\sqrt{{\underset{―}{\mathbf{d}}}^{\mathrm{T}}\underset{―}{\mathbf{d}}}$ 是最佳选择,因为方向搜索程序所得到的方向 ${\underset{―}{\mathbf{d}}}^k$ 与 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 形成最小夹角. 在这种情形下,方向搜索程序并不是线性的,从而要求更大的计算量. 如果选择范数 $\parallel \underset{―}{\mathbf{d}}\parallel =\parallel \underset{―}{\mathbf{d}}{\parallel }_{\mathrm{\infty }}=max\left\{\left|d_i\right|\right\}\le 1$ ,则得到一组线性约束 $-1\le d_i\le 1\left(i=1,\cdots ,n\right)$ ,从而方向搜索程序,例如,可以通过单纯形法求解.

为了确保这种可行方向方法对于二次优化问题 $f\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{x}}}^{\mathrm{T}}\mathbf{C}\underset{―}{\mathbf{x}}+{\underset{―}{\mathbf{p}}}^{\mathrm{T}}\underset{―}{\mathbf{x}}=min!$ , $A\underset{―}{x}\le \underset{―}{b}$ ,能够在有穷步内得到解决,可以利用如下的共轭条件来实施方向搜索程序: 如果在某一步成立 ${\alpha }_{k-1}={\alpha }_{k-1}^{\prime }$ ,即 ${\underset{―}{x}}^k$ 是一 “内” 点,则在方向搜索程序中加上

条件

$$\begin{array}{}\text{(18.104)}& {\underset{―}{\mathbf{d}}}^{k-1^{\mathrm{T}}}\mathbf{C}\underset{―}{\mathbf{d}}=0.\end{array}$$

此外,前面各步骤中相应的的条件均保留不变. 如果在往后的某一步有 ${\alpha }_k={\alpha }_k^{\prime \prime }$ ,则条件 (18.104) 就去掉.

$f\left(\underset{―}{\mathbf{x}}\right)=x_1^2+4x_2^2-10x_1-32x_2=min!,g_1\left(\underset{―}{\mathbf{x}}\right)=-x_1\le 0,g_2\left(\underset{―}{\mathbf{x}}\right)=-x_2\le 0,$ $g_3\left(\underset{―}{\mathbf{x}}\right)=x_1+2x_2-7\le 0,g_4\left(\underset{―}{\mathbf{x}}\right)=2x_1+x_2-8\le 0.$

第 1 步: 从 ${\underset{―}{\mathbf{x}}}^1={(3,0)}^{\mathrm{T}}$ 出发, $\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^1\right)={(-4,-32)}^{\mathrm{T}},I_0\left({\underset{―}{\mathbf{x}}}^1\right)=\{2\}$ .

方向搜索程序: $\left\{\begin{array}{l}-4d_1-32d_2=min!\\ -d_2\le 0,\parallel \underset{―}{\mathbf{d}}{\parallel }_{\mathrm{\infty }}\le 1\end{array}\right\}\Rightarrow {\underset{―}{\mathbf{d}}}^1={(1,1)}^{\mathrm{T}}$ .

最小化常数: ${\alpha }_k^{\prime }=-\frac{{\underset{―}{\mathbf{d}}}^{k^{\mathrm{T}}}\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)}{2{\underset{―}{\mathbf{d}}}^{k^{\mathrm{T}}}\mathbf{C}{\underset{―}{\mathbf{d}}}^k}$ ,其中 $\mathbf{C}=\left(\begin{array}{ll}1& 0\\ 0& 4\end{array}\right)$ .

最大可行步长: ${\alpha }_k^{\prime \prime }=min\left\{\frac{-g_i\left({\underset{―}{\mathbf{x}}}^k\right)}{{\underset{―}{\mathbf{a}}}_i^{\mathrm{T}}{\underset{―}{\mathbf{d}}}^k}:i\text{满足}{\underset{―}{\mathbf{a}}}_i^{\mathrm{T}}{\underset{―}{\mathbf{d}}}^k>0\right\},{\alpha }_1^{\prime }=\frac{18}{5},{\alpha }_1^{\prime \prime }=$$\frac{2}{3}\Rightarrow {\alpha }_1=min\left\{\frac{18}{5},\frac{2}{3}\right\}=\frac{2}{3},{\underset{―}{\mathbf{x}}}^2={(\frac{11}{3},\frac{2}{3})}^{\mathrm{T}}.$

第 2 步: $\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^2\right)={(-\frac{8}{3},-\frac{80}{3})}^{\mathrm{T}},I_0\left({\underset{―}{\mathbf{x}}}^2\right)=\{4\}$ .

方向搜索程序: $\left\{\begin{array}{c}-\frac{8}{3}{d}_1-\frac{80}{3}{d}_2=min!\\ 2d_1+d_2\le 0,\parallel \underset{―}{\mathbf{d}}{\parallel }_{\mathrm{\infty }}\le 1\end{array}\right\}\Rightarrow {\underset{―}{\mathbf{d}}}^2={(-\frac{1}{2},1)}^{\mathrm{T}},{\alpha }_2^{\prime }=$

$$\frac{152}{51},{\alpha }_2^{\prime \prime }=\frac{4}{3}\Rightarrow {\alpha }_2=\frac{4}{3},{\underset{―}{x}}^3={(3,2)}^{\mathrm{T}}.$$

第 3 步: $\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^3\right)={(-4,-16)}^{\mathrm{T}},I_0\left({\underset{―}{\mathbf{x}}}^3\right)=\{3,4\}$ .

方向搜索程序: $\left\{\begin{array}{c}-4d_1-16d_2=min!\\ d_1+2d_2\le 0,2d_1+d_2\le 0,\parallel \underset{―}{\mathbf{d}}{\parallel }_{\mathrm{\infty }}\le 1\end{array}\right\}\Rightarrow {\underset{―}{d}}^3=$

${(-1,\frac{1}{2})}^{\mathrm{T}},{\alpha }_3^{\prime }=1,{\alpha }_3^{\prime \prime }=3\Rightarrow {\alpha }_3=1,{\underset{―}{\mathbf{x}}}^4={(2,\frac{5}{2})}^{\mathrm{T}}.$

接下来的方向搜索程序结果是 $\sigma =0$ ,从而极小点是 ${\underset{―}{x}}^{\ast }={\underset{―}{x}}^4$ (图 18.9).

18.2.7.2 梯度投影方法

1. 问题的提法和求解原理

假定给定凸优化问题

$$\begin{array}{}\text{(18.105)}& f\left(\underset{―}{\mathbf{x}}\right)=min!\text{,其中}\underset{―}{\mathbf{x}}\text{满足}{\underset{―}{\mathbf{a}}}_i^{\mathrm{T}}\underset{―}{\mathbf{x}}\le b_i,i=1,\cdots ,m\text{.}\end{array}$$

点 ${\underset{―}{\mathbf{x}}}^k\in M$ 处的可行下降方向 ${\underset{―}{\mathbf{d}}}^k$ 按如下方式确定:

如果 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 是可行方向,则选择 ${\underset{―}{\mathbf{d}}}^k=-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ . 否则, ${\underset{―}{\mathbf{x}}}^k$ 在 $M$ 的边界上,并且 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 指向 $M$ 外. 向量 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 通过一个线性映射投影到 $M$ 边界的一个线性流形上,该流形由 ${\underset{―}{x}}^k$ 处主动约束的子集确定. 图 18.10(a) 表示投影到一棱边,而图 18.10(b) 表示投影到一个面上. 假定非降秩,即如果对于每个 $\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n$ , 诸向量 ${\underset{―}{\mathbf{a}}}_i,i\in I_0\left(\underset{―}{\mathbf{x}}\right)$ 是线性无关的,则

$$\begin{array}{}\text{(18.106)}& {\underset{―}{\mathbf{d}}}^k=-{\mathbf{P}}_k\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)=-\left(I-{\mathbf{A}}_k^{\mathrm{T}}{\left({\mathbf{A}}_k{\mathbf{A}}_k^{\mathrm{T}}\right)}^{-1}{A}_k\right)\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)\end{array}$$

就给出这样的投影. 这里 ${\mathbf{A}}_k$ 由这样一些向量 ${\underset{―}{\mathbf{a}}}_i$ 组成,其相应的约束构成一个子流形,而 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 正好投影到这个子流形.

2. 算法

梯度投影法由如下几个步骤组成: 从 ${\underset{―}{x}}^1\in M$ 开始,按照如下方式从 $k=1$ 出发依次进行计算.

$\text{I}$: 如果 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 是可行方向,则代入 ${\underset{―}{\mathbf{d}}}^k=-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ ,并从第 $\text{III}$ 步继续. 否则,从向量 ${\underset{―}{\mathbf{a}}}_i,i\in I_0\left({\underset{―}{\mathbf{x}}}^k\right)$ 构造矩阵 ${\mathbf{A}}_k$ ,然后从第 $\text{II}$ 步继续.

$\text{II}$: 代入 ${\underset{―}{\mathbf{d}}}^k=-\left(\mathbf{I}-{\mathbf{A}}_k^{\mathrm{T}}{\left({\mathbf{A}}_k{\mathbf{A}}_k^{\mathrm{T}}\right)}^{-1}{\mathbf{A}}_k\right)\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ . 如果 ${\underset{―}{\mathbf{d}}}^k\ne \underset{―}{\mathbf{0}}$ ,则从第 $\mathbf{III}$ 步继续. 如果 ${\underset{―}{\mathbf{d}}}^k=\underset{―}{\mathbf{0}}$ ,并且 $\underset{―}{\mathbf{u}}=-{\left({\mathbf{A}}_k{\mathbf{A}}_k^{\mathrm{T}}\right)}^{-1}{\mathbf{A}}_k\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)\ge \underset{―}{\mathbf{0}}$ ,那么 ${\underset{―}{\mathbf{x}}}^k$ 是极小点. 局部库恩-塔克条件 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)=\sum _{i\in I_0\left({\underset{―}{\mathbf{x}}}^k\right)}{u}_i{\underset{―}{\mathbf{a}}}_i={\mathbf{A}}_k^{\mathrm{T}}\underset{―}{\mathbf{u}}$ 显然满足.

如果 $\underset{―}{\mathbf{u}}\ngeqq \underset{―}{\mathbf{0}}$ ,则选择一个 $i,{\underset{―}{\mathbf{u}}}_i<0$ ,删除 ${\mathbf{A}}^k$ 的第 $i$ 行,并继续第 II 步.

$\text{III}$: 计算 ${\alpha }_k$ 和 ${\underset{―}{\mathbf{x}}}^{k+1}={\underset{―}{\mathbf{x}}}^k+{\alpha }_k{\underset{―}{\mathbf{d}}}^k$ ,并让 $k=k+1$ 回到第 $\text{I}$ 步继续.

3. 关于算法的注释

如果 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 不是可行方向,则这个向量被映到包含 ${\underset{―}{\mathbf{x}}}^k$ 的最小维子流形上. 如果 ${\underset{―}{\mathbf{d}}}^k=\underset{―}{\mathbf{0}}$ ,则 $-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 垂直于这个子流形. 如果 $\underset{―}{\mathbf{u}}\ge \underset{―}{\mathbf{0}}$ 不成立,则该子流形的维数通过删去一个主动约束而增加一维,从而有可能出现 ${\underset{―}{\mathbf{d}}}^k\ne \underset{―}{\mathbf{0}}$ (图 18.10(b))(投影到一个 (侧) 面). 由于 ${\mathbf{A}}_k$ 往往是从 ${\mathbf{A}}_{k-1}$ 通过增加或删掉一行而得到,故 ${\left({\mathbf{A}}_k{\mathbf{A}}_k^{\mathrm{T}}\right)}^{-1}$ 的计算可以利用 ${\left({\mathbf{A}}_{k-1}{\mathbf{A}}_{k-1}^{\mathrm{T}}\right)}^{-1}$ 而得到简化.

$◼$ 本页 2. 中的例子问题的求解.

第 1 步: ${\underset{―}{\mathbf{x}}}^1={(3,0)}^{\mathrm{T}}$ .

$\text{I}$: $\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^1\right)={(-4,-32)}^{\mathrm{T}},-\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^k\right)$ 是可行的, ${\underset{―}{\mathbf{d}}}^1={(4,32)}^{\mathrm{T}}$ .

$\text{III}$: 如同上例,确定步长为 ${\alpha }_1=\frac{1}{2},{\underset{―}{x}}^2={(\frac{16}{5},\frac{8}{5})}^{\mathrm{T}}$ .

第 2 步:

$\text{I}$: $\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^2\right)={(-\frac{18}{5},-\frac{96}{5})}^{\mathrm{T}}$ (不可行), $I_0\left({\underset{―}{\mathbf{x}}}^2\right)=\{4\},{\mathbf{A}}_2=\left(\begin{array}{ll}2& 1\end{array}\right)$ .

$\text{II}$: ${\mathbf{P}}_2=\frac{1}{5}\left(\begin{array}{cc}1& -2\\ -2& 4\end{array}\right),{\underset{―}{\mathbf{d}}}^2=\left(-\frac{8}{25},\frac{16}{25}\right)\ne \underset{―}{\mathbf{0}}$ .

$\text{III}$: ${\alpha }_2=\frac{5}{8},{\underset{―}{\mathbf{x}}}^3={(3,2)}^{\mathrm{T}}$ .

第 3 步:

$$\text{I:}\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^3\right)={(-4,-16)}^{\mathrm{T}}\text{(不可行),}{I}_0\left({\underset{―}{\mathbf{x}}}^3\right)=\{3,4\},{\mathbf{A}}_3=\left(\begin{array}{ll}1& 2\\ 2& 1\end{array}\right)\text{.}$$$$\text{II:}{\mathbf{P}}_3=\left(\begin{array}{ll}0& 0\\ 0& 0\end{array}\right),{\underset{―}{\mathbf{d}}}^3={(0,0)}^{\mathrm{T}},\underset{―}{\mathbf{u}}={(\frac{28}{3},-\frac{8}{3})}^{\mathrm{T}},u_2<0:{\mathbf{A}}_3=\left(\begin{array}{ll}1& 2\end{array}\right)\text{.}$$$$\text{II:}{\mathbf{P}}_3=\frac{1}{5}\left(\begin{array}{cc}4& -2\\ -2& 1\end{array}\right),{\underset{―}{\mathbf{d}}}^3={(-\frac{16}{5},\frac{8}{5})}^{\mathrm{T}}\text{.}$$$$\text{III:}{\alpha }_3=\frac{5}{16},{\underset{―}{\mathbf{x}}}^4={(2,\frac{5}{2})}^{\mathrm{T}}\text{.}$$

第 4 步:

$$\text{I:}\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^4\right)={(-6,-12)}^{\mathrm{T}}\text{(不可行)},I_0\left({\underset{―}{\mathbf{x}}}^4\right)=\{3\},{\mathbf{A}}_4={\mathbf{A}}_3\text{.}$$$$\text{II:}{\mathbf{P}}_4={\mathbf{P}}_3,{\underset{―}{\mathbf{d}}}^4={(0,0)}^{\mathrm{T}},u=6\ge 0\text{.}$$

由此可知, ${\underset{―}{x}}^4$ 是极小点.