最佳化理論(Optimization Theory)

回味一下高中數學 & 進階版的概念吧！

最佳理論應用場景乍看遙遠，但實際上最環繞著我們，

• 物流業的倉儲與路線最佳化
• 金融業的最佳資產分配、最小化風險
• 製造業的排程最佳化、最小化成本
• 航空公司的路線最佳化

這些都是我們生活周遭常見的例子，但轉換到學理上，要如何看待這些事呢?

數學上怎麼看待最佳化?

傳統的單峰函數或凸函數都可以快速找到極大或極小值，如下A 圖我們可以透過Ternary Search尋找，B 圖則可以透過Gradient Descent尋找。

Unimodal functions and Bimodal functions 示意圖。Source: https://www.geeksforgeeks.org/mathematics-unimodal-functions-bimodal-functions/

但碰上多項式函數 (Polynomial)，進行微分尋找斜率為零者，可能找到極值或鞍點。我們就可以嘗試多種作法：

Polynomial function 示意圖。

• Hill Climbing
  於任意起點開始，若為找極大值，就如矇眼登山，若感覺步伐向上就前行，向下就沿稜線走，直到可以繼續向上，最終攻頂。
  缺點: 可能停在山腰 (local Maxumum)。

Hill Climbing 示意圖。Source: https://genome.sph.umich.edu/w/images/5/51/Bios615-fa12-lec20-presentation.pdf

• Simulated Annealing
  是前一種做法的改良版，允許向下，但設定機率來決定是否要往下走一點路(如下圖的Jump)，向上時仍持續前行，直到攻頂。
  缺點: 可能停在山腰 (local Maxumum)。Jump後仍回原小山頂。

Simulated Annealing 示意圖。Source: https://genome.sph.umich.edu/w/images/5/51/Bios615-fa12-lec20-presentation.pdf

• Gradient Descent 梯度下降法
  相當於爬山時，尋找梯度(斜度)最陡的方向，並朝此方向前進。
  重要前提: 函式必需可微分。

梯度是什麼 ?
相當於進行偏微分的計算，一元函數代表純量函數；多元函數代表向量函數。於網路爬文時，找到高手的多維梯度解釋方式，多維的梯度計算範例相當淺顯易懂。

• Adaptive Gradient Descent
• Steepest Descent
• Coordinate Descent

理論上的最佳化如何定義?

1. 無拘束最佳化問題 (Unconstrained Optimization)
2. 有拘束最佳化問題 (Constrained Optimization)

• 若考慮的條件為 Convex 函數，泛稱為 Convex Optimization 問題，將採Convex Analysis 或 Convex Program進行解題。
• 若為非線性問題，則採 Lagrange multipliers method/ Dynamic Programming / Iterative Algorithm Search進行解題。

而 Convex optimization最著名的特性就是「局部最優值必定等於全局最優值」，因此為最容易解的問題。

面最佳化的問題的兩大重心：

1. 目標函數(Objective function)：
   如同我們要生產製造的內容與投入報酬的公式。
   像是寫一篇 medium文章需要花費 30 分鐘，得到的快樂程度有3分，看一部電影需要花費 120 分鐘，得到的快樂程度有10分。
2. 約束條件(Constraints)
   就是投入的成本函式，因為時間有限、資源有限。
   如假設每天有２小時的自由時間，我們就可以知道：

就好像解高中數學一樣，但真實世界的成本函數與時間、資源函式是需要考慮更複雜的條件的。又如邊際效用遞減，應用到人身上的時候，寫第一篇medium的爽度，到第三篇、第四篇，爽度的增加幅度會逐步下降。

目標式告訴我們目的地方向(夢想)為何，
限制式告訴我們要如何配置時間與資源(人生)。