凸二次规划(convex quadratic programming)问题 - Cache One

1、凸函数

凸函数: 和高数上不一样,不是看形状,而是看定义
f [ ( x 1 + x 2 ) / 2 ] < = [ f ( x 1 ) + f ( x 2 ) ] / 2 f[(x_1+x_2) /2] <=[f(x_1)+f(x_2)]/2 f[(x1+x2)/2]<=[f(x1)+f(x2)]/2

f(x)=x直线也是凸函数,但不严格

严格凸函数: f [ ( x 1 + x 2 ) / 2 ] < [ f ( x 1 ) + f ( x 2 ) ] / 2 f[(x_1+x_2) /2] < [f(x_1)+f(x_2)]/2 f[(x1+x2)/2]<[f(x1)+f(x2)]/2 ,如 f ( x ) = x 2 f(x)=x^2 f(x)=x2

2、仿射函数

仿射函数:最高次数为1的多项式函数。 f ( X ) = w 1 x 1 + w 2 x 2 + . . + w n x n + b f(X)=w_1x_1+w_2x_2+..+w_nx_n+b f(X)=w1x1+w2x2+..+wnxn+b
仿射函数也是凸函数,只是不是严格凸函数。
常数项为零的仿射函数称为线性函数,线性函数是过原点的仿射函数。

3、凸优化问题

f ( X ) f(X) f(X)为目标函数、 g ( X ) g(X) g(X)为不等式约束、 h ( X ) h(X) h(X)为等式约束。三者在定义域内是连续可微的,且目标函数f和不等式约束函数g是凸函数,等式约束h是仿射函数,则这种约束最优化问题称为凸优化问题。

4、凸二次规划问题

凸二次规划问题是凸优化问题的一个特殊形式,当目标函数是二次型函数且不等式约束函数 g 是仿射函数时,就变成一个凸二次规划问题。

凸二次规划问题的特征:
目标函数f是二次型函数函数。如svm: f ( w ) = w 1 2 + . . + w n 2 f(\textbf{w})=w_1^{2}+..+w_n^{2} f(w)=w12+..+wn2
等式约束h是仿射函数
不等式约g是仿射函数

常用的二次规划问题求解方法有:
椭球法
内点法
增广拉格朗日法
梯度投影法

为您推荐