凸优化2021-09-21

背景知识函数符号解释 $\mathbf{inf}$ 和 $\mathbf{sup}$ 拉格朗日乘子法凸函数仿射函数其它符号无约束等式约束不等式约束（KKT条件）对偶问题原始问题对偶问题原始问题和对偶问题的关系对偶问题求解总结参考资料

背景知识

函数符号解释

$\min _{x \in D} f(x)$ $D$ $x$ $f(x)$ 的最小值
$\min _{x \in D} f(x, \lambda)$ $f$ $x,\lambda$ $\lambda$ $x$ $f$ 最小
$g(\lambda) = \min _{x \in D} f(x, \lambda)$ ，该式的含义是：
- $g(\lambda)$ $\lambda$ 的函数
- $\lambda = y$ $g(\lambda)$ $f(x,\lambda)$ $\lambda = y$ $x$ $f$ 取到最小值。例如：
$\begin{matrix} (1) & \begin{aligned} f (x, λ) & = x^{2} + λ^{2} \\ g (λ) & = min_{x \in D} f (x, λ) \\ g (4) & = min_{x \in D} f (x, 4) \\ = min_{x \in D} (x^{2} + 16) \\ = 0 + 16 = 16 \end{aligned} \end{matrix}$
$v=\max _{\lambda} \min _{x} f(x, \lambda)$ $\min _{x} f(x, \lambda)$ $\lambda$ $g(\lambda)$ $g(\lambda)$ 求最大值，即：
$\begin{matrix} (2) & \begin{aligned} g (λ) = min_{x} f (x, λ) \\ v = max_{λ} g (λ) \end{aligned} \end{matrix}$

$\mathbf{inf}$ $\mathbf{sup}$

$\mathbf{inf}$ ：下确界（infimum）
$\mathbf{sup}$ ：上确界（supremum）
和min、max有相似之处，细节略有不同。示例：
$f(x) = \frac{\sin(x)}{x}$ $x=0$ $\mathbf{max}f(x)$ $\mathbf{sup}f(x)$ 存在且为1。

拉格朗日乘子法

凸函数

下图为凸函数图像示例：

凸函数

$f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ 是凸的，则：
$\begin{matrix} (3) & \begin{aligned} \forall x, y \in dom f, \forall θ \in [0, 1] \\ f (θ x + (1 - θ) y) ⩽ θ f (x) + (1 - θ) f (y) \end{aligned} \end{matrix}$
$f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ 是凹的，则：

\begin{matrix} (4) & \begin{aligned} \forall x, y \in dom f, \forall θ \in [0, 1] \\ f (θ x + (1 - θ) y) ⩾ θ f (x) + (1 - θ) f (y) \end{aligned} \end{matrix}

仿射函数

$\vec{x} \in \mathbb{R}^{n}，\vec{b} \in \mathbb{R}^{m}$ ，那么：

\begin{matrix} (5) & \vec{x} \to A \vec{x} + \vec{b} \end{matrix}

$\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ 的仿射变换，该过程称为仿射函数：

\begin{matrix} (6) & f (x) = A x + b, x \in R^{n} \end{matrix}

例如，以下为简单的仿射函数：

$a_1 x_1 + a_2 x_2 + \cdots , a_n x_n + b$

仿射函数的重要性质：既凹且凸，即在凹凸函数不等式中，仿射函数可以取等号。

\begin{matrix} (7) & f (θ x + (1 - θ) y) = θ f (x) + (1 - θ) f (y) \end{matrix}

其它符号

$dom \; f$ $f$ 的定义域
$\bigcap S_i$ $S$ 的交集

无约束

求导，令导数为0即可。

等式约束

问题如下：

\begin{matrix} (8) & \begin{matrix} m i n f (x) \\ s . t . h (x) = 0 \end{matrix} \end{matrix}

等式约束

$x$ $f(x)$ 增大或减小，因此不是可行解。

$\triangledown f(x) = \lambda \triangledown h(x)$ 。

构造朗格朗日函数：

\begin{matrix} (9) & L (x, λ) = f (x) + λ h (x) \end{matrix}

