18.2.2 特殊非线性优化问题

18.2.2.1 凸优化

1. 凸问题

如果函数 $f$ 和 $g_i$ 是凸函数,那么优化问题

$$\begin{array}{}\text{(18.43)}& f\left(\underset{―}{\mathbf{x}}\right)=max!\text{,其中}\underset{―}{\mathbf{x}}\text{满足}{g}_i\left(\underset{―}{\mathbf{x}}\right)\le 0\left(i=1,\cdots ,m\right)\end{array}$$

称作凸问题. 特别地, $f$ 和 $g_i$ 可以是线性函数. 对于凸问题,下列论断成立:

a) $f$ 在 $M$ 上的局部极小也是全局极小.

b) 如果 $M$ 非空且有界,则 (18.43) 至少有一个解.

c) 如果 $f$ 是严格凸的,则 (18.43) 至多有一个解.

2. 最优性条件

a) 如果 $f$ 有连续偏导数, ${\underset{―}{\mathbf{x}}}^{\ast }\in M$ ,并且满足

$$\begin{array}{}\text{(18.44)}& {(\underset{―}{\mathbf{x}}-{\underset{―}{\mathbf{x}}}^{\ast })}^{\mathrm{T}}\mathrm{\nabla }f\left({\underset{―}{\mathbf{x}}}^{\ast }\right)\ge 0,\mathrm{\forall }\underset{―}{\mathbf{x}}\in M,\end{array}$$

那么 ${\underset{―}{x}}^{\ast }$ 是 (18.43) 的解,

b) 斯莱特(Slater)条件是可行集 $M$ 的正则性条件. 如果存在 $\underset{―}{x}\in M$ 使得对于每个非放射线性函数 $g_i$ 有 $g_i\left(\underset{―}{\mathbf{x}}\right)<0$ ,则斯莱特条件满足.

c) 如果斯莱特条件满足,则 ${\underset{―}{x}}^{\ast }$ 是 (18.43) 的极小点当且仅当存在 ${\underset{―}{u}}^{\ast }\ge \underset{―}{0}$ 使得 $\left({\underset{―}{\mathbf{x}}}^{\ast },{\underset{―}{\mathbf{u}}}^{\ast }\right)$ 是拉格朗日函数的鞍点. 此外,如果函数 $f$ 和 $g_i$ 可微,则 ${\underset{―}{\mathbf{x}}}^{\ast }$ 是 (18.43) 的解当且仅当存在 ${\underset{―}{x}}^{\ast }$ 满足局部库恩-塔克条件.

d) 在凸规划问题中函数 $f$ 和 $g_i$ 可微的情形下,对偶问题 (18.42a,18.42b) 可以很容易表述为

$$\begin{array}{}\text{(18.45a)}& L\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)=max!,\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)\in M^{\ast },\end{array}$$$$\begin{array}{}\text{(18.45b)}& M^{\ast }=\left\{\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)\in {\mathbb{R}}^n\times {\mathbb{R}}_{+}^m:\mathrm{\nabla }\underset{―}{\mathbf{x}}L\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)=\underset{―}{\mathbf{0}}\right\}.\end{array}$$

这里 $L$ 的梯度只相对于 $\underset{―}{x}$ 进行计算.

e) 对于凸规划问题, 还成立如下的强对偶性定理:

如果 $M$ 满足斯莱特条件,并且 ${\underset{―}{\mathbf{x}}}^{\ast }\in M$ 是 (18.43) 的解,那么存在 ${\underset{―}{\mathbf{u}}}^{\ast }\in {\mathbb{R}}_{+}^m$ . 使得 $\left({\underset{―}{\mathbf{x}}}^{\ast },{\underset{―}{\mathbf{u}}}^{\ast }\right)$ 是(18.45a,18.45b)的解. 并且

$$\begin{array}{}\text{(18.46)}& f\left({\underset{―}{\mathbf{x}}}^{\ast }\right)=\underset{\underset{―}{\mathbf{x}}\in M}{min}f\left(\underset{―}{\mathbf{x}}\right)=\underset{\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)\in M^{\ast }}{max}L\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)=L\left({\underset{―}{\mathbf{x}}}^{\ast },{\underset{―}{\mathbf{u}}}^{\ast }\right).\end{array}$$

