数学优化入门：凸优化

墨蓝 2022-06-07 08:50 493阅读 0赞

本文转载自http://blog.csdn.net/column/details/13248.html，仅用作个人学习；如需转载请联系原创作者；如需删除，请见谅并联系本人。

做科研时，曾花了段时间学习凸优化，后来发现ML中其应用也非常普遍，想来今后可能还会接触，干脆做个系统的总结，方便以后查询。

博文内容主要参考Boyd（Stanford）的Convex Optimization，配套的slides，以及部分网络材料，感兴趣的朋友可以一起学习探讨。

--------------------

# 1、前言 #

凸优化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。虽然条件苛刻，但应用广泛，具有重要价值，主要体现在：

*  凸优化本身具有很好的性质  
    一来，凸问题的局部最优解就是全局最优解。二来，凸优化理论中的Lagrange对偶，为凸优化算法的最优性与有效性提供了保证。近些年来关于凸问题的研究非常透彻，以至于只要把某一问题抽象为凸问题，就可以近似认为这个问题已经解决了。
 *  凸优化具有很强扩展性  
    对于非凸问题，通过一定的手段，要么可以等价地化归为凸问题，要么可以用凸问题去近似、逼近。例如，几何规划、整数规划，虽然本身是非凸的，但是可以借助凸优化手段去解，这就极大地扩张了凸优化的应用范围。  
    以深度学习来说，其中关键的反向传播（Back Propagation）算法，本质就是凸优化算法中的梯度下降法，即使问题极度非凸，梯度下降还是有很好的表现，当然深度学习的机制还有待研究。
 *  凸优化的应用十分广泛  
    如线性回归、范数逼近、插值拟合、参数估计，以及许多的几何问题等。
 *  针对其他非凸问题的研究还不充分  
    凸优化之重要，从另一个角度说，就是我们没有找到很好的非凸优化的算法，这一部分还有许多学者都在努力。

虽然说凸优化的研究已经比较成熟，但由于还没有行业公认的通行解决方法，所以Boyd也说过“we cannot claim that solving general convex optimization problem is a technology, like solving least-squares or linear programming problems……it is fair to say that interior-point methods are approaching a technology”，即目前已有的凸优化方法还不能称之为技术。但还是说那句话，基本上，如果你把一个现实问题建成凸优化问题模型，你就可以认为这个问题已经被解决了。

多说几句，对于非凸优化中，凸优化同样起到很重要的作用：

*  解决一个非凸优化问题时，可以先试图建立一个简化的多凸优化模型，解出以后作为非凸问题的一个起始点
 *  很多非凸优化问题的启发式算法的基础都是基于凸优化
 *  可以先建立非凸优化的松弛问题，使用凸优化算法求解，然后作为非凸优化问题的上限或下限

那么，下面将分几章花些篇幅好好讲解下凸优化的主要知识点和常用结论。

--------------------

# 2、凸集 #

## 2.1 定义 ##

A set C is convex, if θx\+(1−θ)y∈C, for any x,y∈C and θ∈R with 0≤θ≤1.

简言之，凸集即过集合C内任意两点的线段均在集合C内。

## 2.2 常用凸集 ##

*  Rn
 *  The non-negative orthant: Rn\+
 *  Norm ball: \{ x:∥x∥≤1\}
 *  Affine subspace: \{ x∈Rn:Ax=b,A∈Rn×n,b∈Rn×1\}
 *  Polyhedra: \{ x∈Rn:Ax≺=b\}
 *  Intersections of convex sets (Note here that the union of convex sets in general is not convex)
 *  Postive semidefinite cone: Sn\+=\{ X∈Sn|X≻=0\} (Note: 将前述半正定矩阵改为正定阵、负定阵、半负定阵，仍成立)

# 3、凸函数 #

## 3.1 定义 ##

A function f:Rn→R is convex, if its domain D(f) is a convex set, and if f(θx\+(1−θ)y)≤θf(x)\+(1−θ)f(y)for all x,y∈D(f) and θ∈R,0≤θ≤1.

