案例：最短路径问题
公式:
min ∑ i , j ∈ E W i j X i j s . t . X i j = 0    o r    1 ∑ X i j − ∑ X j i = { 1 , if i = s − 1 , if i = d 0 , otherwise \begin{aligned} & \min \sum_{i,j \in E} W_{ij}X_{ij} \\ & s.t. X_{ij} = 0 \; or \; 1 \\ & \sum X_{ij} - \sum X_{ji} = \begin{cases} 1, & \text {if $i=s$ } \\ -1, & \text {if $i=d$ } \\ 0, & \text{otherwise} \end{cases} \end{aligned}mini,j∈E∑WijXijs.t.Xij=0or1∑Xij−∑Xji=⎩⎪⎨⎪⎧1,−1,0,if i=s if i=d otherwise
对于公式第二条是一个选择问题，比较难处理，修改为X i j ≥ 0 X_{ij} \geq 0Xij≥0
优化问题的分类
线性规划/非线性规划
线性规划
如果所有函数都是线性函数，就是线性规划
线性函数
f i ( α x + β y ) = α f i ( x ) + β f i ( y ) ∀ i = 0 , 1... m f_i(\alpha x + \beta y) = \alpha f_i(x) + \beta f_i(y) \quad \forall i=0,1...mfi(αx+βy)=αfi(x)+βfi(y)∀i=0,1...m
非线性规划
如果其中有一个或多个函数不是线性函数，就是非线性规划。
凸规划/非凸规划
凸规划
所有的f i f_ifi都是凸函数
f i ( α x + β y ) ≤ α f i ( x ) + β f i ( y ) ∀ i = 0 , 1... m f_i(\alpha x + \beta y) \leq \alpha f_i(x) + \beta f_i(y) \quad \forall i=0,1...mfi(αx+βy)≤αfi(x)+βfi(y)∀i=0,1...m
凸函数：
非凸函数：
所有线性规划问题都满足凸规划的问题。
光滑/非光滑
针对目标函数f 0 f_0f0,如果函数每个点都是可微的就是光滑问题。
光滑：
非光滑：
连续/离散
针对与可行域
连续
离散
单目标/多目标
主要内容
1）凸集、凸函数、凸优化
2）凸优化的理论知识
3）若干凸优化算法