关于凸优化 - aliceyangxi1987的博客 - CSDN博客
博客专家
关于凸优化
MachineLearning
本文结构：
凸优化有什么用？
什么是凸优化？
凸优化有什么用？
鉴于本文中公式比较多，先把凸优化的意义写出来吧，就会对它更有兴趣。
我们知道在机器学习中，要做的核心工作之一就是根据实际问题定义一个目标函数，然后找到它的最优解。
不过求解这种优化的问题其实是很难的，但是有一类问题叫做凸优化问题，我们就可以比较有效的找到全局最优解。
例如，SVM 本身就是把一个分类问题抽象为凸优化问题，利用凸优化的各种工具（如Lagrange对偶）进行求解和解释。深度学习中关键的算法反向传播（Back Propagation），本质也是凸优化算法中的梯度下降算法。
凸优化的价值也在于思维转变，当我们在现实生活中遇到计算量接近无穷大的问题时，我们要想办法将模型转换成“凸优化问题”，因为凸优化已经相对嚼得比较烂，所以只要问题转化成凸优化，我们就可以分布迭代去运算。
当然现实中绝大部分优化问题并不是凸优化问题，但是凸优化非常重要, 因为：
还是有相当一部分问题是或等价于凸优化问题，例如下面会举例说明 SVM，最小二乘等。
大部分凸优化问题解起来比较快。
很多非凸优化或NP-Hard的问题可以转化（并非是等价的）为P的凸优化问题。并给出问题的界或近似。例如用对偶（Duality），松弛（Relaxation）等方法将一个优化问题转化为凸优化。
什么是凸优化？
关于凸优化，有几个基础概念：凸集，凸函数，凸优化问题，局部最优和全局最优。以及一个很重要的性质，就是所有局部最优点都是全局最优的
意思是对这个集合的任何两个元素，我们如果画一条线，那么这线上的所有元素仍然属于这个集合：
下面这几个例子都是凸集：
Rn，因为对任意 x, y ∈ Rn, θx + (1 - θ)y ∈ Rn
Rn+ = {x : xi ≥ 0 ?i = 1,…,n}，因为 (θx+(1-θ)y)i =θxi +(1-θ)yi ≥0 ?i。
范数球，∥ · ∥ 例如 {x: ∥x∥ ≤ 1}
映射子空间 Affine subspaces： {x ∈ Rn : Ax = b}
多面体 polyhedra： {x ∈ Rn : Ax ? b}，即 Ax 的每个元素小于或等于 b 的对应元素
凸集的交集
半正定矩阵 Positive semidefinite matrices：A = AT 且 for all x ∈ Rn, xT Ax ≥ 0.
在文献中有详细的证明：
只需要按照凸集的定义，任取这个集合的两个元素，以及
0 ≤ θ ≤ 1，如果可以证明 θx+(1-θ)y 仍然属于这个集合，那么它就是凸集
2. 凸函数：
它的含义就是在这个函数上任意取两个点，在它们之间画一条线，那么这两点之间的函数上的值需要在这条线以下。：
如何验证某个函数是否为凸函数呢？
最基本的，我们可以用凸度的一阶二阶条件：
一阶条件的含义就是，如果我们在这个函数上的任意一点画出它的切线，那么这条切线上的所有点都将在函数的下面。：
二阶条件中如果是一维的话，就相当于函数的二阶导数总是非负的。：
? 此处意思为半正定。
下面这几个例子都是凸函数
可以根据二阶条件，即证明它们的二阶导数非负来判断：
Exponential. Letf :R→R,f(x)=e^ax for any a ∈ R.
Negative logarithm. Let f : R → R, f(x) = -logx {x : x & 0}，
Affinefunctions. Letf:Rn →R,f(x)=bT x + c for some b ∈ Rn,c ∈ R
当然还有下面两个可以直接通过凸函数的定义和不等式来证明：
Norms. Let f : Rn → R be some norm on Rn
Nonnegative weighted sums of convex functions
3. 凸优化问题：
就是我们想要找到凸集 C 中的某个 x 来使 f 达到极小：
minimize f (x)
subject to x ∈ C
其中 f 为凸函数，C 为凸集，
4. 局部最优和全局最优
局部最优的意思是如果 x 这个点是函数的局部极小值点，那么我们可以找到一个半径 R，在以 x 为中心以 R 为半径的球内的任何一个点，它的函数值都会大于这个极小值。
全局最优就是 x 这点的函数值就是在定义域中函数达到的最小值。
对于凸优化问题，有一个很重要的性质，就是所有局部最优点都是全局最优的。
为什么呢，证明如下：
设 x 为一个局部极小值点，那么我们可以找到另外的一个点 y，使得 f(x) & f(y)
这样的话，我们找到一个 z 为：
那么 z 就在 x 的这个半径 R 内：
但是由凸函数定义可得：
即我们在半径 R 内，找到了一个 z ，它的函数值要比 x 的还要小，这与 x 是局部极小值矛盾，所以 x 不可能是局部极小值，只可以是全局的。
下面这几个例子都是凸优化问题：
Linear Programming
Quadratic Programming
Quadratically Constrained Quadratic Programming
Semidefinite Programming
那么这些有什么用呢？
让我们用常见的算法举例，
1. SVM 的优化目标如下：
如果我们根据下面的形式，定义了 x，P，c，G，h，X，y，
那么 SVM 的优化目标就可以写成 Quadratic Programming 的形式：
所以这是个凸优化问题，
当然了我们可以简单地根据 SVM 具有二次的优化目标，以及线性的限制条件来判断，而无需转化成标准形式。
2. 最小二乘的优化目标：
如果我们做如下定义，可以看出它也是个 Quadratic Programming：
当我们拿到了一个凸的优化函数时，那么就有一大套公式定理可以帮我们解决问题了。
因为对凸优化的问题，在基础数学上面已经有了很多解决方法，例如可以将凸优化问题Lagerange做对偶化，然后用Newton、梯度下降算法求解等等。
推荐凸优化入门资源：
book Convex Optimization by Stephen Boyd and Lieven Vandenberghe (available for free online),
EE364，a class taught here at Stanford by Stephen Boyd
也许可以找到你想要的
我的热门文章凸优化(一)——概述 - 简书
凸优化(一)——概述
〇、说明最近在学习机器学习方面的算法知识，这里尽量以通俗易懂的方式将其整理一下，一方面以备自己查阅，另一方面如果可以方便他人则更好。凸优化主要学习《凸优化》(Stephen Boyd等著，王书宁等译)[1]这本书。学习过程中，对其内容的理解时有困惑，也参考一些其他书籍资料。笔者尽量将这部分知识整理地简洁明了，成此系列笔记。如有错误疏漏，烦请指出。如要转载，请联系笔者，hpf_。一、什么是凸优化不严格的说，凸优化就是在标准优化问题的范畴内，要求目标函数和约束函数是凸函数的一类优化问题。二、重要性
“凸优化在数学规划领域具有非常重要的地位。”
“一旦将一个实际问题表述为凸优化问题，大体上意味着相应问题已经得到彻底解决，这是非凸的优化问题所不具有的性质。”
——《&凸优化&译者序》
凸优化之所以如此重要，是因为：1、其应用非常广泛，机器学习中很多优化问题都要通过凸优化来求解；2、在非凸优化中，凸优化同样起到重要的作用，很多非凸优化问题，可以转化为凸优化问题来解决；3、如上引用所述，凸优化问题可以看作是具有成熟求解方法的问题，而其他优化问题则未必。三、凸优化知识体系凸集，定义目标函数和约束函数的定义域。凸函数，定义优化相关函数的凸性限制。凸优化，中心内容的标准描述。凸优化问题求解，核心内容。相关算法，梯度下降法、牛顿法、内点法等。对偶问题，将一般优化问题转化为凸优化问题的有效手段，求解凸优化问题的有效方法。四、标准优化问题
五、凸优化问题
附录A、参考[1]、《凸优化》，Stephen Boyd等著，王书宁等译B、相关目录凸优化(一)——概述C、时间线
第一次发布 修改文章名，重新整理完善做科研时，曾花了段时间学习凸优化，后来发现ML中其应用也非常普遍，想来今后可能还会接触，干脆做个系统的总结，方便以后查询。
博文内容主要参考Boyd（Stanford）的Convex Optimization，配套的slides，以及部分网络材料，感兴趣的朋友可以一起学习探讨。
凸优化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。虽然条件苛刻，但应用广泛，具有重要价值，主要体现在：
凸优化本身具有很好的性质
一来，凸问题的局部最优解就是全局最优解。二来，凸优化理论中的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”，即目前已有的凸优化方法还不能称之为技术。但还是说那句话，基本上，如果你把一个现实问题建成凸优化问题模型，你就可以认为这个问题已经被解决了。
多说几句，对于非凸优化中，凸优化同样起到很重要的作用：
解决一个非凸优化问题时，可以先试图建立一个简化的多凸优化模型，解出以后作为非凸问题的一个起始点
很多非凸优化问题的启发式算法的基础都是基于凸优化
可以先建立非凸优化的松弛问题，使用凸优化算法求解，然后作为非凸优化问题的上限或下限
那么，下面将分几章花些篇幅好好讲解下凸优化的主要知识点和常用结论。
A set C is convex, if θx+(1-θ)y∈C, for any x,y∈C and θ∈R with 0≤θ≤1.
简言之，凸集即过集合C内任意两点的线段均在集合C内。
2.2 常用凸集
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: 将前述半正定矩阵改为正定阵、负定阵、半负定阵，仍成立)
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、凸优化问题
通常将一个优化问题写成以下标准形式：
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
5.6 常用案例
如果f(x),gi(x)是凸函数，hj(x)是仿射函数，且存在x使gi(x)&0对多有i成立，则存在x*;α*,β*使得x*是原始问题的解，α*,β*是对偶问题的解，且p*=d*=L(x*;α*,β*)。
如果f(x),gi(x)是凸函数，hj(x)是仿射函数，且存在x使gi(x)&0对多有i成立，则“x*是原始问题的解，α*,β*是对偶问题的解”与“x*;α*,β*满足KKT条件”是充要关系。
本文已收录于以下专栏：
相关文章推荐
机器学习是一门多领域交叉学科，包括概率论、统计学、凸分析、特征工程等等。最近跟着七月算法学习了机器学习的知识，干货不少，比看书理解的快一些，分别总结一下。
         这节课主要介绍凸优化的入门知识，程博士推荐阅读Boyd的《凸优化》，最经典的凸优化的书，这本书有600多页，细致讲解了凸优化相关的理论知识，可以作为一门学科来学习。因为硕士阶段...
数学优化入门：梯度下降法、牛顿法、共轭梯度法
点击“百度”或“google”，输入关键词“数学孺子牛”进行搜索，网页会显示他的系列时评文章。简约的文风，犀利的语言，字里行间无不透露出一种甘愿为人民大众呼吁呐喊的孺子牛精神。他就是金山校区数学教授、...
本文转载自美团点评技术团队文章/rerank_solution_offline.html。
［ 更新］我们收到一些用户关于安装失败的反馈，但需要更多的信息进行错误排查。所以，如果您无法正常安装微软拼音2010，请通过下述网页发送邮件给我们，以便我们进行进一步的沟通：http...
,buy pandora beads1. Check the heat administration of the hair straightener – Some hair straightener...
总结和实现代码，费了很大功夫
他的最新文章
讲师：吴岸城
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)为什么凸优化这么重要？ - 知乎2378被浏览88002分享邀请回答61221 条评论分享收藏感谢收起14739 条评论分享收藏感谢收起查看更多回答}