18.2.3 二次优化问题的解法

18.2.3.1 沃尔夫方法

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

沃尔夫 (Wolfe) 方法用于求解如下特殊类型的二次问题:

$$\begin{array}{}\text{(18.56)}& 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!,\text{ 约束为 }\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}},\underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}}.\end{array}$$

假定 $\mathbf{C}$ 是正定的. 基本思想是确定与问题 (18.56) 相关的库恩-塔克条件组成的系统

$$\begin{array}{}\text{(18.57a)}& \mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}\end{array}$$$$\begin{array}{}\text{(18.57b)}& 2\mathbf{C}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{v}}+{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}=-\underset{―}{\mathbf{p}},\end{array}$$$$\begin{array}{}\text{(18.57c)}& \underset{―}{x}\ge \underset{―}{0},\underset{―}{v}\ge \underset{―}{0}\end{array}$$$$\begin{array}{}\text{(18.58)}& {\underset{―}{\mathbf{x}}}^{\mathrm{T}}\underset{―}{\mathbf{v}}=0\end{array}$$

的解 $\left({\underset{―}{x}}^{\ast },{\underset{―}{u}}^{\ast },{\underset{―}{v}}^{\ast }\right)$ . 关系式(18.57a,18.57b,18.57c)表示一个线性方程组,共有 $m+n$ 个方程和 $2n+m$ 个变量. 由于 (18.58),必然有 $x_i=0$ 或者 $v_i=0\left(i=1,\cdots ,n\right)$ . 因此 (18.57a,18.57b,18.57c) 和 (18.58) 的每个解至多有 $n+m$ 个非零分量. 从而它必定是(18.57a,18.57b,18.57c)的基本解.

2. 求解过程

首先,我们确定系统 $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ 的一个可行基本解 (顶点) $\underset{―}{\bar{\mathbf{x}}}$ . 属于 $\underset{―}{\bar{\mathbf{x}}}$ 的基变量的指标构成集合 $I_B$ . 为了找出系统(18.57a,18.57b,18.57c)的同时也满足(18.58)的解, 我们把问题表达成:

$$\begin{array}{}\text{(18.59)}& -\mu =min!\left(\mu \in \mathbb{R}\right);\end{array}$$$$\begin{array}{}\text{(18.60a)}& \mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}},\end{array}$$$$\begin{array}{}\text{(18.60b)}& 2C\underset{―}{x}-\underset{―}{v}+A^{\mathrm{T}}\underset{―}{u}-\mu \underset{―}{q}=-\underset{―}{p},\underset{―}{q}=2C\underset{―}{\overline{x}}+\underset{―}{p},\end{array}$$$$\begin{array}{}\text{(18.60c)}& \underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}},\underset{―}{\mathbf{v}}\ge \underset{―}{\mathbf{0}},\mu \ge 0\end{array}$$$$\begin{array}{}\text{(18.61)}& {\underset{―}{\mathbf{x}}}^{\mathrm{T}}\underset{―}{\mathbf{v}}=0.\end{array}$$

如果 $\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{v}},\underset{―}{\mathbf{u}},\mu \right)$ 是这个问题同时满足(19.57a,19.57b,19.57c)和(18.58)的解,那么 $\mu =0$ . 向量 $\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{v}},\underset{―}{\mathbf{u}},\mu \right)=\left(\underset{―}{\bar{\mathbf{x}}},\underset{―}{\mathbf{0}},\underset{―}{\mathbf{0}},1\right)$ 是系统(18.60a,18.60b,18.60c)的已知可行解, 并且它也满足 (18.61). 与此基本解相关的基由系数矩阵

$$\begin{array}{}\text{(18.62)}& \left(\begin{array}{cccc}\mathbf{A}& \mathbf{0}& \mathbf{0}& \underset{―}{\mathbf{0}}\\ 2\mathbf{C}& -\mathbf{I}& {\mathbf{A}}^{\mathrm{T}}& -\underset{―}{\mathbf{q}}\end{array}\right)\end{array}$$

(这里 $\mathbf{I},\mathbf{0},\underset{―}{\mathbf{0}}$ 分别表示相应维数的单位矩阵、零矩阵、零向量) 的某些列构成:

a) $m$ 个列属于 $x_i,i\in I_B$ ,