凸函数的一阶微分条件：

Suppose a function f:Rn→R is differentiable, then f is convex if and only if: D(f) is a convex set and for all x,y∈D(f), f(y)≥f(x)\+(∇xf(x))T(y−x).

凸函数的二阶微分条件：

Suppose a function f:Rn→R is twice differentiable, then f is convex if and only if: D(f) is a convex set and its Hessian is postive semidefinite.

## 3.2 常用凸函数 ##

*  负熵函数：xlogx
 *  范数函数：∥x∥p
 *  f(x)=max(x1,...,xn)
 *  f(x)=log(ex1\+...\+exn)
 *  f(x)=(∏ni=1xi)1/n,D(f)=Rn\+\+
 *  f(X)=log(detX),D(f)=Sn\+\+

## 3.3 保凸运算 ##

*  凸函数的非负加权和
 *  凸函数与仿射变换的复合：g(x)=f(Ax\+b)
 *  逐点最大、最小值：f(x)=max(f1(x),...,fn(x))，g(x)=infy∈Cf(x,y)
 *  透视变换：g(x,t)=tf(x/t)

# 4、凸优化问题 #

## 4.1 定义 ##

通常将一个优化问题写成以下标准形式：

mins.t.:f(x)gi(x)≤0,i=1,...,mhj(x)=0,j=1,...,t

当f(x)和gi(x)均为凸函数，hj(x)均为仿射函数时，上述优化问题称之为凸优化问题。

关于凸优化问题再补充几个特点：

*  一般没有解析解
 *  不考虑等式约束时，计算复杂度大致正比于max\{ n3,n2m,F\}，其中F是对所有gi及其一阶、二阶导的计算代价
 *  虽然难以识别，但可以通过很多手段进行转化

## 4.2 优化问题的等价形式 ##

注意以下等价形式不要求为凸问题，等价和相同不是一个概念。

*  变量替换
 *  目标函数和约束函数的变换
 *  松弛变量（不等式约束转变为等式约束加非负约束）
 *  消除等式约束
 *  消除线性等式约束
 *  引入等式约束
 *  优化部分变量
 *  上境图问题形式
 *  隐式与显式约束

## 4.3 常用凸优化问题 ##

### 1）Least-squares（LS） ###

作为凸优化问题的一个特例，其成熟解法已经可以称之为technology。

对于Least-squares问题：min∥Ax−b∥22，其解析解为x∗=(ATA)−1ATb，对于A∈Rk×n，在不结构化情况下，计算复杂度为O(n2k)。

### 2）Linear programming（LP） ###

作为凸优化问题的一个特例，虽然没有解析解，但仍有可靠高效的算法和工具解决，也可以称之为technology。

对于Linear programming问题：

mins.t.:cTx\+daTix≤bi,i=1,...,m

当  m≥n 时，计算复杂度为  O(n2m) 。

但线性规划问题并不像前面的最小二乘问题那么好辨别，通常需要通过一些标准的小技巧将原问题转化为线性规划问题，如包含l1范数或者l∞范数，或者分段线性函数的问题等。

### 3）Quadratic programming（QP） ###

mins.t.:12xTPx\+qTx\+rGx≺=hAx=bP∈Sn\+

### 4）Quadratically constrained quadratic programming（QCQP） ###

mins.t.:12xTP0x\+qT0x\+r012xTPix\+qTix\+riAx=bPi∈Sn\+

### 5）Second-order cone programming（SOCP） ###

mins.t.:fTx∥Aix\+b∥2≤cTix\+diFx=g

### 6）Semidefinite programming （SDP） ###

mins.t.:Tr(CX)Tr(AiX)=biX≻=0

--------------------

# 5、Lagrange Duality #

对于有约束的优化问题，通过拉格朗日法可以将其转变为等价的无约束优化问题。在这个过程中，新构造的拉格朗日函数存在好玩的对偶性质，从而衍生出了对偶问题。原问题与对偶问题之间的特殊性质，为我们研究优化问题提供了新的方向和方法。

