在机器学习中，很多情况下我们想要优化一个函数。举个例子：给定一个函数 f：Rn−>Rf：Rn−>R，我们要找到一个x∈Rnx∈Rn使得f(x)f(x)取得最大值/最小值。

通常来说，找到一个全局最优解是困难的。但是，对于凸优化问题，局部最优解便是全局最优解。

凸集

在进行凸优化之前，首先我们要知道什么是凸集。

定义：如果集合C是一个凸集，那么对于∀x,y∈C，θ∈R(θ≤θ≤1)，总有

θx+(1−θ)y∈C

几何含义：如果我们对于C中任意两个元素进行连接形成一条直线，那么直线上的任意一个点都在C中，我们称之为凸集。

例如上图，左侧是凸集，右侧是非凸集。

凸函数

定义：对于一个函数f:Rn−>R，它的定义域是一个凸集D(f)，且对于∀x,y∈D(f)，0≤θ≤1， 有 

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)

几何含义：我们在凸函数的图上任取两个点连成一条直线，在这条直线的范围内，凹函数图上的值小于这个直线上的值。

注意：同济高等数学上凸函数，凹函数的定义和国外凹凸函数的定义是相反的。

凸函数的一阶充要条件： 

其中要求f可微

凸函数的二阶充要条件： 

其中要求f的二阶可微。

凸优化问题

我们已经知道啦什么是凸函数、凸集，现在可以考虑凸优化问题。通常一个凸优化问题的形式是： 

st为subject_to缩写。其中ff是一个凸函数，C是一个凸集，x是需要优化的变量。然而，上面的式子表达不够清楚，我们通常写成下面的： 

其中ff是一个凸函数，gi是凸函数，hi是仿射函数，x是需要优化的变量。

对于凸优化问题来说，局部最优解就是全局最优解。

常见的凸优化问题

1. 线性规划（Linear Programming） 
   如果目标函数ff和约束gg都是仿射函数，那这种凸优化问题被称为线性规划问题。 
   

   

   
   其中x∈Rnx∈Rn是需要优化的变量，c∈Rn,d∈R,G∈Rm∗n,h∈Rm,A∈Rp∗n,b∈Rp

2. 二次规划（QP） 
   如果目标函数ff是凸二次函数，约束g是不等式的形式，那么这种凸优化问题被称为二次规划问题。 
   

   

   其中x∈Rnx∈Rn是需要优化的变量，c∈Rn,d∈R,G∈Rm∗n,h∈Rm,A∈Rp∗n,b∈Rp,p∈Sn+

   
   

3. 二次约束的二次规划（QCQP） 
   如果目标函数ff和gg都是凸二次函数，那么这种凸优化问题被称为二次约束的二次规划问题。 
   

   

   
   其中x∈Rn是需要优化的变量，c∈Rn,d∈R,G∈Rm∗n,A∈Rp∗n,b∈Rp,p∈Sn+,Q∈Sni