**b) $n\ast \ast -m$ 个列属于 $v_i,i\notin I_B$ ,

c) 所有 $m$ 个列都属于 $u_i$ ,

d) 先删最后一列, 然后删去 b) 或 c) 中一适当的列.

如果 $\underset{―}{\mathbf{q}}=\underset{―}{\mathbf{0}}$ ,则根据 $\mathrm{d})$ 互换是不可能的. 于是, $\underset{―}{\mathbf{x}}$ 已经是解了. 现在第 1 张单纯形表就可以构建出来了. 目标函数的极小将通过单纯形法求解, 不过这里要加上一个附加的规则,即保证满足关系 ${\underset{―}{\mathbf{x}}}^{\mathrm{T}}\underset{―}{\mathbf{v}}=0$ : 变量 $x_i$ 和 $v_i\left(i=1,\cdots ,n\right)$ 必须不能同时是基变量.

在系数矩阵 $\mathbf{C}$ 正定的情形下,考虑到此附加规则,单纯形法提供问题 (18.59), (18.60a,18.60b,18.60c),(18.61) 的一个满足 $\mu =0$ 的解. 在 $\mathbf{C}$ 为正半定矩阵情形下,由于限制了主元的选择,有可能发生: 尽管 $\mu >0$ ,在无强加的附加规则下,不可能再有交换步骤. 在这种情形下, $\mu$ 再也无法进一步减少了.

$$f\left(\underset{―}{\mathbf{x}}\right)=x_1^2+4x_2^2-10x_1-32x_2=min!,x_1+2x_2+x_3=7,2x_1+x_2+x_4=8.$$$$\mathbf{A}=\left(\begin{array}{llll}1& 2& 1& 0\\ 2& 1& 0& 1\end{array}\right),\underset{―}{\mathbf{b}}=\left(\begin{array}{l}7\\ 8\end{array}\right),\mathbf{C}=\left(\begin{array}{llll}1& 0& 0& 0\\ 0& 4& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),\underset{―}{\mathbf{p}}=\left(\begin{array}{c}-10\\ -32\\ 0\\ 0\end{array}\right).$$

在这种情形下, $\mathbf{C}$ 是半正定的. $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ 的一个可行基本解是 $\underset{―}{\bar{\mathbf{x}}}={(0,0,7,8)}^{\mathrm{T}}$ , $\underset{―}{\mathbf{q}}=2\mathbf{C}\underset{―}{\bar{\mathbf{x}}}+\underset{―}{\mathbf{p}}={(-10,-32,0,0)}^{\mathrm{T}}$ . 基向量的选择是: a) $\left(\begin{array}{c}\mathbf{A}\\ 2\mathbf{C}\end{array}\right)$ 的第 3,4 列; b) $\left(\begin{array}{c}0\\ -I\end{array}\right)$ 的第 1,2 列; c) $\left(\begin{array}{c}0\\ A^{\mathrm{T}}\end{array}\right)$ 的列; d) 列 $\left(\begin{array}{c}\underset{―}{0}\\ -\underset{―}{q}\end{array}\right)$ 代替 $\left(\begin{array}{c}0\\ -I\end{array}\right)$ 的第 1 列. 基矩阵由这些列构成, 并计算基矩阵逆 (参见第 1179 页 18.1). 用基矩阵逆乘矩阵 (18.62) 和向量 $\left(\begin{array}{c}\underset{―}{0}\\ -\underset{―}{p}\end{array}\right)$ ,就得到第 1 个单纯形表 (表 18.9).

表 18.9

	$x_1$	$x_2$	$v_1$	$v3$	U4
$x_3$	1	2	0	0	0	7
$x_4$	2	1	0	0	0	8
$v_2$	64 10	-8	$-\frac{32}{10}$	$\frac{12}{10}$	$\frac{54}{10}$	0
$u_1$	0	0	0	-1	0	0
$u_2$	0	0	0	0	-1	0
$\mu$	2 10	0	1 10	1 10	$\frac{2}{10}$	1
	$-\frac{2}{10}$	0	$\frac{1}{10}$	$-\frac{1}{10}$	$-\frac{2}{10}$	-1