$L(x, \lambda)$ $x$ $\lambda$ 求偏导可得：

\begin{matrix} (10) & \begin{matrix} {\begin{matrix} ▽_{x} L (x, λ) = ▽ f (x) + λ ▽ h (x) = 0 \\ ▽_{λ} L (x, λ) = h (x) = 0 \end{matrix} \end{matrix} \end{matrix}

求解以上方程即可。

不等式约束（KKT条件）

问题如下：

\begin{matrix} (11) & \begin{matrix} m i n f (x) \\ s . t . g (x) <= 0 \end{matrix} \end{matrix}

$g(x)$ $f(x)$ 向内侧为等高线数值降低方向。两种情况如下：

两种情况

情况一：极值点在可行域以内
$\begin{matrix} (12) & \begin{matrix} {\begin{matrix} ▽ f (x) = 0 \\ g (x) < 0 \\ λ = 0 \end{matrix} \end{matrix} \end{matrix}$
情况二：极值点在边界

\begin{matrix} (13) & \begin{matrix} {\begin{matrix} ▽ f (x) + λ ▽ g (x) = 0 \\ g (x) = 0 \\ λ \geq 0 \end{matrix} \end{matrix} \end{matrix}

将以上两种情况进行合并，得：

\begin{matrix} (14) & \begin{matrix} {\begin{matrix} ▽ f (x) + λ ▽ g (x) = 0 \\ g (x) \leq 0 \\ λ \geq 0 \\ λ g (x) = 0 \end{matrix} \end{matrix} \end{matrix}

这个方程组就是该问题的 KKT 条件，只有满足这些条件才会存在极小值。

$\lambda$ 大于等于0？

$g(x)$ $f(x)$ 的梯度指向右侧，因此两个函数的梯度方向相反。

对偶问题

原始问题

$f(x),g_i(x),h_j(x)$ $R^n$ 上的连续可微函数。

定义如下的约束最优化问题为原始优化问题或原问题：

\begin{matrix} (15) & \begin{matrix} \underset{x \in R^{n}}{m i n} f (x) \\ s . t . g_{i} (x) \leq 0, i = 1, 2, . ., k \\ h_{j} (x) = 0, j = 1, 2, . ., l \end{matrix} \end{matrix}

$f(x)$ $f(x)$ 可以是非凹非凸函数。

原问题直接优化比价困难：

$k+l$ 个约束

2. 原问题凹凸性不明确

而对于原问题的拉格朗日对偶问题，其优点为：

1. 只有1个约束。

2. 拉格朗日对偶为一定是凹的。

引入拉格朗日函数：

\begin{matrix} (16) & \begin{matrix} L (x, α, β) = f (x) + \sum_{i = 1}^{k} α_{i} g_{i} (x) + \sum_{j = 1}^{l} β_{i} h_{i} (x) \\ 其 中 ， x = {(x^{(1)}, x^{(2)}, . . ., x^{(n)})}^{T} \in R^{n}, α_{i} 、 β_{j} 是 拉 格 朗 日 乘 子 ， α_{i} \geq 0 \end{matrix} \end{matrix}

$x$ 的函数：

\begin{matrix} (17) & θ_{P} (x) = \underset{α, β; α_{i} \geq 0}{m a x} L (x, α, β) \end{matrix}

$x$ $i$ $g_i(x)>0$ $h_j(x) \neq 0$ $g_i(x)>0$ $\alpha_i \to +\infty$ $\theta_P(x) = +\infty$ $h_j(x) \neq 0$ $\beta_j \to +\infty$ $\beta_j \to -\infty$ $\theta_P(x) = \infty$ $\alpha_i,\beta_j$ 均置为0。那么：

\begin{matrix} (18) & θ_{P} (x) = \underset{α, β; α_{i} \geq 0}{m a x} [f (x) + \sum_{i = 1}^{k} α_{i} g_{i} (x) + \sum_{j = 1}^{l} β_{i} h_{i} (x)] = \infty \end{matrix}

$x$ $g_i(x) \leq 0$ $h_j(x) = 0$ ，那么：

\begin{matrix} (19) & θ_{P} (x) = \underset{α, β; α_{i} \geq 0}{m a x} [f (x) + \sum_{i = 1}^{k} α_{i} g_{i} (x) + \sum_{j = 1}^{l} β_{i} h_{i} (x)] = f (x) \end{matrix}

由以上分析，得：

\begin{matrix} (20) & \begin{array}{r} θ_{P} (x) = {\begin{array}{c} f (x) ， x 满 足 原 始 问 题 约 束 \\ \infty ， x 不 满 足 原 始 问 题 约 束 \end{array} \end{array} \end{matrix}

则极小化如下原始问题等价于原始最优化问题，即有相同的解：

\begin{matrix} (21) & \underset{x}{m i n} θ_{p} (x) = \underset{x}{m i n} \underset{α, β; α_{i} \geq 0}{m a x} L (x, α, β) \end{matrix}

$\qquad \underset{x}{min} \underset{\alpha,\beta;\alpha_i \geq 0}{max} \; L(x,\alpha,\beta)$ 称为广义拉格朗日函数的极小极大问题。

定义原始问题的最优值：

\begin{matrix} (22) & p^{*} = \underset{x}{m i n} θ_{P} (x) \end{matrix}

称为原始问题的最优解。

对偶问题

$\alpha,\beta$ 的拉格朗日对偶函数：

\begin{matrix} (23) & \begin{matrix} θ_{D} (α, β) = \underset{x}{m i n} L (x, α, β) \\ α \geq 0 \end{matrix} \end{matrix}

对偶函数重要性质：

$\theta_D(\alpha,\beta)$ 一定是凹函数。
$\alpha \geq 0$ $\theta_D(\alpha,\beta)$ $p^*$ $\forall \alpha \geqslant 0 \Rightarrow \theta_D(\alpha,\beta) \leqslant p^{*}$ $p^*$ $\max \theta_D(\alpha,\beta)$ 进行逼近。

对偶的最大值

对偶函数极大化问题称为广义拉格朗日函数的极大极小问题：

\begin{matrix} (24) & \underset{α, β; α_{i} \geq 0}{m a x} θ_{D} (α, β) = \underset{α, β; α_{i} \geq 0}{m a x} \underset{x}{m i n} L (x, α, β) \end{matrix}

将广义拉格朗日函数的极大极小问题表示为约束最优化问题，称为原始问题的对偶问题：

\begin{matrix} (25) & \begin{matrix} \underset{α, β; α_{i} \geq 0}{m a x} θ_{D} (α, β) = \underset{α, β; α_{i} \geq 0}{m a x} \underset{x}{m i n} L (x, α, β) \\ s . t . α_{i} \geq 0, i = 1, 2, . ., k \end{matrix} \end{matrix}

定义对偶问题的最优值，称为对偶问题的解：

\begin{matrix} (26) & d^{*} = \underset{α, β; α_{i} \geq 0}{m a x} θ_{D} (α, β) \end{matrix}

$定理 1.1 若原始问题和对偶问题都有最优解，则 \\ \qquad \qquad \qquad \qquad d^{*}=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta) \leqslant \min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=p^{*}$

$证明：对任意的 \alpha，\beta 和 x，有：$

$\qquad \;\theta_{D}(\alpha, \beta)=\min _{x} L(x, \alpha, \beta) \leqslant L(x, \alpha, \beta) \leqslant \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=\theta_{P}(x)$

$即：\theta_{D}(\alpha, \beta) \leq \theta_{P}(x)$

$由于原始问题和对偶问题均有最优值，所以：$

$\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \theta_{D}(\alpha, \beta) \leqslant \min _{x} \theta_{P}(x)$

$即：d^{*}=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta) \leqslant \min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=p^{*}$

$问题得证。$

原始问题和对偶问题的关系

$p^* = d^*$ 。并且，能够通过对偶问题的解，得到原问题的解！

强对偶

$\Large \color{#FF0000}原始问题：$

\begin{matrix} (27) & \begin{matrix} \underset{x \in R^{n}}{m i n} f (x) \\ s . t . g_{i} (x) \leq 0, i = 1, 2, . ., k \\ h_{j} (x) = 0, j = 1, 2, . ., l \end{matrix} \end{matrix}

$\Large \color{#FF0000}对偶问题：$

\begin{matrix} (28) & \begin{matrix} \underset{α, β; α_{i} \geq 0}{m a x} θ_{D} (α, β) = \underset{α, β; α_{i} \geq 0}{m a x} \underset{x}{m i n} L (x, α, β) \\ s . t . α_{i} \geq 0, i = 1, 2, . ., k \end{matrix} \end{matrix}

$定理1.2 \quad 对原始问题和对偶问题，假设函数f(x)和g_i(x)是凸函数，h_j(x)是仿射函数，并且不等式约束g_i(x)是严格执行的，\\ \qquad \qquad则x^*和\alpha ^*，\beta ^* 分别是原始问题和对偶问题的解的充分必要条件是x^*，\alpha ^*，\beta ^*满足下面的KKT条件：$

\begin{matrix} (29) & \begin{matrix} g_{i} (x^{*}) ⩽ 0, i = 1, 2, \dots, k \\ h_{j} (x^{*}) = 0 j = 1, 2, \dots, l \\ α_{i}^{*} ⩾ 0, i = 1, 2, \dots, k \\ \nabla_{x} L (x^{*}, α^{*}, β^{*}) = 0 \\ α_{i}^{*} g_{i} (x^{*}) = 0, i = 1, 2, \dots, k \end{matrix} \end{matrix}

$定理概括：KKT条件 \Leftrightarrow x^*，\alpha ^*，\beta ^*是原始问题和对偶问题的解$ 。

定理部分解释：

$g_i(x)$ $g_i(x) < 0,i=1,2,\cdots,k$
条件1 & 条件2：原始问题约束条件
$公式（23）$ 对偶函数定义
$x^*$ $L(x,\alpha,\beta)$ $\alpha ^*，\beta ^*$ 是对偶问题的解？？？
条件5：又称互补松弛条件。 $x^*，\alpha ^*，\beta ^*$ $\alpha_{i}^{*} g_{i}\left(x^{*}\right)=0, i=1,2, \cdots, k$ 。证明如下：
$f(x^*)=p^*,\theta_D(\alpha^*,\beta^*)=d^*$ $f(x^*)$ $f(x)$ $\theta_D(\alpha^*,\beta^*)$ $\theta_D(\alpha,\beta)$ 的最大值
$p^* = d^*$ $f(x^*)= \theta_D(\alpha^*,\beta^*)$ 。
根据定义：
$\begin{matrix} (30) & \begin{aligned} f (x^{*}) = θ_{D} (α^{*}, β^{*}) & = min_{x} L (x, α^{*}, β^{*}) \\ = min_{x} {f (x) + \sum_{i = 1}^{k} α_{i}^{*} g_{i} (x) + \sum_{j = 1}^{l} β_{i}^{*} h_{i} (x)} \\ \leq f (x^{*}) + \sum_{i = 1}^{k} α_{i}^{*} g_{i} (x^{*}) + \sum_{j = 1}^{l} β_{i}^{*} h_{i} (x^{*}) \end{aligned} \end{matrix}$
$\because (在满足约束的条件下)\alpha^* \geq 0,g_i(x^*) \leq 0 \\ \therefore \alpha^* *g_i(x^*) \leq 0$
$又 \because h_i(x^*)=0 \\ \therefore f(x^*) \geq f(x^*) + \sum_{i=1}^{k} \alpha^*_i g_i(x^*) + \sum_{j=1}^{l} \beta^*_i h_i(x^*)$
$\therefore f(x^*) = f(x^*) + \sum_{i=1}^{k} \alpha^*_i g_i(x^*) + \sum_{j=1}^{l} \beta^*_i h_i(x^*)$
$\therefore \alpha^*_i g_i(x^*) = 0, \quad i=1,2, \cdots, k$

对偶问题求解总结

使用对偶方法求解最优化问题步骤：

确定原始问题
$\begin{matrix} (31) & \begin{matrix} \underset{x \in R^{n}}{m i n} f (x) \\ s . t . g_{i} (x) \leq 0, i = 1, 2, . ., k \\ h_{j} (x) = 0, j = 1, 2, . ., l \end{matrix} \end{matrix}$
构造拉格朗日函数
$\begin{matrix} (32) & \begin{matrix} L (x, α, β) = f (x) + \sum_{i = 1}^{k} α_{i} g_{i} (x) + \sum_{j = 1}^{l} β_{i} h_{i} (x) \\ 其中， x = {(x^{(1)}, x^{(2)}, . . ., x^{(n)})}^{T} \in R^{n}, α_{i} 、 β_{j} 是拉格朗日乘子， α_{i} \geq 0 \end{matrix} \end{matrix}$
构造拉格朗日对偶函数
$\begin{matrix} (33) & \begin{matrix} θ_{D} (α, β) = \underset{x}{m i n} L (x, α, β) \\ α \geq 0 \end{matrix} \end{matrix}$
求解拉格朗日对偶函数
$\begin{matrix} (34) & ▽_{x} L (x, α, β) = 0 \end{matrix}$
对偶函数极大化
$\begin{matrix} (35) & \begin{matrix} \underset{α, β; α_{i} \geq 0}{m a x} θ_{D} (α, β) \\ s . t . α_{i} \geq 0, i = 1, 2, . ., k \end{matrix} \end{matrix}$

$例题1$ $p^* = \underset{\mathbf{x}}{\min} \parallel \mathbf{x} \parallel _2^2 \\ s.t. \mathbf{A} \mathbf{x} = \mathbf{b}$

$解：$ $L(\mathbf{x}, \mathbf{v}) = \mathbf{x}^T \mathbf{x} + \mathbf{v}^T(\mathbf{A} \mathbf{x} - \mathbf{b})$

$g(\mathbf{v}) = \underset{x}{\min} L(\mathbf{x},\mathbf{v})$

$\triangledown_\mathbf{x} L(\mathbf{x},\mathbf{v}) = 0$

$2 \mathbf{x}+\mathbf{A}^{T} \mathbf{v}=\mathbf{0} \Rightarrow \mathbf{x}^{*}(\mathbf{v})=-\frac{1}{2} \mathbf{A}^{T} \mathbf{v}$

$g(\mathbf{v})=L\left(\mathbf{x}^{*}(\mathbf{v}), \mathbf{v}\right)=-\frac{1}{4} \mathbf{v}^{T}\left(\mathbf{A} \mathbf{A}^{T}\right) \mathbf{v}-\mathbf{v}^{T} \mathbf{b}$

$d^{*}=\max _{\mathbf{v}}-\frac{1}{4} \mathbf{v}^{T}\left(\mathbf{A} \mathbf{A}^{T}\right) \mathbf{v}-\mathbf{v}^{T} \mathbf{b}$

$\mathbf{v} * =-2\left(\mathbf{A} \mathbf{A}^{T}\right)^{-1} \mathbf{b} \\d^{*} =\mathbf{b}^{T}\left(\mathbf{A} \mathbf{A}^{T}\right)^{-1} \mathbf{b}$

$\mathbf{x}^{*}$

$p^* = d^*$ ，通过对偶函数的解可以求得原函数的解，因此：

$\mathbf{x}^{*}=\mathbf{x}^{*}\left(\mathbf{v}^{*}\right)=\mathbf{A}^{T}\left(\mathbf{A} \mathbf{A}^{T}\right)^{-1} \mathbf{b}$

背景知识

函数符号解释

inf\mathbf{inf}和sup\mathbf{sup}

拉格朗日乘子法

凸函数

仿射函数

其它符号

无约束

等式约束

不等式约束（KKT条件）

对偶问题

原始问题

对偶问题

原始问题和对偶问题的关系

对偶问题求解总结

参考资料

$\mathbf{inf}$ $\mathbf{sup}$