凸優化筆記(5)Conic Programming簡介

05-15

本文主要參考卡耐基梅隆大學(CMU)的Ryan Tibshirani教授在Convex Optimization(Course 10-725/36-725)課上(課程網站鏈接：Convex Optimization)的Lecture Notes。以及參考了現任職牛津大學的Dr. Paul Goulart，以前在ETH任教時Convex Optimization課的Lecture Notes。如有錯誤疏漏，煩請指出。如需付費轉載，請聯繫筆者，zhu.hathaway@gmail.com。

我們在凸優化筆記(2)幾類標準問題以及Linear Programming簡介中講到：

凸優化的標準問題有四類：

1. Linear Programming(LP)
2. Quadratic Programming(QP)
3. Semidefinite Programming(SDP)
4. Cone Programming(CP)

今天我們繼續第四類問題——Conic Programming(CP)。在講CP之前，我們有必要澄清一下什麼是cone。

一、Cone

Definition: A set $old{chi}$ is said to be a Cone if for all $xin chi$ , $heta xin chi$ , for all $hetage 0$ .

所以如果 $x$ 是一個2維向量，那麼 $x$ 對應的Cone就是如下圖所示：

它是一條射線，其中該Cone包含原點，因為 $heta$ 可以等於0。更多例子，圖中a,b,d是cone，c,e,f不是cone(圖片來自http://wwwhome.ewi.utwente.nl/~DickinsonPJC/Teaching/2016CO/CO_Dickinson_7_v2016_11_11.pdf)：

顯然Cone不一定是convex的，如上圖中的a，以及下圖的右邊：

by Paul Goulart

那麼一個cone是convex的，背後滿足什麼樣的數學性質呢？學者們發現如下性質：

Definition: A set $old{chi}$ is said to be a Convex Cone if for all $x, yin chi$ , $heta_1 x+ heta_2 yin chi$ , for all $heta_1ge 0, heta_2ge 0$ .

接下來我們看看常見的三種的convex cone(非凸的cone暫時不舉例子了)：

1. Non-negative orthant(非負象限)：例如二維或者三維的非負象限

2. Norm cone(圖片來自http://www.seas.ucla.edu/~vandenbe/236C/lectures/conic.pdf)：注意這裡x,y都是變數哦

3. Positive definite/semidefinite cone(圖片來自http://www.seas.ucla.edu/~vandenbe/236C/lectures/conic.pdf)：

二、Conic Programming

Conic Programming的形式如下：

$min_{xin D}{kern 25pt}c^Tx\ old{subject{kern 3pt} to:} {kern 3pt} D(x)+din K\ {kern 53pt} Ax= b$

其中 $xin mathbb{R}^n$ ， $D(x)$ 是一個linear map of $x$ ，K是一個closed convex cone。顯然對於凸優化筆記(2)幾類標準問題以及Linear Programming簡介中的LP問題， $K=mathbb{R}_{+}^n$ (也就是剛才三個常見的convex cone中的非負象限)。對於凸優化筆記(4)Semidefinite Programming簡介中的SDP問題， $K=mathbb{S}_{+}^n$ (也就是剛才三個常見的convex cone中的Positive definite/semidefinite cone)。