凸集和凸函数的定义：

凸集：

• 数学定义：集合X 属于R^n(即其中的元素x有n维，每维都在R实数空间)如果X是凸集，那么它就要包含所有它本身任意两点间的片段。
  

  
  其中
  就代表了空间上点经过x到点y之间直线上面的任意点，如果λ在[0,1]之间，那么就是只代表x到y之间的线段，当λ从0-->1就是从x点到y点变化。
  同理，函数f(*)上的的两点之间的弦的定义就可以是为：（1-λ）*f(x)+λ*f(y)

• 几何解释：集合任意两点之间的线段都在集合内部，这样的集合就是凸集

• 其他概念:
  闭凸集： 又叫封闭凸集，闭合凸集。是包含其所有极限点的凸集。
  有界+闭：数学分析中讲到：R中闭区间[a,b]上连续函数具有一些好的性质，比如有界、能取到最值、介值定理、连续等价于一致连续等。先推广到n维欧氏空间Rⁿ也要具有那些好的性质，有界、最值可达、连续就一致连续等，需要把原来的闭区间[a,b]换成“有界+闭”集，就也可以保证。引自知乎 [2]
  集合的边界定义（用符号bd表示）： 以下引自博客[3],如果我们考虑R2中的单位圆，那么其边界显然就是圆。但是对于更加复杂的情况，例如有理数，它的边界是什么在直观上就不明显，因此我们需要精确的定义：原始的定义是指bd(A)是A与Rn∖A之间的边界。具体数学定义为下面的定义6：

  其中cl的意思是：闭合封闭的意思，close的缩写（有待考证）,这个式子的直观解释就是指(封闭集合A的边界)是指(封闭集合A)和(封闭集合Rⁿ去掉A集合)的交集。
  "平面"的公式：
  二维：Ax+By+Cz+D=0 (二维平面的公式) ，平面的法向量n 就是(A,B,C)，点(x0,y0,z0)到平面的公式：
  点到平面距离另一种形式就是平面上面的点P到Q的向量PQ点乘向量n并除以法向量的模：(PQ * n)/|n|。（其中，我们求P点到 法向量n且经过Q点的平面的距离，*代表点乘）
  多维： W₁x₁+W₂x₂+W₃x₃...+W_mx_m+C. 同理点到这个高维面的距离为：(向量PQ*法向量w)/|w|
  点与“平面“的相对位置: 当w^Tx0 +C >0 说明点x0在”平面“上方，相反的X0 在”平面“下方。

凸函数：

• 数学定义：X是属于Rⁿ的凸集，有一个函数 f:X-->R 是凸函数，那么函数值一直会位于其弦的下面(注意R是一维的)。

