【OR】二次規劃(2)：SCA方法

導航

• 前文連結
• 線性限制的非凸二次規劃
• SCA方法
• • 算法架構
• 參考資料

前文連結

二次規劃(1)

線性限制的非凸二次規劃

QP問題

min ⁡ 1 2 x T Q x + c T x s . t . { a i T − b i ≤ 0 , i = 1 , … , m a i x − b i = 0 , i = m + 1 … , m + l \begin{aligned} &\min \frac{1}{2}x^TQx+c^Tx\\ &s.t. \begin{cases} a_i^T-b_i\leq 0, i=1,\dots, m\\ a_i^x-b_i=0, i=m+1\dots, m+l \end{cases} \end{aligned} ​min21​xTQx+cTxs.t.{aiT​−bi​≤0,i=1,…,maix​−bi​=0,i=m+1…,m+l​​

其中 Q Q Q不定

SCA方法

構造凸近似問題

Q = P − N Q=P-N Q=P−N，其中 P P P和 N N N為半正定矩陣

Q = H T ( λ 1 ⋱ λ n ) ⏟ Q H = H T ( λ 1 ⋱ λ k 0 ) H ⏟ P − H T ( 0 ⋱ 0 − λ k + 1 ⋱ ) ⏟ N H Q=H^T \underbrace{ \left( \begin{matrix} &\lambda_1\\ &&\ddots\\ &&&\lambda_n \end{matrix} \right)}_{Q}H=H^T \underbrace{ \left( \begin{matrix} &\lambda_1\\ &&\ddots\\ &&&\lambda_k\\ &&&&0 \end{matrix} \right)H}_P- H^T \underbrace{ \left( \begin{matrix} &0\\ &&\ddots\\ &&&0\\ &&&&-\lambda_{k+1}\\ &&&&&\ddots\\ \end{matrix} \right)}_{N} H Q=HTQ

⎝⎛​​λ1​​⋱​λn​​⎠⎞​​​H=HTP

⎝⎜⎜⎛​​λ1​​⋱​λk​​0​⎠⎟⎟⎞​H​​−HTN

⎝⎜⎜⎜⎜⎛​​0​⋱​0​−λk+1​​⋱​⎠⎟⎟⎟⎟⎞​​​H

可以得到

f ( x ) = 1 2 x T Q x + c T x = 1 2 x T P x + c T x − 1 2 x T N x \begin{aligned} f(x)&=\frac{1}{2}x^TQx+c^Tx\\ &=\frac{1}{2}x^TPx+c^Tx-\frac{1}{2}x^TNx \end{aligned} f(x)​=21​xTQx+cTx=21​xTPx+cTx−21​xTNx​

記 f 1 ( x ) = 1 2 x T P x + c T x ， f 2 ( x ) = 1 2 x T N x f_1(x)=\frac{1}{2}x^TPx+c^Tx，f_2(x)=\frac{1}{2}x^TNx f1​(x)=21​xTPx+cTx，f2​(x)=21​xTNx，任取 x ˉ ∈ S \bar{x}\in S xˉ∈S, 構造 x ˉ \bar{x} xˉ處的線性函數對 f 2 ( x ) f_2(x) f2​(x)近似

記一階Taylor展開

l ( x ) = − f 2 ( x ˉ ) − ∇ f 2 ( x ) T ( x − x ˉ ) = − 1 2 x ˉ T N x ˉ − ( N x ˉ ) T ( x − x ˉ ) = 1 2 x ˉ T N x ˉ − x ˉ T N x ≥ f 2 ( x ) \begin{aligned} l(x)&=-f_2(\bar{x})-\nabla f_2(x)^T(x-\bar{x})\\ &=-\frac{1}{2}\bar{x}^TN\bar{x}-(N\bar{x})^T(x-\bar{x})\\ &=\frac{1}{2}\bar{x}^TN\bar{x}-\bar{x}^TNx\\ &\geq f_2(x) \end{aligned} l(x)​=−f2​(xˉ)−∇f2​(x)T(x−xˉ)=−21​xˉTNxˉ−(Nxˉ)T(x−xˉ)=21​xˉTNxˉ−xˉTNx≥f2​(x)​

得到 x ˉ \bar{x} xˉ處的凸近似問題QP( x ˉ \bar{x} xˉ)

min ⁡ f 1 ( x ) + l ( x ) = 1 2 x T P x + c T x − x ˉ T N x + 1 2 x ˉ T N x ˉ s . t . { a i T x − b i ≤ 0 , i = 1 , … , m a i T x − b i = 0 , i = m + 1 , … , m + l \begin{aligned} &\min f_1(x)+l(x)=\frac{1}{2}x^TPx+c^Tx-\bar{x}^TNx+\frac{1}{2}\bar{x}^TN\bar{x}\\ &s.t. \begin{cases} a_i^Tx-b_i\leq 0, i=1, \dots, m\\ a_i^Tx-b_i=0, i=m+1,\dots, m+l \end{cases} \end{aligned} ​minf1​(x)+l(x)=21​xTPx+cTx−xˉTNx+21​xˉTNxˉs.t.{aiT​x−bi​≤0,i=1,…,maiT​x−bi​=0,i=m+1,…,m+l​​

引理：如果 x ˉ \bar{x} xˉ是QP( x ˉ \bar{x} xˉ)的最優解，則 x ˉ \bar{x} xˉ是QP問題的KKT點.

證明：由于 x ˉ \bar{x} xˉ是QP( x ˉ \bar{x} xˉ)的最優解，則 x ˉ \bar{x} xˉ滿足KKT條件

{ P x ˉ + c − N x ˉ + ∑ i = 1 m + l λ i a i = 0 λ i ≥ 0 , i = 1 … , m λ i ( a i T x ˉ − b i ) = 0 , i = 1 , … , m \left\{ \begin{aligned} &P\bar{x}+c-N\bar{x}+\sum_{i=1}^{m+l}\lambda_ia_i=0\\ &\lambda_i\geq 0, i=1\dots, m\\ &\lambda_i(a_i^T\bar{x}-b_i)=0, i=1,\dots, m \end{aligned} \right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​Pxˉ+c−Nxˉ+i=1∑m+l​λi​ai​=0λi​≥0,i=1…,mλi​(aiT​xˉ−bi​)=0,i=1,…,m​

即QP問題的KKT條件，是以 x ˉ \bar{x} xˉ是QP的KKT點.

算法架構

step 0: 取 x 0 ∈ S , ε > 0 , k = 0 x^0\in S, \varepsilon>0, k=0 x0∈S,ε>0,k=0.

step 1: 求解近似子問題，QP( x k x^k xk)

min ⁡ 1 2 x T P x + c T x − ( x k ) N x + 1 2 ( x k ) N x k \min \frac{1}{2}x^TPx+c^Tx-(x^k)Nx+\frac{1}{2}(x^k)Nx^k min21​xTPx+cTx−(xk)Nx+21​(xk)Nxk

得到最優解 x k + 1 x^{k+1} xk+1;

step 2: 如果 ∥ x k + 1 − x k ∥ ≤ ε \lVert x^{k+1}-x^k\rVert\leq \varepsilon ∥xk+1−xk∥≤ε終止

step 3: k=k+1，轉step 1.

性質 1：

x k → Q P ( x k ) x k + 1 f ( x k + 1 ) = f 1 ( x k + 1 ) − f 2 ( x k + 1 ) ≤ f 1 ( x k + 1 ) + l ( x k + 1 ) ≤ f 1 ( x k ) + l ( x k ) = f ( x k ) \begin{aligned} &x^k\xrightarrow{QP(x^k)}x^{k+1}\\ &f(x^{k+1})=f_1(x^{k+1})-f_2(x^{k+1})\leq f_1(x^{k+1})+l(x^{k+1})\leq f_1(x^k)+l(x^k)=f(x^k) \end{aligned} ​xkQP(xk)

​xk+1f(xk+1)=f1​(xk+1)−f2​(xk+1)≤f1​(xk+1)+l(xk+1)≤f1​(xk)+l(xk)=f(xk)​

性質 2（收斂性）：

1.如果SCA有限步終止，則 x k x^k xk為QP問題的KKT點

2.如果QP ( x k ) (x^k) (xk)的最優解為 x k + 1 x^{k+1} xk+1，乘子為 λ k \lambda^k λk，設 { λ k } \{\lambda^k\} {λk}有界，則 { x k } \{x^k\} {xk}的任意聚點為QP的KKT點

證明：

由于 x k + 1 x^{k+1} xk+1是QP( x k x^k xk)的最優解，則滿足KKT條件：

P x k + 1 + c − N x k + ∑ i = 1 m + l λ i a i = 0 λ i k ≥ 0 , i = 1 , … , m λ i k ( a i T x k + 1 − b i ) = 0 , i = 1 , … , m \begin{aligned} &Px^{k+1}+c-Nx^{k}+\sum_{i=1}^{m+l}\lambda_ia_i=0\\ &\lambda_i^k\geq 0, i=1, \dots, m\\ &\lambda_i^k(a_i^Tx^{k+1}-b_i)=0, i=1, \dots, m \end{aligned} ​Pxk+1+c−Nxk+i=1∑m+l​λi​ai​=0λik​≥0,i=1,…,mλik​(aiT​xk+1−bi​)=0,i=1,…,m​

設 x ∗ x^* x∗是 { x k } \{x^k\} {xk}的聚點，不妨記為 { x k } , x k → x ∗ \{x^k\}, x^k\to x^* {xk},xk→x∗. 由于 { λ k } \{\lambda^k\} {λk}有界，存在收斂子列 { λ k i } , λ k i → λ ∗ \{\lambda^{k_i}\}, \lambda^{k_i}\to \lambda^* {λki​},λki​→λ∗.

令 k i → ∞ : k_i\to\infty: ki​→∞:

P x ∗ + c − N x ∗ + ∑ λ i ∗ a i = 0 λ i ∗ ≥ 0 , i = 1 , … , m a i T x ∗ − b i ≤ 0 , i = 1 , … , m a i T x ∗ − b i = 0 , i = m + 1 , … , m + l \begin{aligned} &Px^*+c-Nx^*+\sum\lambda^*_ia_i=0\\ &\lambda_i^*\geq 0, i=1, \dots, m\\ &a_i^Tx^*-b_i\leq 0, i=1,\dots, m\\ &a_i^Tx^*-b_i=0, i=m+1, \dots, m+l \end{aligned} ​Px∗+c−Nx∗+∑λi∗​ai​=0λi∗​≥0,i=1,…,maiT​x∗−bi​≤0,i=1,…,maiT​x∗−bi​=0,i=m+1,…,m+l​

即QP的KKT條件，是以 x ∗ x^* x∗是QP的KKT點.

參考資料

非凸二次規劃 上海财經大學 崔雪婷