凸二次規劃(convex quadratic programming)問題

文章目錄

• 1、凸函數
• 2、仿射函數
• 3、凸優化問題
• 4、凸二次規劃問題

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)=w1​x1​+w2​x2​+..+wn​xn​+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是仿射函數

常用的二次規劃問題求解方法有：

橢球法

内點法

增廣拉格朗日法

梯度投影法