凸优化的基础

1. 凸优化的基本形式

$min \ \ \ f_0(x), \ \ x\in R^n$

subject to

$f_i(x)\leq 0, \ i=1,...m$

$h_j(x)=0, j=1,....p$

其中:$f_i(x)$是凸函数，$h_j(x)是仿射函数$

• 可行解：满足约束条件的解

• 可行域：所有可行解的集合

• 凸优化问题的可行域是凸集；凸优化问题的局部最优解是全局最优解

2. 拉格朗日乘子法

• 拉格朗日函数

$L(x,\lambda,\nu)=f_0(x)+\sum\limits_{i=1}^{m}\lambda_if_i(x)+\sum\limits_{j=1}^p\nu_jh_j(x)$

固定x，拉格朗日函数是关于$\lambda$和 $\nu$的仿射函数

• 拉格朗日乘子法将约束问题等价于无约束问题

3. 优化问题

* 分类

• 无约束优化
• 约束优化
  • 等式约束优化
  • 不等式约束优化

* 约束优化的算法

• Largrangian法（KKT）
• 罚函数法
• largrangian法和罚函数法的结合(增广乘子法)