Lecture1——對最優化的介紹

一，簡介——什么是最優化？

1，三種問題：

用80米的圍欄盡可能的圍成一個面積最大的矩形
如何規劃產品的生產，使得公司獲得的利潤最大
給你一個圖（Graph），如何獲得最短的距離

2，一個普通的最優化問題有哪幾個部分？

決策（Decision）
目標（Objective）
限制（Constraints）

最優化涉及用一個或者多個決策使得目標最優化，同時也會存在一些限制，根據題目的背景，我們要獲得的可能是最大化，也可能是最小化。

因此我們發現，在第一部分給出的三個問題中：

圍欄問題

決策：圍成矩形；目標：面積最大化；限制：80米圍欄

生產問題：

決策：生產計劃；目標：利潤最大化；限制：生產資源

最短距離問題

決策：從S到T的路徑；目標：路徑最短；限制：從S出發，T為終點

3，最優化的歷史

最早的研究是在公元前 300-100 年，當時歐幾里得研究幾何學 / 海倫研究光的反射原理。
它主要是數學的一部分（主要貢獻者：牛頓、拉格朗日、歐拉等）
現代優化始于 20 世紀，在第二次世界大戰期間受到廣泛關注。
今天，計算機的使用和數據的可用性為優化提供了新的方法和視角。

當下重要應用場景：AI與機器學習，圖像處理

4，最優化的前置知識

在學習最優化之前，你可能需要學習微積分，線性代數，這樣才能順利的理解。

5，學習目標

建模技術：如何將實際問題轉化為優化問題，尤其是好的優化問題？
優化算法：如何有效地解決優化問題？
實施：如何使用可用工具解決優化問題？

二，最優化基礎

1，基本術語——最優化問題的數學表達

通常一個最優化問題可以表達為：

? ? ? ? ? ? ? ? ? ? ? ? x——>決策變量（Decision variable）

? ? ? ? ? ? ? ? ? ? ? ? f——>目標函數（Objective function）

? ? ? ? ? ? ? ? ? ? ? ??——>限制（Constraints）

? ? ? ? “maximize”與之類似。

一些轉化

（1） $maximize_{x}c(x)$ ?： $f(x)=-c(x)\rightarrow minimize_{x}f(x)$

（2）限制 $l_{i}(x)\geqslant 0$ ?： $g_{i}(x)=-l_{i}(x)\rightarrow g_{i}(x)\leqslant 0$

（3）一些特殊限制：非正（nonpositivity）和非負（nonnegativity）

（4）在問題中通常不考慮嚴格不等式限制。

2，關于“值”和“結果”的一些術語

可行點（Feasible point）：滿足所有約束的決策變量。
可行集（區域）（Feasible set/region）Ω：可行點集。
最佳解決方案（Optimal solution）：達到與任何其他可行點一樣好的目標值的（可行）決策變量。
最佳值（Optimal value）：任何最佳解決方案的目標值（如果有）；所有可能目標值的最大下限（最小化）。

3，最小化器（Minimizer）

一個例題（來自課件）：

所以，對與點? $x^{^{*}}\in R^{n}$ ?他可以被稱為：

局部最小化器（local minimizer）：如果x? ∈ ?，存在 $\epsilon > 0$ ， $f(x)\geqslant f(x^{*})$ 對于所有的 $x^{*}$ $\in$ ??∩B(x?,?)
嚴格最小化器（strict local minimizer）：如果x? ∈ ?，存在 $\epsilon > 0$ ， $f(x)> f(x^{*})$ 對于所有的 $x^{*}$ $\in$ ?（?∩B(x?,?)）\{x?}.
全局最小化器（global minimizer）：如果x? ∈ ?，存在 $\epsilon > 0$ ， $f(x)\leqslant f(x^{*})$ 對于所有的x ∈ ?.
嚴格全局最小化器（strict global minimizer）如果x? ∈ ?，存在 $\epsilon > 0$ ， $f(x)< f(x^{*})$ 對于所有的x ∈ ?\{x?}.

注意：全局最小化器=全局解=最優解；最大化器類似

三，最小化問題可能的結果和分類

1，可能的結果

不可行（Infeasible）：問題中沒有找到可行點。

? ? ? ? 例如： $minimize\underset{x\in R^{n}}{}$ ? f(x) s.t. x ≥ 1,x ≤ 0

可行（Feasible）：

? ? ? ? ?（1）無界最優解：例如最優解結果是負無窮。

? ? ? ? ?（2）有限最優解：最優解的值是有界的；

? ? ? ? ? ?但是，這個最優解又分可得和不可得：

? ? ? ? ? ? ? ? ? ? ? ? ?如1/x 在 x $\geqslant$ 1的最小值是不可得的

? ? ? ? ? ? ? ? ? ? ? ? ?如sinx 在x>0的最小值是可得的

注意：我們可能會有多個最佳解決方案，但最佳值只有一個。

2，分類

有限制的或無限制的。如?? =? $R^{n}$ ，則是無限制的
線性的或非線性的。 $f$ , $g_{i}$ (i = 1,...,m) and $h_{j}$ (j = 1,...,p) are all linear;如果其中的函數有非線性的，則這類問題也是非線性的
連續的或離散的。如果問題內存在變量是離散的，則是離散的；反之則是連續的。

Integer Optimization：一些或所有的變量是整數。

默認狀態下，我們認為問題中的值是連續的，除非很明確的告訴你是離散的。

注意：

上述分類基于 f、g、h 的結構以及可行集 Ω：

有時非線性問題可以等效地轉換為線性問題。有時線性問題可以等效地轉換為連續優化問題。

線性優化是研究最深入、最簡單的優化問題：

非線性優化和整數優化可能比線性優化難得多。因此，在很多情況下，人們努力尋找問題的線性優化公式（傳統上）。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/24378.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/24378.shtml
英文地址，請注明出處：http://en.pswp.cn/web/24378.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！