COAC：Introduction

凸集和凸函数的定义：

凸集：

• 数学定义：集合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个充要条件或者定义去证明。

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

研究的问题：

输入是凸集X，然后有一个凸函数f，然后我们求F在定义域X中最大或者最小的值。用数学表达式来描述这个问题就是：

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

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

  其中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不是闭集合，那么上面的结果就退化成如下： 这个很容易推导到下面支持超平面定理。

其它角度来理解:直观的理解这个定理：就是对于闭凸集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，使得：

直观解释：X是凸集，那么存在一个超平面，使得X边界上的某点x0到这个平面的距离比所有X的其他元素来的小。

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

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

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

你可以这么来推，首先我们将代表任意点的y的值f(y)移动至不等式的左边可以得到;f(y)>=g^T(y-x)+f(x),其中g^T(y-x)+f(x)是横坐标为y切线函数的上面的点（（梯度x(目标横坐标-当前横坐标)+当前横坐标的值）就是目标横坐标在切线上面的值），f(y)是原来函数上面的点，所以根据定义是大于等于。所以子梯度有一个性质，函数f都会在切线直线g^T(y-x)+f(x)上方。另外，f函数的子梯度可能不止是一个数，而是存在一个集合，我们把这个集合记作： 为什么要引出次梯度：是因为有一些凸函数是不可导的，没法用梯度，所以subgradient就在这里使用了。注意到，子梯度也是求解凸函数的，只是凸函数不是处处可导。
次梯度的命题：
1.如果x’属于X（x在函数f的自定义中），并且g是f的子梯度集合，那么f的值会一直在函数f(x‘)+g^T(x-x’) 上面。如下面图所示：直线f(x‘)+g^T(x-x’) 必过点(x',f(x')),且若f(x)可导，那么该直线就是f(x)在x‘点的切线。

可以看出图像f(x)都在直线f(x')+g(x-x')上面，当点不可导时，其g的值不只一个。在下图中就是竖直直线形式存在。
2.次梯度存在性命题： 凸函数总会存在子梯度（在COAC上有证明过程，主题思路是应用支持超平面定理）并且如果这个凸函数可导，那么导数一定存在于次梯度中。
条件： 如果让X含于Rⁿ是凸集合，并且f:X到R的映射函数。对于任意的x属于X，其次梯度集合都不为空。
结果： 函数f(x)是凸函数。可以从集合上面理解，如果每一点都存在次梯度g，那么这一函数f(x)必然位于f(x')+g*(x-x')上面。如果是凹函数就不满足这个条件了。
相反的:
条件： f(x) 是凸函数
结果： 对于任意x属于int(X),则其次梯度g非空。更进一步的，如果f(x)是凸的并且是可导的
3.次梯度的由来: 如果f是凸函数那么次梯度的由来可以用一阶泰勒公式来得到（图片少了右括号）：

4.次梯度的使用:
1)常见的max函数：就是用在max函数中，在很多函数由于是分段函数导致在分段点左右导数不同即不存在导数，但是存在次梯度，所以可以用次梯度来求： 即所有该点函数值等于最大值的函数的梯度的凸包。 其中co就是凸包的意思。
2)次梯度一般使用流程：其实次梯度的一般使用流程和普通的的梯度下降使用的流程是相同的，只不过梯度选取是次梯度集合中任意一个就行。这个时候要注意了：次梯度下降是非单调收敛：−g^t不需要是下降方向，在这种情况下，不能使用线性搜索选择合适的α^t即学习率。
3)在非约束最优化问题中，要求解一个凸函数f:Rⁿ映射到R的最小值问题： 如果f(x)可导我们一般求解其导数为0，求解x^*,但是在函数f不可导的时候我们可以求的是次梯度中为0的值来获得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^*是最小值，这个也很好理解，因为这个式子表明，对于其他任意y值对比与切点x^*而言，切线的增量都是大于等于0的，所以可以看到这个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