因此，这部分的思路是：对4.1定义的优化问题，通过拉格朗日法构造拉格朗日函数，从而生成原问题Primal problem和对偶问题Dual problem，然后介绍一些引理，揭示原问题与对偶问题之间的关系。

## 5.1 Primal problem ##

首先要求4.1提出的标准优化问题中的f(x)、gi(x)和hj(x)均为连续可微函数，构造广义拉格朗日函数

L(x;α,β)=f(x)\+∑i=1mαigi(x)\+∑j=1tβjhj(x)

其中，  α 和  β 是拉格朗日乘子，且  αi≥0 ，  x 称为primal变量，  α 和  β 称为dual变量。   
注意，L(x;α,β)是关于α和β的仿射函数。

从而，我们可以构造Primal problem：

minxθP(x)=minx\[maxα,β;αi≥0L(x;α,β)\]

显然有：

θP(x)=f(x)\+\{ 0,ifxisprimalfeasible\+∞,ifxisnotprimalfeasible

其中，primal feasible意味着x满足4.1优化问题中的所有约束条件。  
注意，θP(x)是关于x的凸函数。

因此，可以看出这里构建的primal problem和4.1的优化问题是等价的，即同解。这样一来，就把原始优化问题表示成了广义拉格朗日函数的极小极大问题，我们定义primal problem的最优值p∗=minxθP(x)=θP(x∗)，称为primal problem的值。

## 5.2 Dual problem ##

好了，下面我们来构造神奇的Dual problem：

minα,β;αi≥0θD(α,β)=maxα,β;αi≥0\[minxL(x;α,β)\]

对于上述广义拉格朗日函数的极大极小问题，定义dual problem的最优值d∗=maxα,β;αi≥0θD(α,β)=θD(α∗,β∗)，称为primal problem的值。  
注意，θD(α,β)是关于α和β的凹函数。

## 5.3 Primal problem与Dual problem的关系 ##

### 1）Lemma 1 ###

If (α,β) are dual feasible, then θD(α,β)≤p∗.

### 2）Lemma 2（Weak Duality） ###

For any pair of primal and dual problems, d∗≤p∗.

注意，此性质always holds，无论优化问题是凸的还是非凸的，通常用来寻找困难问题的下界。

### 3）Lemma 3 （Strong Duality） ###

For any pair of primal and dual problems, which satisfy certain conditions called constraint qualifications, then d∗=p∗.

实际上有不少constraint qualifications可以保证强对偶，我们介绍几种常用的constraint qualification：

*  f=f∗∗ where f is the perturbation function relating the primal and dual problems and f=f∗∗ is the biconjugate of f
 *  f is convex and lower semi-continuous (equivalent to the first point by the Fenchel-Moreau theorem)
 *  the primal problem is a linear OP
 *  Slater’s condition for a convex optimization problem

其中，Slater’s condition更常用，we say that the problem satisfies Slater’s condition if it is strictly feasible, that is:

∃x0∈D(f):gi(x0)<0,i=1,...,m;hj(x0)=0,j=1,...,t

即，if the primal problem is convex, and satisfies the weak Slater’s condition, then strong duality holds.

注意，有些非凸问题也可以满足强对偶。

## 5.4 Complementary slackness ##

也称作KKT complementarity，即

If strong duality holds, then α∗igi(x∗)=0 for any i.

直观来看，就是如果α∗i>0则gi(x∗)=0，如果gi(x∗)<0则α∗i=0。

## 5.5 KKT条件 ##

有以下逻辑：当strong duality存在，且x∗为primal optiaml和α∗,β∗为dual optiaml时，则KKT条件成立；当KKT条件成立时，有x∗为primal optiaml和α∗,β∗为dual optiaml。

下面介绍KKT条件：

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪x∗isprimalfeasibleα∗,β∗isdualfeasiblecomplementaryslackness∇xL(x∗;α∗,β∗)=0