18.2.2.2 二次优化

1. 问题的提法

二次优化问题的形式如下:

$$\begin{array}{}\text{(18.47a)}& 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!,\underset{―}{\mathbf{x}}\in M\subset {\mathbb{R}}^n,\end{array}$$$$\begin{array}{}\text{(18.47b)}& M=M_1:M=\left\{\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n:\mathbf{A}\underset{―}{\mathbf{x}}\le \underset{―}{\mathbf{b}},\underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}}\right\}.\end{array}$$

这里 $\mathbf{C}$ 是对称(n, n)矩阵, $\underset{―}{\mathbf{p}}\in {\mathbb{R}}^n,\mathbf{A}$ 是(m, n)矩阵,而 $\underset{―}{\mathbf{b}}\in {\mathbb{R}}^m$ . 可行集 $M$ 也可以写成下列形式:

$$\begin{array}{}\text{(18.48a)}& M=M_{\mathrm{II}}:M=\left\{\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n:\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}},\underset{―}{\mathbf{x}}\ge \underset{―}{\mathbf{0}}\right\},\end{array}$$$$\begin{array}{}\text{(18.48b)}& M=M_{\mathrm{III}}:M=\left\{\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n:\mathbf{A}\underset{―}{\mathbf{x}}\le \underset{―}{\mathbf{b}}\right\}.\end{array}$$

2. 拉格朗日函数和库恩-塔克条件

问题 (18.47a,18.47b) 的拉格朗日函数是

$$\begin{array}{}\text{(18.49)}& L\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)={\underset{―}{\mathbf{x}}}^{\mathrm{T}}\mathbf{C}\underset{―}{\mathbf{x}}+{\underset{―}{\mathbf{p}}}^{\mathrm{T}}\underset{―}{\mathbf{x}}+{\underset{―}{\mathbf{u}}}^{\mathrm{T}}\left(\mathbf{A}\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{b}}\right).\end{array}$$

引入记号:

$$\begin{array}{}\text{(18.50)}& \underset{―}{\mathbf{v}}=\frac{\partial L}{\partial \underset{―}{\mathbf{x}}}=\underset{―}{\mathbf{p}}+2\mathbf{C}\underset{―}{\mathbf{x}}+{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}},\underset{―}{\mathbf{y}}=-\frac{\partial L}{\partial \underset{―}{\mathbf{u}}}=-\mathbf{A}\underset{―}{\mathbf{x}}+\underset{―}{\mathbf{b}},\end{array}$$

则库恩-塔克条件如下:

情形 I 情形 II

**a) $\mathbf{A}\underset{―}{\mathbf{x}}\ast \ast +\underset{―}{\mathbf{y}}=\underset{―}{\mathbf{b}}$ , a) $\mathbf{A}\underset{―}{\mathbf{x}}=\underset{―}{\mathbf{b}}$ ,

**b) $2C\underset{―}{\mathbf{x}}\ast \ast -\underset{―}{\mathbf{y}}+{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}=-\underset{―}{\mathbf{p}}$ , b) $2C\underset{―}{\mathbf{x}}-\underset{―}{\mathbf{y}}+{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}=-\underset{―}{\mathbf{p}}$ ,

**c) $\underset{―}{x}\ast \ast \ge \underset{―}{0},\underset{―}{v}\ge \underset{―}{0},\underset{―}{y}\ge \underset{―}{0},\underset{―}{u}\ge \underset{―}{0}$ , c) $\underset{―}{x}\ge \underset{―}{0},\underset{―}{v}\ge \underset{―}{0}$ ,

**d) ${\underset{―}{\mathbf{x}}}^{\mathrm{T}}\underset{―}{\mathbf{v}}\ast \ast +{\underset{―}{\mathbf{y}}}^{\mathrm{T}}\underset{―}{\mathbf{u}}=0$ . d) ${\underset{―}{\mathbf{x}}}^{\mathrm{T}}\underset{―}{\mathbf{v}}=0$ .

情形 III