根据互补约束,只有 $x_1$ 可以与 $v_2$ 交换. 如此几步之后,我们就得到解 ${\underset{―}{x}}^{\ast }=(2,5/2$ , $0,3/2{)}^{\mathrm{T}}.2\mathbf{C}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{v}}+{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}-\mu \underset{―}{\mathbf{q}}=-\underset{―}{\mathbf{p}}$ 的后两个方程是: $v_3=u_1,v_4=u_2$ . 因此, 除去变量 $u_1,u_2$ 之后,问题的维数可以降低.

18.2.3.2 希尔德雷思-戴索普 (Hildreth-d'Esopo) 方法

1. 原理

严格凸优化问题

$$\begin{array}{}\text{(18.63)}& 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!,\mathbf{A}\underset{―}{\mathbf{x}}\le \underset{―}{\mathbf{b}}\end{array}$$

的对偶问题 (参见第 1202 页 1.) 是

$$\begin{array}{}\text{(18.64a)}& \psi \left(\underset{―}{\mathbf{u}}\right)={\underset{―}{\mathbf{u}}}^{\mathrm{T}}\mathbf{E}\underset{―}{\mathbf{u}}+{\underset{―}{\mathbf{h}}}^{\mathrm{T}}\underset{―}{\mathbf{u}}=min!,\underset{―}{\mathbf{u}}\ge 0\text{,其中}\end{array}$$$$\begin{array}{}\text{(18.64b)}& \mathbf{E}=\frac{1}{4}\mathbf{A}{\mathbf{C}}^{-1}{\mathbf{A}}^{\mathrm{T}},\underset{―}{\mathbf{h}}=\frac{1}{2}\mathbf{A}{\mathbf{C}}^{-1}\underset{―}{\mathbf{p}}+\underset{―}{\mathbf{b}}.\end{array}$$

矩阵 $\mathbf{E}$ 是正定的,并有正对角元 $e_{ii}\left(i=1,\cdots ,m\right)$ . 变量 $\underset{―}{\mathbf{x}}$ 和 $\underset{―}{\mathbf{u}}$ 满足如下关系:

$$\begin{array}{}\text{(18.65)}& \underset{―}{\mathbf{x}}=-\frac{1}{2}{\mathbf{C}}^{-1}\left({\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}+\underset{―}{\mathbf{p}}\right).\end{array}$$

2. 迭代求解

对偶问题 (18.64a) 仅包含约束条件 $\underset{―}{u}\ge \underset{―}{0}$ ,可以通过如下简单的迭代方法求解:

a) 代入 ${\underset{―}{\mathbf{u}}}^1\ge \underset{―}{\mathbf{0}}$ (例如, ${\mathbf{u}}^1=\underset{―}{\mathbf{0}}$ ), $k=1$ .

b) 根据下列公式计算 $u_i^{k+1},i=1,\cdots ,m$ :

$$\begin{array}{}\text{(18.66a)}& w_i^{k+1}=-\frac{1}{e_{ii}}\left(\sum _{j=1}^{i-1}{e}_{ij}{u}_j^{k+1}+\frac{h_i}{2}+\sum _{j=i+1}^m{e}_{ij}{u}_j^k\right),\end{array}$$$$\begin{array}{}\text{(18.66b)}& u_i^{k+1}=max\left\{0,w_i^{k+1}\right\}.\end{array}$$

c) 重复步骤 b),用 $k+1$ 代替 $k$ ,直至停止规则满足,例如 $\left|\psi \left({\underset{―}{\mathbf{u}}}^{k+1}\right)-\psi \left({\underset{―}{\mathbf{u}}}^k\right)\right|<$ $\epsilon ,\epsilon >0$ .

假定存在 $\underset{―}{x}$ 使得 $\mathbf{A}\underset{―}{x}<\underset{―}{b}$ ,则序列 $\left\{\psi \left({\underset{―}{u}}^k\right)\right\}$ 收敛于极小值 ${\psi }_{min}$ ,而由 (18.65) 给出的序列 $\left\{{\underset{―}{\mathbf{x}}}^k\right\}$ 收敛于原问题的解 ${\underset{―}{\mathbf{x}}}^{\ast }$ . 序列 $\left\{{\underset{―}{\mathbf{u}}}^k\right\}$ 并不总是收敛的.