Methods: Quadratic programming und SOCP

Definition

Qua­dra­tic pro­gramming (QP), qua­dra­ti­cal­ly cons­trai­ned qua­dra­tic pro­gramming (QCQP), and second order cone pro­gramming (SOCP) are gene­ra­liza­ti­ons of line­ar pro­gramming (LP). They encom­pass many prac­ti­cal pro­blems, inclu­ding gene­ra­liza­ti­ons of least squares.

The line­ar objec­ti­ve func­tion and line­ar cons­traints of LP are exten­ded to qua­dra­tic objec­ti­ve func­tions and qua­dra­tic cons­traints. Qua­dra­tic pro­grams have the form:

\[
\begin{align*}
\text{(QP)} \quad &  \min_x \quad \frac{1}{2} x^T P_0 x + \langle c_0, x \rangle \\
&~ \text{s.t.}  \quad Ax = b \\
& \quad Gx \ge h
\end{align*}
\]
\[
\begin{align*}
\text{(QCQP)}\quad &  \min_x \quad \frac{1}{2} x^T P_0 x + \langle c_0, x \rangle \\
& ~\text{s.t.}  \quad Ax = b \\
& \quad \frac{1}{2} x^T P_k x + \langle p_k, x \rangle \le h_k \quad k=1, …, m_2
\end{align*}
\]

whe­re \(x, c_0, b, h\) are vec­tors and \(P_0, P_1, …, P_{m_2}, A, G\) are matri­ces. QP direct­ly extends LP by incor­po­ra­ting the qua­dra­tic term \((1/2) x^T P_0 x\) in the objec­ti­ve func­tion, and QCQP extends QP by inclu­ding qua­dra­tic terms \((1/2) x^T P_k x\) in the cons­traints, invol­ving cir­cle and ellip­so­id equa­tions. SOCP inves­ti­ga­tes an even more gene­ral optimi­zation problem:

\[
\begin{align*}
\min_x & \quad \langle c, x \rangle \\
\text{s.t.} & \quad Ax = b \\
& \quad \|G_k x + h_k\|_2 \le \langle f_k, x \rangle + d_k \quad k=1, …, m_2
\end{align*}
\]

in the optimi­zation varia­ble \(x\), whe­re \(x, c, b, f_1, …, f_{m_2}, h_1, …, h_{m_2}\) are vec­tors, \(A, G_1, …, G_{m_2}\) are matri­ces, and \(d_1, …, d_{m_2}\) are scalars.

Example

SOCP allows for the solu­ti­on of line­ar pro­grams whe­re the con­di­ti­ons are sto­cha­stic in natu­re. Sup­po­se two pro­ducts are to be manu­fac­tu­red in quan­ti­ties \(x_1, x_2\) such that the demand \(b\) is met while mini­mi­zing pro­duc­tion cos­ts \(c_1x_1 + c_2x_2\). Now, con­sider that the pro­duc­tion pro­cess is sub­ject to uncer­tain­ties, so that only parts \(a_1x_1, a_2x_2\) of the manu­fac­tu­ring out­put are usable. If \([a_1, a_2]\) are ran­dom, it makes sen­se to requi­re the ful­fill­ment of the demand not abso­lut­e­ly but with high pro­ba­bi­li­ty \(\eta\). If \(a=[a_1, a_2]\) is nor­mal­ly dis­tri­bu­ted with mean \(\bar{a}=[\bar{a}_1, \bar{a}_2]\) and cova­ri­ance matrix \(\Sigma\), then

\[
\begin{align}
P(a^Tx \ge b)\ge \eta & \Leftrightarrow \phi^{-1}(\eta) \|\Sigma^{1/2} x \|_2 \le \bar{a}^Tx — b
\end{align}
\]

whe­re \(P(\cdot)\) stands for the pro­ba­bi­li­ty of the enc­lo­sed expres­si­on and \(\phi^{-1}\) is the inver­se of the cumu­la­ti­ve nor­mal dis­tri­bu­ti­on func­tion. The cor­re­spon­ding SOCP

\[
\begin{align}
\min_x ~~~& c_1x_1 + c_2x_2 \\
\text{s.t.} & x_1 \ge 0 ~~~ x_2 \ge 0 \\
& \phi^{-1}(\eta)\|\Sigma^{1/2}x\|_2 \le \bar{a}^Tx‑b
\end{align}
\]

for­mu­la­tes a cost mini­miza­ti­on while ensu­ring a pro­ba­bi­li­ty of demand covera­ge of \(\eta\)% [1, p.158]. The sub­se­quent figu­re illus­tra­tes this for the case \(\bar{a}=[0.7, 0.7], \Sigma=0.1 I\), and \(\eta=90\%\); the other para­me­ters are as in the exam­p­le for LP.

Figu­re 1: The fea­si­ble set is a cur­ved con­vex set. Its inter­sec­tion with the iso­cost line repre­sen­ting the lowest cos­ts yields the optimum—in this case \([4.5, 1]\), which is con­sider­a­b­ly distant from the ori­gi­nal demand line \(x_1 + x_2 = 2\).

Geometrical aspects

The cone con­di­ti­on \( \|\Sigma^{1/2} x\|_2 \le [\phi^{-1}(\eta)]^{-1}(\bar{a}^Tx‑b)\) is a mul­ti­va­ria­te gene­ra­liza­ti­on of the clas­si­cal con­fi­dence inter­vals. While the­se are actu­al inter­vals in the one-dimen­sio­nal case, in the two-dimen­sio­nal case they take on ellip­so­id-like shapes. The term \(\| \Sigma^{1/2} x\|_2\) is the stan­dard devia­ti­on of the ran­dom line­ar com­bi­na­ti­on \(a^Tx\) and thus a mea­su­re of the disper­si­on around the expec­ted value \(\bar{a}^Tx\).