**a) $\mathbf{A}\underset{―}{\mathbf{x}}\ast \ast +\underset{―}{\mathbf{y}}=\underset{―}{\mathbf{b}}$ ,(18.51a)

**b) $2C\underset{―}{\mathbf{x}}\ast \ast +{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}=-\underset{―}{\mathbf{p}}$ ,(18.51b)

**c) $\underset{―}{\alpha \mathbf{\ast }\mathbf{\ast }}\ge \underset{―}{\mathbf{0}},\underset{―}{\mathbf{y}}\ge \underset{―}{\mathbf{0}}$ ,(18.51c)

**d) ${\underset{―}{\mathbf{y}}}^{\mathrm{T}}\underset{―}{\mathbf{u}}\ast \ast =0$ .(18.51d)

3. 凸性

函数 $f\left(\underset{―}{\mathbf{x}}\right)$ 是 (严格) 凸的,当且仅当矩阵 $\mathbf{C}$ 是半正定 (正定) 的. 有关凸优化问题的每个结果都可用于带半正定矩阵 $C$ 的二次问题; 特别地,斯莱特条件总是成立的,从而点 ${\underset{―}{x}}^{\ast }$ 为最优点的必要且充分条件是,存在点 $\left({\underset{―}{x}}^{\ast },\underset{―}{y},\underset{―}{u},\underset{―}{v}\right)$ 满足相应的局部库恩-塔克条件组.

4. 对偶问题

如果 $C$ 是正定的,那么(18.47a,18.47b)的对偶问题(18.45a,18.45b)可以表达为

$$\begin{array}{}\text{(18.52a)}& L\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)=max!,\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)\in M^{\ast },\end{array}$$

其中

$$\begin{array}{}\text{(18.52b)}& M^{\ast }=\left\{\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)\in {\mathbb{R}}^n\times {\mathbb{R}}_{+}^m:\underset{―}{\mathbf{x}}=-\frac{1}{2}{C}^{-1}\left({\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}+\underset{―}{\mathbf{p}}\right)\right\}.\end{array}$$

如果表达式 $\underset{―}{\mathbf{x}}=-\frac{1}{2}{\mathbf{C}}^{-1}\left({\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}+\underset{―}{\mathbf{p}}\right)$ 代入对偶目标函数 $L\left(\underset{―}{\mathbf{x}},\underset{―}{\mathbf{u}}\right)$ ,于是得到等价的问题:

$$\phi \left(\underset{―}{\mathbf{u}}\right)=-\frac{1}{4}{\underset{―}{\mathbf{u}}}^{\mathrm{T}}\mathbf{A}{\mathbf{C}}^{-1}{\mathbf{A}}^{\mathrm{T}}\underset{―}{\mathbf{u}}-{(\frac{1}{2}\mathbf{A}{\mathbf{C}}^{-1}\underset{―}{\mathbf{p}}+\underset{―}{\mathbf{b}})}^{\mathrm{T}}\underset{―}{\mathbf{u}}-\frac{1}{4}{\underset{―}{\mathbf{p}}}^{\mathrm{T}}{\mathbf{C}}^{-1}\underset{―}{\mathbf{p}}=max!,\underset{―}{\mathbf{u}}\ge \underset{―}{\mathbf{0}}.$$

(18.53)

因此,如果 ${\underset{―}{\mathbf{x}}}^{\ast }\in M$ 是(18.47a,18.47b)的解,那么 (18.53) 有解 ${\underset{―}{\mathbf{u}}}^{\ast }\ge \underset{―}{\mathbf{0}}$ ,并且

$$\begin{array}{}\text{(18.54)}& f\left({\underset{―}{\mathbf{x}}}^{\ast }\right)=\phi \left({\underset{―}{\mathbf{u}}}^{\ast }\right).\end{array}$$

问题 (18.53) 可以用如下等价的形式替代:

$$\begin{array}{}\text{(18.55a)}& \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!,\text{ 约束为 }\underset{―}{\mathbf{u}}\ge \underset{―}{\mathbf{0}},\end{array}$$

这里

$$\begin{array}{}\text{(18.55b)}& \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}$$