凸优化基础（Convex Optimization basics）

JimmyCM

18482人浏览 · 2020-02-23 16:33:01

JimmyCM · 2020-02-23 16:33:01 发布

总目录

一、凸优化基础（Convex Optimization basics）

凸优化基础（Convex Optimization basics）

二、一阶梯度方法（First-order methods）

三、对偶

Introduction

一个凸优化问题具有以下基本形式：
$\begin{aligned} \min_{x\in D} f(x)\qquad\qquad\qquad\\ subject\ to\qquad g_i(x)\leq 0,\ i=1,...,m \\ h_j(x)=0,\ j=1,...,r\\ \end{aligned}$

其中， $f$ 和 $g_i$ 都是凸函数的，且 $h_j$ 是仿射变换。凸优化问题有一个良好的性质，即对于一个凸优化问题来说，任何局部最小值都是全局最小值。凸优化问题是优化问题中被研究得比较成熟的，也是非凸优化的基础，许多非凸优化问题也被局部近似为凸优化问题求解。
convex

凸集和凸函数

凸集

凸集的定义

一个集合 $\subseteq R^n$ 是凸集，如果对任意 $x,y\in C$ 都有
$tx+(1-t)y\in C,\ for\ all\ 0\leq t\leq 1$

许多常见的集合，如空集，点、线集合，仿射空间 ${x:Ax=b,\ for\ given\ A,b\}$ 都属于凸集。正因如此，对于凸集中的变量做仿射变换得到的仍然是凸集。

凸函数

凸函数的定义

如果函数 $f:\ R^n\rightarrow R$ 是凸函数，那么函数的定义域 $dom(f)\subseteq R^n$ 是凸的，且对于所有 $x,y\in dom(f)$ ，都有
$f(tx+(1-t)y)\leq tf(x)+(1-t)f(y),\ for\ 0\leq t\leq 1$

换句话说，函数永远不会高于 $f (x)$ 和 $f (y)$ 两点连线。
convex function
在凸函数中有两种比较重要的特例：

严格凸函数（strictly convex）：把上述公式的 $\leq$ 变为 $<$ ，即函数永远低于 $f (x)$ 和 $f (y)$ 两点连线，把线性情况给排除了。
强凸函数（strongly convex）：即 $f$ 至少与二次函数一样凸，其最高阶数不小于2.
强凸意味着严格凸，他们都是凸函数的子集，他们的关系为：
$strongly\ convex \subset strictly\ convex \subset convex$

一些常见的函数如，指数函数，仿射函数，以及常用的范数和最大值函数等，都是凸函数。

凸函数的性质

从凸函数的定义我们可以得到两个性质：

一阶特性：如果 $f$ 是可微的，那么 $f$ 是凸函数，当且仅当 $d o m (f)$ 是凸的，且对于所有 $x,y\in dom(f)$ ，都有
$f(y)\geq f(x)+\nabla f(x)^T (y-x)$ 因此对于一个可微的凸函数来说， $\nabla f(x)=0 \Leftrightarrow x\ minimizes f$ 。
二阶特性：如果 $f$ 是二次可微的，那么 $f$ 是凸函数，当且仅当 $d o m (f)$ 是凸的，且对于所有 $x\in dom(f)$ 都有 $\nabla ^2 f(x)\geq 0$ 。

其次我们还能得到詹森不等式（Jensen’s inequality）：如果 $f$ 是凸的，且 $X$ 是定义在 $d o m (f)$ 上的一个随机变量，那么有 $f(E[X])\leq E[f(x)]$ 。

凸优化问题

前面我们给出了凸优化问题的定义，这里我们讨论凸优化问题的一些性质。

解集

令 $X_{opt}$ 为一个给定凸优化问题的所有解的集合，其可以写为：
$X_{opt}=\arg\min_{x\in D} f(x)$

$subject\ to\qquad g_i(x)\leq 0,\ i=1,...,m$

$A x = b$

则 $X_{opt}$ 为凸集。
若 $f$ 为严格凸函数，那么解是唯一的，即 $X_{opt}$ 只包含一个元素。

一阶最优化条件

对于一个凸优化问题
$\min_{x}f(x)\ subject\ to\ x\in C$

且 $f$ 可微，一个可行点是最优的，当
$\nabla f(x)^T(y-x)\geq 0$

换句话说，从当前点 $x$ 起的所有可行方向都与梯度方向对齐。当最优化问题是无约束时，该条件简化为 $\nabla f(x)=0$ 。

凸优化问题的层次

凸优化问题有许多分支，常见的有线性规划（linear programs, LPs），二次规划（qudaratic programs, QPs），半定规划（semidefinite programs, SDPs），锥规划（cone programs, CPs）。他们的关系为：
$\subset QPs \subset SDPs \subset CPs \subset Convex\ Programs$

典型的凸优化问题

线性规划

线性规划是最典型的一类凸优化问题，其基本形式为：
$\begin{aligned} \min_{x} c^Tx\\ subject\ to\qquad Dx\leq d\\ Ax=b \end{aligned}$

许多解决线性规划的方法是单纯形法和内点法。压缩感知中的基追踪算法就是线性规划问题。
例子：基追踪
给定 $y\in R^n$ 和 $X\in R^{n\times p}$ ，其中 $p > n$ 。对于一个欠定线性系统 $X\beta =y$ ，我们想要找到其最稀疏的解，其可以表达为非凸优化形式：
$\begin{aligned} \min_{\beta}\|\beta\|_0\\ subject\ to\qquad X\beta =y \end{aligned}$

其中， $\|\beta\|_0=\sum^p_{j=1}1\{\beta_j \neq0\}$ ，为 $\beta$ 的零阶范数（ $l_0$ norm）。
由于该问题是非凸的，我们可以对其做凸松弛，即进行 $l_1$ norm近似，常常称为基追踪：
$\begin{aligned} \min_{\beta}\|\beta\|_1\\ subject\ to\qquad X\beta =y \end{aligned}$

基追踪是一个线性规划问题，可以将其变为基本形式：
$\begin{aligned} \min_{\beta,z}1^Tz\\ subject\ to\qquad z\geq \beta\\ z\geq -\beta\\ X\beta =y \end{aligned}$

二次规划

二次规划的基本形式为：
$\begin{aligned} \min_{x}\ c^Tx+\frac{1}{2}x^TQx\\ subject\ to\qquad Dx\leq d\\ Ax=b \end{aligned}$

其中， $Q\succeq 0$ ，即为正定的。
例子：支持向量机（SVM）
给定 $y\in \{-1,1\}^n$ ， $X\in R^{n\times p}$ 有行向量 $x_1,...,x_n$ ，则支持向量机问题（support vector machine）定义为：
$\begin{aligned} \min_{\beta,\beta_0,\xi} &\frac{1}{2}\|\beta\|^2_2+C\sum^n_{i=1}\xi_i\\ subject\ to\qquad & \xi_i\geq 0,\ i=1,...,n\\ &y_i(x_i^T\beta + \beta_0) \geq1-\xi_i,\ i=1,...,n \end{aligned}$

例子：lasso
给定 $y\in R^n$ ， $X\in R^{n\times p}$ ，则lasso问题定义为：
$\begin{aligned} \min_{\beta} \|y-X\beta\|^2_2\\ subject\ to\qquad \|\beta\|_1\leq s \end{aligned}$