Both mea­su­res are nee­ded to esti­ma­te the pro­ba­bi­li­ty that the share \(a^Tx\) of defect-free pro­ducts falls short of the requi­red demand due to ran­dom fluc­tua­tions. Sin­ce \(\|\Sigma^{1/2} x\|_2\) and \(a^Tx\) appear on both sides of the equa­ti­on, it can only be for­mu­la­ted as an SOCP, not as a QCQP.

Figu­re 2: The 1D 95% con­fi­dence inter­val is the inter­val within which 95% of all ran­dom­ly gene­ra­ted values fall (a). The 2D 95% con­fi­dence ellip­ses achie­ve the same for 2D data (b). The cone for­mu­la­ti­on of the sto­cha­stic cons­traints uti­li­zes ellip­so­ids and line­ar equations ©.

Applications

All examp­les of appli­ca­ti­ons of LP are also examp­les of appli­ca­ti­ons of SOCP. In par­ti­cu­lar, pro­blems that invol­ve vec­tor lengths and ellip­so­ids can be for­mu­la­ted, which include sto­cha­stic gene­ra­liza­ti­ons of LP and the mini­miza­ti­on of phy­si­cal­ly moti­va­ted qua­dra­tic ener­gies. Spe­ci­fi­cal­ly, the­se are port­fo­lio opti­miza­ti­ons, robust LP, LP with sto­cha­stic cons­traints, opti­mal line­ar-qua­dra­tic con­trol of kine­ma­tic sys­tems, phy­si­cal simu­la­ti­on, para­me­ter esti­ma­ti­on in Gaus­si­an models, robust Least-Squa­res, Kal­man fil­te­ring, iso­to­nic regres­si­on, anten­na design, robot tra­jec­to­ry optimi­zation, and image pro­ces­sing. Details can be found here.

The examp­les seem less prac­ti­cal­ly rele­vant and intui­tively under­stan­da­ble than with LP. Howe­ver, this is becau­se QP, QCQP, and SOCP extend the clas­si­cal LP to include the pre­sence of uncer­tain­ty and pro­vi­de new pos­si­bi­li­ties for other estab­lished tech­ni­ques such as Least-Squares.

Solution procedure

Sin­ce the fea­si­ble sets are cur­ved, sear­ching for the opti­mum by enu­me­ra­ting and eva­lua­ting all ver­ti­ces is not prac­ti­cal. Solu­ti­on approa­ches with a par­ti­cu­lar empha­sis on speed are often gra­di­ent-based, as the gra­di­ents of qua­dra­tic and line­ar terms are simp­le to cal­cu­la­te. The­se include methods such as con­ju­ga­te gra­di­ents, aug­men­ted Lagran­gi­an, and pro­jec­ted gra­di­ents [2, pp. 73, 116, 173]. Due to their uni­ver­sal appli­ca­bi­li­ty and incre­asing nume­ri­cal per­for­mance, inte­ri­or-point methods are also incre­asing­ly used, which sub­sti­tu­te cons­traints with addi­tio­nal penal­ty terms.

Practical aspects

SOCPs with many tens of thou­sands of varia­bles can relia­bly be sol­ved today. Solu­ti­on algo­rith­ms are available in the form of open-source soft­ware, such as the Split­ting Conic Sol­ver [3]. Due to the clo­sen­ess of QP to fini­te ele­ment methods, the­re is also soft­ware spe­ci­fi­cal­ly for appli­ca­ti­ons in struc­tu­ral engi­nee­ring and mecha­ni­cal engi­nee­ring [4]. Given the fre­quent occur­rence of qua­dra­tic ener­gy terms in phy­sics, mecha­nics, and sta­tis­tics, QP is a natu­ral tool in the­se disci­pli­nes. The cor­rect form of QPs and QCQPs may be direct­ly dis­cer­ni­ble from a pro­blem for­mu­la­ti­on; SOCPs are typi­cal­ly har­der to inter­pret. If not all embed­dings were obvious in LP, this is even more the case here.

Code & Sources

Exam­p­le code: Methods_socp.py in our tuto­ri­al­fol­der

[1] Boyd, S., & Van­den­berg­he, L. (2004). Con­vex Optimi­zation. Cam­bridge: Cam­bridge Uni­ver­si­ty Press.

[2] Dostál, Zde­nek. (2009) Opti­mal Qua­dra­tic Pro­gramming Algo­rith­ms: With Appli­ca­ti­ons to Varia­tio­nal Ine­qua­li­ties. Ber­lin Hei­del­berg: Sprin­ger Sci­ence & Busi­ness Media.

[3] O’do­noghue, B., Chu, E., Parikh, N., & Boyd, S. (2016). Conic Optimi­zation via Ope­ra­tor Split­ting and Homo­ge­neous Self-Dual Embed­ding. Jour­nal of Optimi­zation Theo­ry and Appli­ca­ti­ons, 169(3), 1042–1068.

[4] Szabo, B. A., & Tsai C. (1973). The qua­dra­tic pro­gramming approach to the fini­te ele­ment method. Inter­na­tio­nal Jour­nal for Nume­ri­cal Methods in Engi­nee­ring, 5(3), 375–381.