18.2.9 割平面法

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

设考虑有界区域 $M\subset {\mathbb{R}}^n$ 上的问题

$$\begin{array}{}\text{(18.117)}& f\left(\underset{―}{\mathbf{x}}\right)={\underset{―}{\mathbf{c}}}^{\mathrm{T}}\underset{―}{\mathbf{x}}=min!,\underset{―}{\mathbf{c}}\in {\mathbb{R}}^n,\end{array}$$

这里 $M$ 由凸函数 $g_i\left(\underset{―}{\mathbf{x}}\right)\left(i=1,\cdots ,m\right)$ 以约束形式 $g_i\left(\underset{―}{\mathbf{x}}\right)\le 0$ 给出. 相应于非线性但凸的目标函数 $f\left(\underset{―}{x}\right)$ 的规划问题就可以转换成这种形式,为此只要把

$$\begin{array}{}\text{(18.118)}& f\left(\underset{―}{\mathbf{x}}\right)-x_{n+1}\le 0,{\underset{―}{\mathbf{x}}}_{n+1}\in \mathbb{R}\end{array}$$

看作另一个约束,并且在约束 ${\overline{g}}_i\left(\underset{―}{\mathbf{x}}\right)=g_i\left(\underset{―}{\mathbf{x}}\right)\le 0$ 之下求解问题:

$$\begin{array}{}\text{(18.119)}& \overline{f}\left(\overline{\underset{―}{\mathbf{x}}}\right)=x_{n+1}=min!,\mathrm{\forall }\overline{\underset{―}{\mathbf{x}}}=\left(\underset{―}{\mathbf{x}},x_{n+1}\right)\in {\mathbb{R}}^{n+1}.\end{array}$$

这个方法的基本想法是通过极小点 ${\underset{―}{x}}^{\ast }$ 邻域中一凸多面体,迭代线性逼近 $M$ ,从而原规划问题转化成一列线性规划问题.

首先, 确定凸多面体

$$\begin{array}{}\text{(18.120)}& P_1=\left\{\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n:{\underset{―}{\mathbf{a}}}_i^{\mathrm{T}}\underset{―}{\mathbf{x}}\le b_i,i=1,\cdots ,s\right\}.\end{array}$$

由线性规划问题

$$\begin{array}{}\text{(18.121)}& f\left(\underset{―}{\mathbf{x}}\right)=min!,\underset{―}{\mathbf{x}}\in P_1\end{array}$$

相对于 $f\left(\underset{―}{\mathbf{x}}\right)$ 确定 $P_1$ 的最优极端点 ${\underset{―}{\mathbf{x}}}^1$ . 如果 ${\underset{―}{\mathbf{x}}}^1\in M$ ,则就找到原问题的最优解. 否则,确定将点 ${\underset{―}{\mathbf{x}}}^1$ 和 $M$ 分离的一超平面: $H_1=\left\{\underset{―}{\mathbf{x}}:{\underset{―}{\mathbf{a}}}_{s+1}^{\mathrm{T}}\underset{―}{\mathbf{x}}=b_{s+1},{\underset{―}{\mathbf{a}}}_{s+1}^{\mathrm{T}}{\underset{―}{\mathbf{x}}}^1>b_{s+1}\right\}$ , 于是新的多面体包含

$$\begin{array}{}\text{(18.122)}& P_2=\left\{\underset{―}{\mathbf{x}}\in P_1:{\underset{―}{\mathbf{a}}}_{s+1}^{\mathrm{T}}\underset{―}{\mathbf{x}}\le b_{s+1}\right\}.\end{array}$$

图 18.13 为割平面法的示意图.

2. 凯利 (Kelley) 方法

不同方法之间的区别在于分离平面的选取. 采用凯利方法, $H_k$ 的选取方法如下: 选择一标号 $j_k$ 使得

$$\begin{array}{}\text{(18.123)}& g_{j_k}\left({\underset{―}{\mathbf{x}}}^k\right)=max\left\{g_i\left({\underset{―}{\mathbf{x}}}^k\right):i=1,\cdots ,m\right\}.\end{array}$$

函数 $g_{j_k}\left(\underset{―}{\mathbf{x}}\right)$ 在 $\underset{―}{\mathbf{x}}={\underset{―}{\mathbf{x}}}^k$ 的切平面为

$$\begin{array}{}\text{(18.124)}& T\left(\underset{―}{\mathbf{x}}\right)=g_{j_k}\left({\underset{―}{\mathbf{x}}}^k\right)+{(\underset{―}{\mathbf{x}}-{\underset{―}{\mathbf{x}}}^k)}^{\mathrm{T}}\mathrm{\nabla }{g}_{j_k}\left({\underset{―}{\mathbf{x}}}^k\right).\end{array}$$

超平面 $H_k=\left\{\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n:T\left(\underset{―}{\mathbf{x}}\right)=0\right\}$ 把点 ${\underset{―}{\mathbf{x}}}^k$ 与所有满足 $g_{j_k}\left(\underset{―}{\mathbf{x}}\right)\le 0$ 的点 $\underset{―}{\mathbf{x}}$ 分离开. 于是,对于第 $k+1$ 个线性规划问题,增加一个约束条件 $T\left(\underset{―}{\mathbf{x}}\right)\le 0$ . 序列 $\left\{{\underset{―}{\mathbf{x}}}^k\right\}$ 的每个聚点 ${\underset{―}{x}}^{\ast }$ 都是原问题的一个极小点. 实际应用表明,这种方法的收敛速度较低. 此外, 约束的数量总是不断增加.