凸优化，对偶问题与拉格朗日函数

优化问题的基本形式

 

 

 

 

 

 

最大值问题可转化为最小值问题 

 

优化问题的域

　　　　　

可行域&＃xff1a;所有可行点的集合

最优化值&＃xff1a;

最优化解&＃xff1a;

 

凸优化问题的基本形式

其中&＃xff0c;约束函数f(x)是凸函数&＃xff0c;h(x)为仿射函数

 仿射函数&＃xff1a;即最高次数为1的多项式函数。常数项为零的仿射函数称为线性函数。

 凸优化问题的重要性质&＃xff1a;

　　1.凸优化问题的可行域为凸集

　　2.凸优化问题的局部最优解即为全局最优解

 

对偶问题

 一般优化问题的拉格朗日乘子法

　　　　

拉格朗日函数

　　　　

对固定的x&＃xff0c;拉格朗日函数是关于和的仿射函数&＃xff0c;当x为定值时&＃xff0c;f(x)为定值&＃xff0c;h(x)为定值&＃xff0c;函数关于 线性&＃xff0c;关于线性&＃xff0c;即为若干条直线。

拉格朗日对偶函数

　　　　

若问题没有明确的下确界&＃xff0c;则g(lamta,V) 为负无穷

 　　　　

根据定义&＃xff0c;显然有&＃xff1a;对于任意的lamda&＃xff0c;任意的x&＃xff0c;若优化问题有最优值p&＃xff0c;则g(lamta,V) <&＃61;p

进一步&＃xff0c;拉格朗日对偶函数为凹函数

 

分析

公式纯手打QAQ&＃xff01;

对偶

 

 

 

强对偶条件

若要对偶函数的最大值等于原问题的最小值&＃xff0c;则需满足&＃xff1a;

KKT条件

 

 实践案例

可以参见SVM的求解过程&＃xff01;