概述

本文將探究一個被稱為二次規(guī)劃的優(yōu)化問題，這是一種特殊形式的非線性約束優(yōu)化問題。二次規(guī)劃在許多領(lǐng)域都有運用，比如投資組合優(yōu)化、求解支持向量機(SVM)分類問題等。在R中求解二次規(guī)劃有許多包，這次，我們將討論一下quadprog包。在我們開始講解案例之前，我們將先簡短地介紹一下二次規(guī)劃的機理。

什么是二次規(guī)劃

對于一個二次規(guī)劃問題,首先要考慮的就是一個二次目標(biāo)函數(shù):

Q(x)=12xTDx?dTx+c.

這里 x 在 ?n 中是一個向量, D 是一個n×n 的對稱正定矩陣，在 ?n 中 d 是常數(shù)項約束，c 是一個標(biāo)量常數(shù)。Q(x)函數(shù)通常以二次函數(shù)的形式出現(xiàn)，并且它高維的通項表達(dá)式是：

q(x)=ax2+bx+c

Q(x)的關(guān)鍵特性在于這是一個凸函數(shù)。

我們也對向量x構(gòu)造一個線性約束集合，即x ∈?n。
我們把這些約束寫成:

Ax=fBx≥g

這里，A 是一個 m1×n 的矩陣且約束為 m1≤n，BB 是一個 m2×n 的矩陣.向量 f 和向量 g的長度分別是m1和m2.

這是一種讓我們可以充分考慮實際條件的標(biāo)準(zhǔn)型。比如我們讓 x 強制滿足

∑i=1nxi=1

的求和條件，或者滿足ai≤xi≤bi的區(qū)間約束。接下來，我們將介紹如何將這些約束轉(zhuǎn)化為矩陣表達(dá)。

用這個符號系統(tǒng),我們可以簡潔表示二次規(guī)劃 (QP):

{minimizex∈?n:Q(x)=12xTDx?dTx+csubjectto:Ax=fBx≥g

示例

目標(biāo)函數(shù)

考慮目標(biāo)函數(shù)：

Q(x,y)==12[xy][2?1?12][xy]?[?32][xy]+4x2+y2?xy+3x?2y+4.

約束條件

我們這個約束條件下的可行域內(nèi)尋求最小化：

yyy≥≥≤2?x?2+x3.

我們可以找到這個可行域的頂點并在R畫出整個可行域:

plot(0, 0, xlim = c(-2,5.5), ylim = c(-1,3.5), type = "n",       xlab = "x", ylab = "y", main="Feasible Region") polygon(c(2,5,-1), c(0,3,3), border=TRUE, lwd=4, col="blue")

 SHAPE  \* MERGEFORMAT

化為標(biāo)準(zhǔn)型

想要用quadprog包求解二次規(guī)劃，我們需要同時轉(zhuǎn)化我們的目標(biāo)函數(shù)和約束條件為矩陣形式。這里是官方文檔的說明：

This routine implements the dual method of Goldfarb and Idnani (1982, 1983) for solving quadratic programming problems of the form min(-d^T b + 1/2 b^T D b) with the constraints A^T b >= b_0.

可惜官方文檔多可讀性不高，我們很難得知如何準(zhǔn)確地轉(zhuǎn)化二次型Q(x,y)為一個矩陣形式。首先，我們觀察到，對于任意常數(shù) c， 都存在MinQ(x,y)+c 和 Q(x,y)的解相等。因此，我們可以忽略二次規(guī)劃中的常數(shù)項:

D=[2?1?12]d=[?32].

我們可以寫出約束方程的矩陣形式:

????1?1011?1????[xy]≥????2?2?3????

因此：

A=????1?1011?1????Tb0=????2?2?3????

quadprog包默認(rèn)是求解最小化問題，目標(biāo)函數(shù)二次，約束一次。所以，我們的約束條件默認(rèn)的形式也就是AX>=bvec。通常我們需要把一些原來是求極大值的問題或者<=約束通過乘以負(fù)號來轉(zhuǎn)化。

這是R的完整實現(xiàn):

·       參數(shù)Dmat表示海賽矩陣

·       參數(shù)dvet表示一階向量，和Dmat的維數(shù)要相對應(yīng)。

·       參數(shù)Amat表示約束矩陣，默認(rèn)的約束都是是>=。

·       參數(shù)bvet表示右邊值，由向量，和Amat的維數(shù)要相對應(yīng)。

·       參數(shù) meq 表示從哪一行開始Amat矩陣中的約束是需要被當(dāng)作等式約束的。

結(jié)論

讓我們檢查一下 quadprog 求解器求解的結(jié)果吧：

(1/6,11/6) 點是唯一滿足約束條件和 Q(x,y)的最小化目標(biāo)，但 (?4/3,1/3)點才是 Q(x,y) 的最小值點。iterations,Lagrangian 和 iact 都是用來描述quadprog算法性能的。對于這些值之后我們將進一步討論。現(xiàn)在，讓我們先可視化二次規(guī)劃的解。為此，我們在Q(x,y)的可行域邊界添加一個外側(cè)的等高線圖。

在圖中，深綠色區(qū)域表示Q(x,y) 表面目標(biāo)函數(shù)值較小的解,而亮色表示目標(biāo)函數(shù)值較大的解。紅點是Q(x,y)的全局最小值點，而黃點表示二次規(guī)劃的解。

英文原文