• 凸函数充要条件：
  一阶重要条件（1st-order condition）：

  其中要求f一阶可微，这个很好理解：就是凸函数任意一点(x0,f(x0))处的切平面，永远在f(x)下方,用抛物线x²函数来想就非常好理解了。
  二阶充要条件(2nd-order condition）：
  其中要求f二阶可微，表示二阶导数需大于0才是凸函数，这里x是多维的，那么这里应该是hessian矩阵是半正定矩阵。具体如何理解可以参考知乎：https://www.zhihu.com/question/40181086?sort=created
  可微补充，引自[5]：多元函数这些性质之间的关系是：可微分是最强 的性质，即可微必然可以推出偏导数存在，必然可以推出连续。反之偏导数存在与连续之间是不能相互推出的（没有直接关系），即连续多元函数偏导数可以不存在；偏导数都存在多元函数也可以不连续。偏导数连续强于函数可微分，是可微分的充分不必要条件。
  另外：可微分可以直观地理解为用线性函数逼近函数时的情况(一元函数用一次函数即切线替代函数增量，二元函数可以看做是用平面来代替，更多元可以看做是超平面来的代替函数增量，当点P距离定点P0的距离p趋于零时，函数增量与线性函数增量的差是自变量与定点差的高阶无穷小(函数增量差距缩小的速度快与自变量P靠近P0的速度))。
  引出扩展：Jacobian矩阵和Hessian矩阵：
  定义：
  Jacobian：
  雅可比矩阵类似于单变数函数的导数。 假设F:Rⁿ到R^m一个从n维欧氏空间映射到到m维欧氏空间的函数。这个函数由m个实函数组成：y1(x1,x2,x3,...xn),y2(x1,x2,x3,...xn).这些函数的偏导数(如果存在)可以组成一个m行n列的矩阵，这个矩阵就是所谓的雅可比矩阵：
  
  Hessian：
  其他：详细可参见这个博客http://jacoxu.com/jacobian%E7%9F%A9%E9%98%B5%E5%92%8Chessian%E7%9F%A9%E9%98%B5/ 这个人觉得博主写很清楚。

• 常见的凸函数有：
  指数函数族；
  非负对数函数；
  仿射函数；
  二次函数；
  常见的范数函数；

• 保凸运算：
  非负加权求和、复合仿射映射、逐点最大和逐点上确界、复合等。
  这些可以采用上面2个充要条件或者定义去证明。

熟记常见的凸函数和保凸运算，有助于后期自己建模模型！！（有空整理下，然后关键是非凸函数如何有效的求解建模）

研究的问题：

几个凸优化在机器学习领域典型的例子

• 一般机器学习公式都会遵循如下格式：

  其中f₁,f₂,f₃,....f_m,R是凸函数，并且λ>=0是固定的参数。一种解释是：f_i(x) 是样本数据集第i种cost。R(x)是正则项。所以我们机器学习很多问题，就是要将问题进行凸优化建模获得f_i(x)。 注意这里面的x是我们要学习的权值.那么现在我们有一堆数据他们的格式是(w_i,y_i),一般w代表特征，y代表标签。

• 分类问题：
  1.Y = {1，-1} f_i(x)=max(0,1-y_ix^Tw_i) 这个也被叫做hinge-loss。如果R(x) = ||x||² 那么就是SVM算法了。
  2.分类的另一种表示为：f_i(x)=log(1+exp(-y_ix^Tw_i)) 这个也被叫做the logistic loss，如果R(x) = ||x||² 那么我们就可以得到logistic regression的问题了。

• 回归问题：
  其中一种回归问题是指：Y=R,f_i(x)=(x^Tw_i-y_i)²，令R(x)=0,这个就是vanilla least-squares problem，可以被重新写为：

  其中W是mxn的样本矩阵，其中m是样本个数，n是特征的个数。Y=(y₁,....y_n)^T
  如果R(x) = ||x||² 那么就是 ridge regression
  如果R(x) = ||x||₁ 那么就是 LASSO

• 稀疏逆协方差估计：
  

  其中X是矩阵，Y是经验协方差矩阵
  ?问题：稀疏逆协方差什么问题？

• 矩阵填充：
  这一类问题是我们可以观察到未知矩阵Y的部分元素，我们的任务是利用观察到的元素去推测填补Y中未知的元素。一个(凸)矩阵（什么是凸矩阵）填充问题可以被表示成下面的数学公式：
  

  ?问题：为什么矩阵填充可以表示这样的数学形式？

“凸”的基本属性的介绍

1.分离定律（Separation Theorem）

条件：让X含于Rⁿ作为一个闭合凸集集合（closed convex），并且x₀属于Rⁿ\X(“\”的意思是除去)
结果：存在w 属于Rⁿ and t 属于R 使得:

其它角度来理解:直观的理解这个定理：就是对于闭凸集X，在集合外存在一个平面W，和点x0，和值t，使得点x0到平面W的距离小于等于t,同时集合内任意一点到这个平面的距离大于等于t。如果X不是闭凸集合只是凸集合的时候只能说X集合外存在平面W和外一个点x0，使得集合内部的点到这个平面w的距离都大于x0平面w的距离。

2.支持超平面定理（Supporting Hyperplane Theorem）

条件：让X含于Rⁿ是一个凸集，并且x0属于X的边界。
结果：存在w属于Rⁿ,w不等于0，使得：

其实在上面用数学公式都是不等式符号，然后你可以两边同时除以W的模那么就可以变成距离公式，就可以用几何的角度来理解了。

次梯度(Subgradients)(关键概念)[3]

定义： 让X含于Rⁿ,并且 f是X到R（只是一维）的映射。然后如果g属于Rⁿ是f在点x的次梯度。那么就有x属于X，有任意y点属于X，满足如下不等式：

为什么研究凸函数

在继续下面一个话题之前，我们先进行回答一个重要问题，为什么我们要研究凸函数，很显然一个重要原因就是凸函数拥有很有优良的性质，其中最主要的就是：可以很方便的从局部特性拓展到全局的特性。这个体现在了两个方面：一个是：之前的导数，只能体现一个在x周围的局部的特性，可能切线会和函数相交，但是现在次梯度可以体现全局的最下界。另一个是：凸函数中局部的最小值就是全局的最小值。
命题1.2:若函数f是凸函数，那么如果x是f的局部最小值，那么x就是f的全局最小值，并且当且仅当次梯度g集合中有0值。
命题1.3:(一阶最优性条件(First order optimality condition))
条件：1）f是凸函数，2）X是闭合凸集且在此定义域上f是可微的（differentiable）
结论：然后为了求函数f(x)的最小值x^*：

黑箱模型：

黑箱模型的定义是假设我们有无限的计算资源，然后有一个集合X是已知的，但是目标函数f:X到R是未知的（故称为黑箱），但是可以根据数据库进行查询来回答以下两个问题：
1)输入一个点x属于集合X，输出f关于x的值f(x)
2)输入一个点x属于集合X,输出f(x)在点x的次梯度
目标一般也是求f(x)的最小值。在这种条件下，我们感兴趣与在于：对凸函数进行优化求解的时候需要利用数据库的复杂度。即需要查询多少次数据库，才能达到lamda近似极值。并且要去计算他的复杂度上界。
另外的黑箱模型问题，也并不知道集合X，想对应的他需要加入数据库的另外一种询问方式：
3）输入x，来返回是否x属于X
黑箱模型的优点：近几年，黑箱模型很流行，主要的原因有一下两点：
1.数据库的询问方式，不被数据的维度做束缚，所以黑箱模型可以优化非常高维度的优化问题。
2.很多算法用黑箱模型会对于数据库的输出噪声非常的鲁棒，这个对传统的优化问题，和机器学习的优化问题特别相关，详情在后续章节在继续介绍。

