凸优化简单介绍
&&&&生活中很多问题可以用数学方法来解决，这其中有很多就是优化问题，我们需要采用最优决策来节省成本提高效率。现在的机器学习中也需要用到很多数学优化，常用的就是凸优化。要介绍什么是凸优化，先来简单确定下数学优化问题。一个简单的数学优化问题形式上定义如下：其中x是优化变量，f0()是目标方程，fi()是约束方程。经典的优化问题当上诉的数学优化问题满足一些条件的时候，会产生经典的几类优化问题。简单介绍下面几个特定优化问题。线性规划当目标函数和约束函数都成线性的时候，此时的数学的优化问题即为线性优化问题。线性规划的公式表示为：这里c，a1，a2..am都是n维空间中的向量，b1，b2...bm都是实数。线性规划问题一般可用单纯性来求解，同时也有很多规划的求解库。最小二乘问题(least-squares)最小二乘法是非常经典的一种算法，高中就开始学习。它是回归分析，最优控制的基础。将最优化问题识别为最小二乘问题是很直观的;我们只需要验证目标是一个二次函数（然后测试相关二次形式是否为正半定形）。 虽然基本最小二乘问题有一个简单的固定形式，几种标准技术用于增加其在应用中的灵活性。简单的线性回归中常用最小二乘。几种简单的变形比如局部加权线性回归，岭回归等。凸优化”凸优化“ 是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题&线性规划和最小二乘问题都是凸优化问题的一种，凸优化广泛应用于组合问题和数据拟合问题。也是学习机器学习必须掌握的知识。为什么凸优化这么重要 应用广泛虽然现实生活中的绝大多数问题确确实实是非凸的，但是并不妨碍凸优化问题在许多问题上大展身手。往细说，比如线性回归，范数逼近，插值拟合，参数估计以及许多几何问题都可以采用凸优化。往大了说，在通信，机器学习，统计，金融等设计优化、决策的领域，凸优化都是非常有效的手段。拥有很好的性质凸优化的局部最优解就是全局最优解。并且在理论上，如果一个问题能够化成为凸优化问题，那么理论上就可以视为该问题能够找到有效的办法，即该问题可解。因此很多非凸问题比如几何规划，整数规划，通过一定的手段，要么等价为凸问题，要么用凸问题去逼近，拟合。在凸优化理论中最重要的工具就是Lagrange对偶，这为凸优化算法的最优性和有效性提供了保证。非凸问题目前研究不充分凸优化之所以这么重要，从另一个角度说，就是我们没有找到很好地非凸优化的算法，这一部分许多学者正在努力。机器学习中的凸优化 支持向量机(SVM)支持向量机把一个分类问题抽象为一个凸优化问题，然后采用凸优化问题的各种工具(拉格朗日对偶)求解和解释。神经网络深度学习是神经网络的又一次爆发，其中关键是反向传播，本质就是凸优化算法中的梯度下降算法。即使问题极度非凸，梯度下降还是有很好的表现。最后为大家献上福利，我也就不要求关注了。三本书，分享给大家。链接：/s/1gf9OUQZ 密码：c0hf祝大家新年快乐。 &观想厅也更新了二维码，这里感谢我们的设计师同学哈哈，希望喜欢的没关注的动动手指关注下。
& 上一篇：
& 下一篇：
凸优化简单介绍 [相关推荐]
Copyright & , All rights reserved.牛哥网 , 传播文明正能量，做有文艺范的青年喜爱网站。作者：韩龙飞
题外话，来到CMU已经两周了，从刚开始的难以开口到现在可以沟通，从四处借东西蹭吃喝到现在学习做饭健身三不误，渐渐的开始适应了美国气息的生活。总的感觉，在这里无论是国人还是老外，自主性都很强，每天都有为之努力的目标，不知道这是不是跟due或者所谓的压力有关。这学期旁听了三门课，接下来要写的《凸优化》系列学习笔记就是其中之一，另两门是“16720－Computer Vision”和“10715－Advanced Introduction of Machine Learning”。在日后的时间里，我也会把机器学习相关的算法继续补充完整。
整体来说，从听课和做作业的角度来讲，CMU课程的强度之大是公认的，一学期最多修3-4门课就不错了，不像国内的课程，很多硕士一学期会选9-10门课程，然并卵，走形式而已，真正可以学到的知识少之又少。这一现象基本上是国内各大院校的普遍现象，如果想要提高国内科研水平，提高课程质量和效果是必须的。因为，CMU本科生或者硕士生一年课程代码量基本在5万行，而且对于领域相关知识的掌握很充分，相比之下，国内本科生基本不写代码，硕士毕业下来代码量也不会超过2万行，加上上课基本没什么用，所以理论与实践上的差距就体现出来了。当然，开篇废话这么多，无外乎是想把自己感受到的表达出来，生活是需要积极向上的，不能沉醉于平稳和安逸，每来到一个新的环境，总发现自己low到极点，算是学渣了吧，希望离开的时候起码可以称为合格的一员。
好了，废话不多说，开始整理凸优化课程的学习笔记，笔记可能并不会记全所有老师讲述的内容，但会把大部分我认为重要的东西保留下来～～
1. Tibshirani
感谢Ryan Tibshirani老师为这门课开源做出的贡献，希望更多人可以更好的了解凸优化，明白其在机器学习研究领域的重要性。所有课件和视频都可以在上找到。
2. 优化理论
对于优化理论的定义，Ryan教授给出了一副很好理解优化理论是做什么的图，优化理论就是用于求解某个函数的极值，至于极值体现的含义就跟你要解决的问题相关了，与机器学习的“没有天生优越的分类器”的理论类似，优化算法也没有好坏之分，只有适合还是不适合解决某一问题。
3. 凸集和凸锥
仿射集和凸集的概念在一文中做了详细介绍。
凸集为 \(C \subseteq \mathbb{R}^n\)，使得\(x,y \in C \rightarrow tx+(1-t)y \in C\)，其中\(0 \leq t \leq 1\)。具体表现为下图，左边第一个为凸集，第二个则不是凸集。
任何凸集的线性组合仍为凸集，所有凸集的集合为Convex hull。空集、点、线、球体（Norm ball:\(\{x: \parallel x \parallel \leq r\}\)）、超平面（Hyperplane:\(\{x: a^Tx=b\}\)）、半空间（Halfspace:\(\{x: a^Tx \leq b\}\)）、仿射空间（Affine space:\(\{x: Ax=b \}\)）和多面体（Polyhedron\(\{x: Ax \leq b \}\)）均为凸集。
下面证明为什么Norm ball是凸集：
对于Norm ball中的任意两点\(x和y\)，可以根据三角不等式获得：
\(\parallel tx + (1-t)y \parallel leq t \parallel x \parallel + (1-t) \parallel y \parallel \leq tr + (1-t)r \leq r\)
所以，Norm ball中的任意两点\(x和y\)的线性组合仍在集合内，证明Norm ball为凸集。
其中，Ryan还提到一个问题就是关于多面体，集合\(\{x: Ax \leq b, Cx=d\}\)是否仍是Polyhedron？
结果是显然的，仍然是多面体，因为平面\(Cx=d\)可以写成\(Cx \leq d和-Cx \leq -d\)，满足Polyhedron的定义，即\(\{x: Ax \leq b\}\)。
锥（cone）是指\(x \in C \rightarrow tx \in C\)，其中\(t \geq 0\)，而凸锥（convex cone）的定义则是\(x_1,x_2 \in C \rightarrow t_1x_1 + t_2x_2 \in C\)，其中\(t_1,t_2 \geq 0\)，凸锥的实例如下图：
但是，是否可以举一个例子，使得集合\(C\)为锥，但不是凸锥呢？如下图，如果两条直线组成的锥，分别从直线上选两点，则亮点的线性组合不一定在这两条直线上。
对于凸锥，其中两个重要的实例为Norm cone和Normal cone，接下来着重介绍这两个凸锥的概念。
Norm cone是指\(\{(x,t):\parallel x \parallel \leq t\}\)，而second-order cone则是使用2阶范数\(norm \parallel \cdot \parallel_2\)，如果只看定义的话不太好理解Norm cone是什么，下面给出了matlab仿真得到的三维下的Norm Cone实例：
Normal cone是指给定任意集合\(C\)和点\(x \in C\)，\(\mathbb{N}_C(x)=\{g:g^Tx \geq g^Ty\}\)，其中\(y \in C\)。无论集合C是否是凸集，满足该定义的点的集合都是Normal cone，其含义是指Normal cone中的点与集合C内的点\(x\)的内积永远大于集合C内任意点与其点x的内积。具体实例如下图，\(x’\)normal cone是集合C边缘切线向量之间的点的集合：
normal cone的定义将会在subgradient descent算法中应用到。
c. 凸集的性质
凸集有两个重要的性质，这对机器学习的分类问题，或者更进一步说，对SVM等算法理论有着重要的支撑作用。
（1）Separating hyperplane理论：两个不相交的凸集之间必然存在一个分割超平面，使得两个凸集可以分开。即如果\(C和D\)都是非空凸集，且\(C \cap D =\emptyset\)，则必然存在\(a,b\)使得\(C \subseteq \{x:a^T \leq b\}\) 和 \(D \subseteq \{x:a^Tx \geq b\}\)。如下图：
（2）Supporting hyperplane理论：凸集边界上的一点必然存在一个支撑超平面穿过该点，即如果\(C\)都是非空凸集，\(x_0 \in bd(C)\)，那么必然存在一个超平面\(a\)，使得\(C \subseteq \{x:a^Tx \leq a^Tx_0\}\)，如下图：
d. Operations preserving convexity
凸集经过以下几个操作，仍会是凸集：
（1）Intersection： 凸集交集仍然是凸集。
（2）Scaling and translation：如果\(C\)都是凸集，那么对于\(\forall a,b\)，\(aC+b=\{ax+b:x \in C\}\)仍是凸集。
（3）Affine images and preimages：如果\(f(x)=Ax+b\)，\(C和D\)是凸集，那么\(f(C)=\{f(x):x \in C\}\)和\(f^{-1}(D)=\{x:f(x) \in D\}\)仍是凸集。
这里需要注意的是，第二点和第三点的区别在于，第二点仅相对于凸集做了尺度或平移变换，而第三点则是A为矩阵，b为向量，可以对凸集做矩阵变换，这在图像里可以看成是旋转、压缩、或者是降维操作，而不仅仅是简单的平移变换。
a. 凸函数的定义
总体而言，凸函数跟凸集的定义和性质基本一致，凸函数的性质都可以通过凸集来证明。
函数\(f\)为凸函数，如果其满足\(f: \mathbb{R} \rightarrow \mathbb{R}\)，使得函数\(f\)的定义域为凸集，\(dom(f) \subseteq \mathbb{R}^n\)，且\(f(tx+(1-t)y) \leq tf(x)+(1-t)f(y)\),其中\(0 \leq t \leq 1\)。也就是说凸函数上任意两点的连线都在两点区间的函数之上。具体表现为下图：
当然，如果函数\(f\)为凸函数，那么相应的\(－f\)则为凹函数。
如果凸函数满足\(% &![CDATA[ f(tx+(1-t)y) & tf(x)+(1-t)f(y) %]]&\),其中\(% &![CDATA[ 0 & t & 1 %]]&\)，则该函数为严格凸函数（strictly convex）；如果严格凸函数还满足\(\forall m & 0: f- \frac{m}{2} \parallel x \parallel_2^2\)，则该函数为强凸函数（strongly convex），即函数\(f\)至少是像二次函数一样的凸函数。所以，根据定义，强凸函数一定是严格凸函数，严格凸函数一定是凸函数，反之，则不成立。
例如：单变量函数中的指数函数\(e^{ax}\)、仿射函数\(a^Tx+b\)、二次函数\(\frac{1}{2} x^TQx+b^Tx+c\)（其中\(Q \succeq 0\)半正定）、平方误差函数\(\parallel y-Ax \parallel_2^2\)、p-范数函数\(\parallel x \parallel_p= (\sum_{i=1}^n x_i^p)^{1/p}\)、Indicator function和Max function（\(f(x)=max{x_1, \ldots, x_n}\)）均是凸函数，相反，对数函数则为凹函数。其中，Indicator function定义为：
\(\begin{equation} I_C(x)= \begin{cases} 0 \quad x \in C \\ \infty \quad x\notin C \end{cases} \end{equation}\)
b. 凸函数的性质
与凸集类似，凸函数具有以下的性质：
（1）Epigraph characterization：函数\(f\)为凸函数当且仅当，它的epigraph（\(epi(f)=\{(x,t) \in dom(f) \times \mathbb{R}: \, f(x) \leq t\}\)）为凸集。其中，函数的epigraph是指在函数上方的所有点的集合，如下图所示，我们可以绘制图像的曲线并采用该方法来确定一个函数是否属于凸函数：
（2）Convex sublevel sets：如果函数\(f\)为凸函数，那么它的sublevel sets（\(\{x \in dom(f): \, f(x) \leq t\}\)）为凸集，反之，则不成立。如下图，函数值域小于t的下方的定义域区间（XXX位置）为凸集。
（3）First-order characterization：如果函数\(f\)可微，那么当且仅当\(dom(f)\)为凸集，且对于\(\forall x,y \in dom(f)\)，使得\(f(y) \geq f(x)+\nabla f(x)^T(y-x)\)，则函数\(f\)为凸函数。这一点很易于理解，即在函数某点切线上的点的值小于该点在函数上的值，如下：
根据凸函数一阶导的性质，我们可以看出，如果当我们找到某一点使得\(\nabla f(x)=0\)，那么就会使得函数上所有点\(f(y) \geq f(x)\)，即点\(f(x)\)为函数的极小值。这一点，对于接下来将要介绍的优化问题极为重要，阐明我们求解函数极小值的方法。
（4）Second-order characterization：函数\(f\)二阶可微，那么当且仅当\(dom(f)\)为凸集，且对于\(\forall x \in dom(f)\)，使得\(\nabla^2 f(x) \succeq 0\)，则函数\(f\)为凸函数。
（5）Jensen’s inequality：如果函数\(f\)为凸函数，则\(f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)])\)
c. 凸函数变换
与凸集类似，凸函数经过一些变换后仍能为凸函数，例如：
（1）Nonnegative linear combination；
（2）Pointwise maximization：如果\(\forall s \in S, \, f_s\)为凸函数，那么\(f(x)=max_{s \in S} f_s(x)\)仍为凸函数；
（3）Partial minimization：如果\(g(x,y)\)是凸函数，集合C也为凸集，那么\(f(x)=min_{y \in C} \, g(x,y)\)仍为凸集；
（4）Affine composition：如果函数\(f\)为凸函数，那么经过矩阵变换的函数\(g(x)=f(Ax+b)\)也为凸函数。
5. softmax函数
实例：对于softmax函数，作为机器学习中logistic回归的泛化形式，也成为log-sun-exp函数，什么是softmax函数呢？如何证明该函数为凸函数呢？
假设函数\(g(x)=log \sum_{i=1}{k} e^{a_i^Tx+b_i}\)，从表面上可以看出该函数就像估计函数\(max_{i=1,\ldots,k}(a_i^Tx+b_i)\)的最大值，为什么呢？如果\(\forall i, \, a_i^Tx+b_i\)，则会得到k个数值，如果其中某一个数值比较大，那么通过指数运算会放大该数值在求和运算中的比例，导致求和运算的最终结果受到该较大数值的影响，所以再求对数缩小数值，最后求得的结果基本上就类似于找到\(a_i^Tx+b_i\)的最大值。但是与直接求最大值不同，该函数是光滑函数，便于运用优化算法求解，因此称为softmax函数。
接下来证明为什么log-sun-exp函数是凸函数：
首先，利用之前提到的affine composition，我们可以知道如果\(f(x)=log(\sum_{i=1}{n}e^{x_i})\)为凸函数，那么softmax肯定为凸函数；
然后，利用凸函数的二阶微分的性质，计算\(f(x)=log(\sum_{i=1}{n}e^{x_i})\)的一阶微分和二阶微分：
\(\nabla_i f(x)=\frac{e^{x_i}}{\sum_{l=1}^n e^{x_l}}\)
\(\nabla_{ij}^2 f(x)=\frac{e^{x_i}}{\sum_{l=1}^n e^{x_l}}l{i=j}-\frac{e^{x_i}e^{x_j}}{(\sum_{l=1}^n e^{x_l})^2}＝diag(z)-zz^T\)
其中，\(z_i=e^{x_i}/(\sum_{l=1}^n e^{x_l})\)，通过计算我们可以获得\(\nabla^2 f(x)\)为diagonally dominant矩阵，diagonally dominant是指矩阵\(A\)，满足\(A_{ii} \geq \sum_{i \neq j} \mid A_{ij}\mid\)，即矩阵对角线上的元素大于该行非对角线元素之和。
因此，证明该矩阵是半正定p.s.d.的（positive semidefinite）。满足上面介绍的凸函数性质的第四点，因此，该softmax函数为凸函数。
Ryan还提到一个例子，这个例子我就不详细阐述为什么是凸函数，大家可以根据上面讲解的知识来判断下面的函数是否是凸函数：
\(max\{log(\frac{1}{(a^Tx+b)^7)}, \parallel Ax+b \parallel_1^3 \}\)
欢迎加入我爱机器学习QQ14群：
微信扫一扫，关注我爱机器学习公众号
欢迎加入我爱机器学习QQ14群：
最新文章列表
NIPS 2016 — Day 1 Highlights NIPS 2016 — Day 2 Highlights:...
2017年十二月 &(10)
2017年十一月 &(20)
2017年十月 &(31)
2017年九月 &(47)
2017年八月 &(58)
2017年七月 &(60)
2017年六月 &(67)
2017年五月 &(66)
2017年四月 &(65)
2017年三月 &(54)
2017年二月 &(48)
2017年一月 &(54)
2016年十二月 &(62)
2016年十一月 &(97)
2016年十月 &(97)
2016年九月 &(124)
2016年八月 &(83)
2016年七月 &(13)
2016年六月 &(10)
2016年五月 &(7)
2016年四月 &(9)
2016年三月 &(7)
2016年二月 &(2)
2016年一月 &(3)
2015年十二月 &(5)
2015年十一月 &(4)
2015年十月 &(2)
2015年九月 &(2)
2015年八月 &(3)
2015年七月 &(6)
2015年六月 &(8)
2015年五月 &(4)
2015年四月 &(1)
2015年三月 &(3)
2015年二月 &(1)
2015年一月 &(2)
2014年十二月 &(4)
2014年十一月 &(2)
2014年十月 &(3)
2014年九月 &(4)
2014年八月 &(22)
2014年七月 &(40)
2014年六月 &(61)
2014年五月 &(63)
2014年四月 &(187)
2014年三月 &(4798)
2014年二月 &(764)
2014年一月 &(330)
2013年十二月 &(145)
2013年十一月 &(126)
2013年十月 &(216)
2013年九月 &(284)
2013年八月 &(327)
2013年七月 &(275)
2013年六月 &(315)
2013年五月 &(228)
2013年四月 &(175)
2013年三月 &(186)
2013年二月 &(118)
2013年一月 &(210)
2012年十二月 &(221)
2012年十一月 &(155)
2012年十月 &(143)
2012年九月 &(98)
2012年八月 &(99)
2012年七月 &(109)
2012年六月 &(75)
2012年五月 &(88)
2012年四月 &(78)
2012年三月 &(78)
2012年二月 &(50)
2012年一月 &(17)
2011年十二月 &(27)
2011年十一月 &(6)
2011年十月 &(11)
2011年九月 &(13)
2011年八月 &(13)
2011年七月 &(19)
2011年六月 &(18)
2011年五月 &(6)
2011年四月 &(12)
2011年三月 &(15)
2011年二月 &(6)
2011年一月 &(9)
2010年十二月 &(6)
2010年十一月 &(11)
2010年十月 &(5)
2010年九月 &(8)
2010年八月 &(5)
2010年七月 &(12)
2010年六月 &(4)
2010年五月 &(7)
2010年四月 &(6)
2010年三月 &(12)
2010年二月 &(7)
2010年一月 &(2)
2009年十二月 &(5)
2009年十一月 &(16)
2009年十月 &(6)
2009年九月 &(7)
2009年八月 &(7)
2009年七月 &(5)
2009年六月 &(6)
2009年五月 &(6)
2009年四月 &(4)
2009年三月 &(7)
2009年二月 &(6)
2009年一月 &(1)
2008年十二月 &(4)
2008年十一月 &(5)
2008年十月 &(1)
2008年八月 &(1)
2008年七月 &(3)
2008年六月 &(3)
2008年五月 &(3)
2008年三月 &(1)
2007年十二月 &(1)
2007年十月 &(1)
2007年八月 &(4)
2007年七月 &(1)凹函数-学术百科-知网空间
concave function与凸函数相对应的一类函数.设S是线性空间中的凸集....若-f是S上的凸函数，则称f是S上的凹函数.若-f是S上的严格凸函数，则称f是S上的严格凹函数.
与"凹函数"相关的文献前10条
该文给出了多目标拟凹函数 F=( f1,f2 ,…… fn) T 在一个紧凸集上的有效解集的若干性质
目的讨论弱对数凸(凹)函数及其性质。方法采用了分析方法和数学归纳法。结果给出了弱对数凸(凹)函数的几个等价刻画。结论弱对数凸(凹)函数有很好的性质,与凸(凹)函数存在着紧密的关系
本文从凹函数的定义出发研究了凹函数的充要条件,并给出凹函数新的判定法.
从凹函数的定义出发研究了连续函数与凹函数的关系,并给出连续凹函数的几个判定条件。
根据凹函数的定义,首先得到了判断凹函数的一个充要条件,在此基础上得出了一个新的判断凹函数的充分条件。
针对凹函数一种定义上的不足,给出了与严格凹函数定义等价的一个新定义;根据凹函数成立的一个充要条件,得到了一个较弱的判断函数凹凸性的充分条件。
在大学数学学习中,凹函数是比较特别的一类.在数学分析、概率等课程中的一些不等式的证明问题,利用凹函数的等价条件可以很简洁、巧妙地得以证明.利用凹函数证明不等式的关键是构造出能够解
研究一类凹函数全局优化问题的求解方法.建立凹函数全局优化问题和相对应的最优控制问题之间的等价关系.利用Krotov沿拓法,构造辅助函数,解决了与原问题等价的的最优控制问题,并对目
在数学规划的对偶理论中,函数及其共轭函数在解决某些实际问题时发挥着重要的作用,利用二者的关系,我们可以把涉及某一函数的问题转化为与其共轭函数有关的对偶问题加以解决.有关凸函数及其
以凹函数为对象,以特殊的仿射函数为态射,建立了范畴CONF,指出凸集和凸模糊集为范畴CONF中的对象,证明了范畴CONF有FiniteProducts和Equalizers性质.
"凹函数"的相关词
快捷付款方式
订购知网充值卡
<font color="#0-819-9993
<font color="#0-
<font color="#0-凸集证明_中华文本库
非常遗憾！在本库中没有找到与&"凸集证明"&相关的文本}