優(yōu)化入門知識

什么是優(yōu)化問題

優(yōu)化問題：求最優(yōu)，例如獲利最大、最少損失、最短路徑、最小化風(fēng)險等等。
例如：之前文章提到華為杯2019F題多約束條件下智能飛行器航跡快速規(guī)劃，其中第一問就涉及求飛行器從A點到B點帶約束下的最短路徑。

如何判斷是不是優(yōu)化問題

題目帶有優(yōu)化、規(guī)劃、最值、安排、分配、最合理等等。

題目涉及到圖，例如三維空間飛行、二維地圖上旅行。

優(yōu)化模型建模

優(yōu)化模型格式：決策變量+目標(biāo)函數(shù)+約束條件。

決策變量：能夠?qū)δ繕?biāo)結(jié)果產(chǎn)生影響的變量。
$$x_i,i=1,2,...,n$$

目標(biāo)函數(shù)：通常都是一個Min或者Max求某個決策變量的函數(shù)表達式。例如：
$$Min(orMax)z=f(x),x=(x_1,...,x_n{)}^T$$
約束條件：以s.t.為開頭，后面寫上約束條件。
$$s.t.?\begin{array}{l}{g}_1(x)?0\\ g_2(x)?0\\ ...\\ g_n(x)?0\end{array}$$

求解器

優(yōu)化模型建立好之后，選擇什么樣的算法去解模型是比賽的關(guān)鍵。

求解器：用來求解模型的程序、算法之類的，在matlab里面求解器填寫的其實就是函數(shù)模型。

優(yōu)化問題的分類

從目標(biāo)函數(shù)的個數(shù)來說：可以分成單目標(biāo)和多目標(biāo)。

從問題的類型來說：可以分為規(guī)劃類、圖論和動態(tài)規(guī)劃。

規(guī)劃類按照決策變量在目標(biāo)函數(shù)和約束條件中是否線性：可以分為線性規(guī)劃和非線性規(guī)劃。
規(guī)劃類中，比較特殊的是決策變量為整數(shù)的“整數(shù)規(guī)劃”，和決策變量只能取0或者1的“0-1規(guī)劃”。
非線性規(guī)劃中比較特殊的是二次規(guī)劃，目標(biāo)函數(shù)是關(guān)于決策變量的二次函數(shù)，約束條件是線性函數(shù)。

圖論中常見的問題有：最短路、最小生成樹、網(wǎng)絡(luò)流和排隊論。

多目標(biāo)規(guī)劃

條件：線性規(guī)劃和非線性規(guī)劃只有一個目標(biāo)函數(shù)，多目標(biāo)函數(shù)有多個目標(biāo)函數(shù)（$f_i(x)$），講究一個既要還要。

方法：多目標(biāo)轉(zhuǎn)化為單目標(biāo)。

• 優(yōu)先因子：可以主觀上給目標(biāo)函數(shù)進行一個重要性排序，來使得整體的完成情況盡量好，也就是優(yōu)先因子，相當(dāng)于權(quán)重（$P_i$）。
  $$min\sum P_i{f}_i(x)$$
• 平方加權(quán)：知道每個目標(biāo)理想值的情況下，可以求每個目標(biāo)函數(shù)和理想值的平方和，可以帶上權(quán)重。
  $$min\sum {\lambda }_i[f_i(x)?{f_i}^{?}{]}^2$$
• 乘除法：如果每個目標(biāo)重要程度一樣。
  $$min\frac{f_1(x)f_2(x)...f_k(x)}{f_{k+1}(x)f_{k+2}(x)...f_n(x)}$$
• 分開求最優(yōu)解對比：有時候單獨最優(yōu)解之間差距可能不是很大，例如之前華為杯2019F題，有個論文就是分別求最優(yōu)路徑和最少矯正點，然后對比。

特殊：問題中存在剛性約束和柔性約束。剛性約束就是必須要滿足的，否者就是不可行解。柔性約束就是可以存在偏差的，例如使目標(biāo)f(x)盡可能不少于5，可以在5左右有正負偏差。這個正負偏差可以記作$d^{+}和d^{?}$， d + = m i n { f ( x ) ? f ? , 0 } , d ? = ? m i n { f ? ? f ( x ) , 0 } d^+=min\{f(x)-f^*,0\},d^-=-min\{f^*-f(x),0\} d+=min{f(x)?f?,0},d?=?min{f??f(x),0}。
例子：三個目標(biāo)函數(shù)，三個目標(biāo)是柔性約束，1盡量不超過、2盡量等于、3盡量不少于，會發(fā)現(xiàn)柔性約束都有“盡量”兩個字作為修飾。最終的多目標(biāo)規(guī)劃函數(shù)可以寫成：
min ? { P 1 d 1 + + P 2 ( d 2 ? + d 2 + ) + P 3 d 3 ? } \min{\{P_1{d_1}^++P_2({d_2}^-+{d_2}^+)+P_3{d_3}^-\}} min{P1?d1?++P2?(d2??+d2?+)+P3?d3??}
擴展一下格式：
$$min\sum P_i({w_i}^{+}{d_i}^{+}+{w_i}^{?}{d_i}^{?})$$

總結(jié)：多目標(biāo)規(guī)劃，可以轉(zhuǎn)換成為單目標(biāo)問題，然后單目標(biāo)去看符合單目標(biāo)中那種取套，根據(jù)情況套回規(guī)劃類、圖論和動態(tài)規(guī)劃中。