结构优化（Structured optimization）

黑箱优化为什么有提出结构优化：主要原因就是黑箱优化的前提是基于不知道目标函数，但是很多时候我们已经知道了，目标函数的格式，所以如果我们还继续使用黑箱模型的优化方法，那么相当于人工为此类优化问题进行限制。所以基于这个观察，针对目标函数已经知道的优化问题，提出了数学家提出了更有效优化策略，即结构优化。
常见的结构优化的算法：
内点法(the Interior Point Methods),其他还有（FISTA or Mirror Prox）
结构优化对于LPs和SDPs： 结构优化对于(Linear Programs)线性规划问题 and SDPs (Semi-Definite Programs)与半正定规划问题非常有效，也会在后续进行简单的介绍.
线性规划问题定义：线性规划问题,目标函数一般为f(x) = c^Tx, c∈Rⁿ,限制条件X一般也为线性函数即X={x∈Rⁿ,Ax<=b},A的维度是mxn，b的维度是m。
半正定规划问题定义：优化的变量时一个对称的矩阵X∈R^nxn，让Sⁿ是对称矩阵nxn空间。让符号<*,*>代表Frobenius内积，具体为<A,B>=Tr(A^TB).那么半正定问题拥有如下形式：目标函数f(x)=<X,C>,其中C∈R^nxn,并且限制条件为{X∈Sⁿ₊:<X,A_i><=b_i,i∈{1....m}},其中Sⁿ₊表示正定矩阵nxn。A₁,...A_m∈R^nxn 并且b∈R^m,值得一提的是矩阵填充问题是SDP问题一个例子。
Frobenius inner product：定义摘自wiki：

image.png

参考文献：

2. https://www.zhihu.com/question/58904993
3. http://blog.csdn.net/u010182633/article/details/54139896
4. 次梯度(subgradient)相关解释：http://blog.csdn.net/lansatiankongxxc/article/details/46386341
5. 可微的解释（百度知道）https://zhidao.baidu.com/question/554026989474496252.html
6. FISTA
   https://zhuanlan.zhihu.com/p/26645449
   http://blog.csdn.net/huang1024rui/article/details/51534524