4.2 凸优化 – 李云浩的博客

本文最后更新于120 天前，其中的信息可能已经过时，如有错误请发送邮件至 2641805259@qq.com

一、标准形式的凸优化问题

凸优化问题是形如

\begin{aligned} \text{minimize} \quad & f_0(x)\\ \text{subject to} \quad & f_i(x) \leq 0, & i = 1, \dots ,m\\ & a_i^T x = b_i, & i = 1, \dots ,p \end{aligned}

的问题，其中 $f_0, \dots ,f_m$ 是凸函数。

凸优化问题对比于普通优化问题多了三个约束条件：

目标函数必须是凸的
不等式约束函数必须是凸的
等式约束函数 $h_i(x) = a_i^Tx + b_i$ 必须是仿射的

有上述条件可以推断出，图优化问题的可行集也是凸集。

二、最优性条件

1. 局部最优解与全局最优解

定理 1 一个凸优化问题的局部最优解也是全局最优的。

设 $x$ 是凸优化问题的局部最优解，因此有
$f_0(x) = \inf\{f_0(z) | z \text{可行}, \|z - x\| \leq \mathbb{R} \}.$
现在假设存在全局最优解 $y$ ，且 $y \neq x$ 。因此有 $f_0(y) < f_0(x)$ 。

现在令
$z = (1 - \theta) x + \theta y, \quad \theta = \frac{\mathbb{R}}{2\|y - x\|}$
因此有 $\|z - x\| = \|- \theta x + \theta y\| = \theta \|y - x\| = \frac{\mathbb{R}}{2} \leq \mathbb{R}$

由于可行集是凸集，且 $f_0$ 是凸函数

2. 可微函数 $f_0$ 的最优性准则

常规凸优化问题

定理 2 $x$ 是最优的当且仅当它是可行的并且对所有可行 $y \in X$ 有

\nabla f_0(x)^T (y - x) \geq 0

根据凸函数的一阶条件有：
$f_0(y) \geq f_0(x) + \nabla f_0(x) (y - x)$
当 $\nabla f_0(x)^T (y - x) \geq 0$ ，有 $f_0(y) \geq f_0(x)$ 恒成立。

而当 $\nabla f_0(x)^T (y - x) < 0$ 时，取 $z(t) = ty + (1 - t)x, t \in [0, 1]$ 。我们有
$\frac{d}{dt}f_0(z(t)) \bigg|_{t = 0} = \nabla f_0(x)^T(y - x) < 0$
由于导数为负数，因此存在 $f_0(z(t)) < f_0(x)$ ，与 $x$ 是最优的矛盾。

此处也可以通过支撑超平面进行理解。

$\nabla f_0(x)^T$ 定义了 $X$ 在 $x$ 处的一个支撑超平面，如果 $\nabla f_0(x)^T(y - x) < 0$ ，则由 $\nabla f_0(x)^T$ 和 $x$ 确定的超平面与集合 $X$ 的内部相交，与 $x$ 是最优点矛盾。

无约束凸优化问题

定理 3 对于无约束问题，定理2可简化为 $x$ 是最优解当且仅当

\nabla f_0(x) = 0

由于 $f_0$ 是可微的，因此所有充分靠近 $x$ 的点都是可行的。我们定义
$y = x - t \nabla f_0(x)$
因此
$\lim_{t \rightarrow 0} \nabla f_0(x)^T(y - x) = \lim_{t \rightarrow 0} \nabla f_0(x)^T(- t \nabla f_0(x)) = \lim_{t \rightarrow 0} -t \| \nabla f_0(x) \|_2^2 \geq 0$
故 $\nabla f_0(x) = 0$

等式约束凸优化问题

考虑只含等式约束二没有不等式约束的问题，即

\begin{aligned} \text{minimize} \quad & f_0(x)\\ \text{subject to} \quad & Ax = b, \end{aligned}

其可行集是仿射的。

定理 4 对于等式约束问题， $x$ 是最优解当且仅当存在一个 $v$ 使得

x \in \text{dom}f_0, \quad Ax = b, \quad \nabla f_0(x) + A^Tv = 0

其中， $A^T = (\alpha_1, \alpha_2, \dots)$

非负象限中的极小化

考虑

\begin{aligned} \text{minimize} \quad & f_0(x)\\ \text{subject to} \quad & x \succeq 0 \end{aligned}

定理 5 $x$ 是最优解当且仅当

x \in \textbf{dom} f_0, \quad x \succeq 0, \quad \begin{cases} \nabla f_0(x)_i \geq 0, x_i = 0\\ \nabla f_0(x)_i = 0, x_i > 0 \end{cases}

三、拟凸优化

形式：

\begin{aligned} \text{minimize}\quad & f_0(x)\\ \text{subject to}\quad & f_i(x) \leq 0, \quad i = 1, \dots, m\\ & Ax = b, \end{aligned}

其中 $f_0: \mathbb{R}^n \rightarrow \mathbb{R}$ 是拟凸函数， $f_1, \cdots, f_m$ 是凸函数。

局部最优解与最优性条件

拟凸优化问题可能有不是最优点的局部最优点。

$x$ 是最优的，如果

x \in X , \quad \nabla f_0(x)^T(y - x) > 0, \forall y \in X \backslash \{x\}.

这一性质与凸优化问题的类似性质有两个重要的不同：

该条件仅仅是充分条件，不是必要
该条件要求 $f_0$ 梯度非零，而原凸优化问题的条件不需要

通过凸可行性问题求解拟凸优化问题

通过一族凸不等式来表示拟凸函数的下水平集。 $\phi_t: \mathbb{R}^n \rightarrow \mathbb{R}, t \in \mathbb{R}$ 为满足

f_0(x) \leq t \Leftrightarrow \phi_t(x) \leq 0

的一族凸函数，并且对于每个 $x$ ， $\phi_t(x)$ 都是 $t$ 的非增函数，即对任意 $s \geq t$ 总有 $\phi_s(x) \leq \phi_t(x)$ 。

用 $p^*$ 表示拟凸优化问题的最优值，如果可行性问题：

\begin{aligned} \text{find}\quad & x\\ \text{subject to}\quad & \phi_i(x) \leq 0\\ & f_i(x) \leq 0, & i = 1, \cdots, m\\ & Ax = b \end{aligned}

是可行的，我们有 $p^* \leq t$ ，如果不可行，我们有 $p^* \geq t$ 。

通过二分法缩小 $p^*$ 的范围，可逐渐逼近最优值。