凸优化问题简述

学习人工智能，数学是最重要的一部分，本科期间我学习了高数，线代以及概率论还有离散数学，但是在人工智能方面还有一门凸优化未学，故以此做学习记录。

最优化问题
  基本形式
  简述：最优化问题就是一定条件下，求目标函数的最优值
  数学描述：

分类
  最优化问题按照有无约束条件，可以分为有约束和无约束的优化问题，而又约束问题又可以分为含等式约束和不含等式约束的优化问题。不同的优化问题有不同的处理策略：
1，无约束的优化问题：直接求导，使导数为0
2，含等式约束的优化问题：主要通过拉格朗日乘数法将含等式约束的优化问题转化为无约束优化问题
3，含不等式约束优化问题：主要通过KKT条件将其转化为无约束优化问题
  方法：
    无约束：1，梯度下降法 2，Powell法 3，牛顿法 4，单纯形法 5，共轭梯度法 6，坐标变化法
    有约束：1，Monte Carlo法 2，广义简约梯度法 3，随即方向搜索法 4，序列线性规划法 5，复合形法 6，序列二次规划法
  在有约束的最优化问题里，还可以根据目标函数的和约束函数是否为凸函数分为凸优化问题和非凸优化问题。

线性规划问题
  线性规划问题是凸优化问题中的一种
  线性规划问题的标准形式
    如果目标函数和约束函数都是线性函数，则称该类优化问题为线性规划问题
    其一般形式为：

  而线性规划问题的标准形式则需要满足下面的条件
    1，目标函数为最大值，即max z= c1x1+c2x2+...+cnxn
    2,约束条件为等式，即

    3，约束条件右端项非负，即bi>=0,i=1,2,...,m。
    4，决策变量非负，即x1,x2,...,>=0。   线性规划的标准形式，也可以用矩阵来表示：

  线性规划问题的求解
    求解线性规划问题就是从满足约束条件的方程组中找出一个解，使目标函数达到最大值。主要方法有：1，图解法 2，单纯形法 3，计算机软件求解
    图解法：
      主要使用于二维的或者三维的线性规划问题，在高中我们便已经接触过该类问题，它的基本步骤为：
        1，建立直角坐标系
        2，确定可行域（约束条件所构成的区域）
        3，图示目标函数
        4，最优解的确定（可行域中是目标函数值达到最优的点）
    比如，我们要求解下面这个最优化问题：

凸集和凸函数
  空间里的直线
    假设在pow(R,n)内存在两个不同的点x1和x2，那么穿越两点的直线可以用下式来表示：
           y=θx1+(1-θ)x2 θ∈R
    如果觉得式子太抽象了无法理解，可以结合下图(y轴未画出，想象y轴由x1，x2决定后在空间中的位置)便于理解

    如果在指定原点和θ的情况下，y就表示通过x1和x2这两点的直线上的某一点。
  仿射集
     定义：
      对于任意的x1，x2∈C以及θ∈R，有θx1+(1-θ)x2∈C，那么集合C就是仿射集
  凸集
    凸集和仿射集的定义很类似：
      对于任意的x1，x2∈C且0<=θ<=1,有θx1+(1-θ)x2∈C，那么集合C就是凸集
      换句话说，对于一个集合**C**?pow(**R**,**n**)，如果集合内的任意两点构成的线段仍在集合**C**内，则称集合**C**为凸集。由此可见，仿射集也是凸集。

超平面和半空间
   我们知道，二维空间里的直线在数学上，是以下线性方程
           ax+by=d
的所有解(x,y)在空间里形成的集合。
  三维空间里的平面，则是以下线性方程
          ax+by+cz=d
的所有解(x,y,z)在空间里形成的集合。

   超平面为空间中的平面在n维空间里的推广，表示为            **a**1**x**1+...+**a**n**x**n=**d**   将**x**和**α**写成向量的形式，就可以得到超平面**H**的向量表达式   因为向量**α**与平面正交。超平面既是仿射集也是凸集   半空间任意点的线段在半空间内，而任意连线的直线不在半空间内，半空间是凸集，但不是仿射集。

凸函数
  定义：
     函数f：pow(R,n)->R的定义域domf是凸集，并且任意x,y∈domf和任意θ 0<=θ<=1有
            f(θx+(1-θ)y)<=θf(x)+(1-θ)f(y)
     则称函数f是凸的
  凸函数可以理解为割线总在函数上方的函数。

凸优化问题
   定义：

  上述优化问题中，如果fi(x)是凸函数，hj(x)为仿射函数的优化问题成为凸优化问题。   凸优化问题的重要性质   1，凸优化问题的可行域为凸集   2，凸优化问题中局部最优解同时也是全局最优解。   凸优化之所以如此重要，是因为：     1，应用非常广泛，机器学习中很多优化问题都要通过凸优化来求解；     2，很多非凸优化问题，可以转化为凸优化问题来解决；      3，凸优化问题目前具有成熟求解问题，而其他优化问题则未必；