凸优化问题¶

1. 简介¶

凸优化问题具有这样的形式：

\[ \min_{x} \ f_0(x) \quad \\ \text{subject to:} \quad f_i(x) \leq b_i, \quad i = 1, \dots, m, \\ \]

其中，目标函数和约束函数 \(f_0, \dots, f_m\) 是凸函数。

一个函数 \(f: \mathbb{R}^n \to \mathbb{R}\) 是凸函数，当且仅当对于任意的 \(x, y \in \mathbb{R}^n\) 和 \(\theta \in [0, 1]\)，满足以下不等式：

\[ f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta)f(y) \]

直观的几何理解是，凸函数上任意两点间的连线总在函数图像的上方或者重合。

教科书认为，若一个优化问题可以被化作凸优化问题，那么这个问题基本可以说是解决了，就是这样强大。比如一些经典的问题，如最小二乘问题和线性规划问题，实际上也是凸优化问题，他们已经有了完整的解决方案。历史上，苏联的科学家 Nesterov 与 Nemirovski 最早发现，使得优化问题变“容易”的关键性质，是函数的凸性，并且，他们引入了内点法来有效求解凸问题。实际中很少能像最小二乘或者函数求导那样简单地能获得问题的解析解（代数表达式），但是只要能化为凸优化问题，往往就意味着可以利用高效的数值方法求出问题的最优解。

2. 对偶¶

学过微积分的读者，应该对这样的问题有印象：求解含有等式约束的多变量极值问题。当时我们的做法是引入拉格朗日函数，将等式约束问题转化为无条件约束问题。其几何意义就是获得几个曲面的的交线，在这个交线上寻找最优点。

在优化理论中，也有类似的概念，称为对偶（duality）。它将一个有约束问题转化成一个无约束问题，后者称为对偶问题。

我们考虑这样的优化问题：

\[ p^* = \min_{x} \ f_0(x) \quad \\ \text{subject to:} \quad f_i(x) \leq b_i, i = 1, \dots, m, \\ \quad h_j(x) = 0, j=1,\dots, q, \]

那么其拉格朗日函数表示为：

\[ L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i \left( f_i(x) - b_i \right) + \sum_{j=1}^q \nu_j h_j(x), \]

其中：

\(\lambda_i \geq 0\) 是不等式约束的拉格朗日乘子；
\(\nu_j\) 是等式约束的拉格朗日乘子

定义拉格朗日对偶函数是拉格朗日函数的关于变量 \(x\) 取得的最小值：

\[ g(\lambda, \nu) = \inf_x L(x, \lambda, \nu) \\ = \inf_x (f_0(x) + \sum_{i=1}^m \lambda_i \left( f_i(x) - b_i \right) + \sum_{j=1}^q \nu_j h_j(x)) \]

我们容易证明这样的性质：对偶函数构成原问题最优值 \(p^*\) 的下界，即对任意 \(\lambda>0, \nu\) 都有：

\[ g(\lambda, \nu) \leq p^* \]

这意味着我们只要求出 \(g(\lambda, \nu)\) 的上界 \(d^*\)，就可以逼近原问题的下界 \(p^*\)。

于是，我们就这样定义原问题的对偶问题：

\[ d^*=\max_{\lambda \geq 0, \nu} \ g(\lambda, \nu) \]

很容易知道，即使原问题不是凸的，对偶问题也是凸优化问题。

我们容易得到： \(d^* \leq p^*\)。根据是否取到等号来判断是强对偶性或者是弱对偶性。所以我们有时可以通过求对偶问题的解，再转化成原问题的解。

对于一个满足强对偶性的问题，若这个问题的最优解为 \(x^*\)，其对偶问题的解是 \((\lambda^*, \nu^*)\)。则它们满足 KKT(Karush-Kuhn-Tucker) 条件：

原始可行性：

\[ f_i(x^*) \leq 0, \quad h_j(x^*) = 0. \]

对偶可行性：

\[ \lambda_i^* \geq 0, \quad i = 1, 2, \dots, m. \]

互补松弛条件：

\[ \lambda_i^* f_i(x^*) = 0, \quad i = 1, 2, \dots, m. \]

拉格朗日梯度条件：

\[ \nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^q \nu_j^* \nabla h_j(x^*) = 0. \]

KKT 条件是一组最优解的必要条件。若原问题也是凸的，则 KKT 条件成为解的充分条件。

KKT 条件非常重要，对一些问题来说，可以将求解原问题转化成求解满足 KKT 条件的点，从而找到最优解。

后面，我们介绍一些典型的凸优化问题。