[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62) › 05｜影片 [1:40:36–2:04:58](https://www.youtube.com/watch?v=S1km7opW6rw&t=6036s)｜投影片 Ch4 p.21–26｜上一章 [04 連續空間的梯度上升（1:21–1:40）](https://app.notion.com/p/3e6fc631b030812a99d4eb793b437690)｜下一章 [06 部分觀察與線上搜尋（2:16–2:29）](https://app.notion.com/p/3e6fc631b0308161a1a1c05842cdd2c7) 跳過提示：(1:40:36–1:50:14) 老師在接續推導牛頓法(切線斜率、更新公式)並推廣到 Hessian 矩陣(二次微分排成的矩陣)，聽不懂可以直接跳到 [1:50:14](https://www.youtube.com/watch?v=S1km7opW6rw&t=6614s)，接著講「這整套方法就是深度學習的 learning rate」的類比。 白話：跳過的這段在把「用切線找方程式的解」這招，改裝成「找山頂或谷底」的工具；結論都寫在下面「牛頓法拿來找極值」那段，不聽推導也看得懂。 跳過提示：(1:53:15–2:00:46) 老師在寫線性規劃的數學設定(矩陣內積、線性方程式、工廠排程的不等式限制)，聽不懂可以直接跳到 [2:00:46](https://www.youtube.com/watch?v=S1km7opW6rw&t=7246s)，接著進入同學問答時間。 白話：跳過的這段在把「工廠每種產品做多少、原料不能超用」這種現實問題寫成數學式子；下面「限制最佳化與線性規劃」和「例子：製造商排產」兩段已經用中文講完。 ## 重點 - 梯度 ∇f（把每個變數的偏微分排成的向量）跟等高線垂直，指向「走一小步、函數值上升最多」的方向；反方向就是下降最快的方向。 - 牛頓法原本是用切線求 g(x) = 0 的根；把 g 換成 ∇f，就變成找極值的更新式 x ← x − Hf⁻¹(x)∇f(x)，H 是二次微分排成的 Hessian 矩陣。連續空間一樣會卡在局部最高點；步長 α 在深度學習裡叫 learning rate。 - 解必須滿足硬性限制的最佳化叫 constrained optimization；目標和限制都是線性的叫 linear programming（線性規劃），標準形式是 minimize cᵀx subject to Ax = b、x ≥ 0。怎麼求解本課不講。 ## Exam-ready - **Gradient ⊥ level set f(x) = c**: "The gradient of f at x0, denoted by ∇f(x0), is orthogonal to the tangent vector to an arbitrary smooth curve passing through x0 on the level set f(x) = c." "The direction of maximum rate of increase of a real-valued differentiable function at a point is orthogonal to the level set of the function through that point."（Ch4 p.21） - 中文：函數 f 在 x₀ 的梯度 ∇f(x₀)，跟通過 x₀ 那條等高線（level set，f(x)=c）互相垂直。白話：站在山坡上，梯度是最陡的上坡方向，跟繞著山走、不上不下的那條路成直角。 - **Gradient = steepest direction**: "The gradient acts in such a direction that for a given small displacement, the function f increases more in the direction of the gradient than in any other direction."（Ch4 p.21）【老師強調】(1:43:49) - 中文：只要沿著梯度方向走一小步，f 上升的量會比往任何其他方向都多。白話：梯度就是「當下最陡的上坡方向」，這是老師特別強調的一句。 - **Newton's method of tangents xₖ₊₁ = xₖ − g(xₖ) / g′(xₖ)**: "Newton's method for solving equations of the form g(x) = 0 is also referred to as Newton's method of tangents." "If we draw a tangent to g(x) at the given point x(k), then the tangent line intersects the x-axis at the point x(k+1), which we expect to be closer to the root x* of g(x) = 0."（Ch4 p.22） - 中文：牛頓法（切線法）本來是用來解 g(x)=0 的根：在目前的猜測點 xₖ 對曲線 g(x) 畫一條切線，切線碰到 x 軸的地方就是下一個猜測 xₖ₊₁，通常會比 xₖ 更接近真正的根。 - **Newton's method for optimization x ← x − Hf⁻¹(x)∇f(x)**: "To find a maximum or minimum of f, we need to find x such that the gradient is zero (i.e., ∇f(x) = 0). Thus, g(x) in Newton's formula becomes ∇f(x), and the update equation can be written in matrix–vector form as"（Ch4 p.23） - 中文：要找 f 的極大或極小值，就是要找讓梯度等於零的點（∇f(x)=0）。把牛頓法公式裡的 g(x) 換成 ∇f(x)，就得到用矩陣寫的更新式：x ← x − Hf⁻¹(x)∇f(x)。 - **Hessian matrix Hᵢⱼ = ∂²f/∂xᵢ∂xⱼ**: "where Hf(x) is the Hessian matrix of second derivatives, whose elements Hij are given by"（Ch4 p.23） - 中文：Hessian 矩陣是把 f 所有的二次偏微分排成的矩陣，第 i 列第 j 欄的元素是 Hᵢⱼ = ∂²f/∂xᵢ∂xⱼ（先對 xᵢ、再對 xⱼ 微分）。它記錄的是「坡度變化的快慢」，也就是函數的彎曲程度。 - **Local optima in continuous spaces**: "Local search methods suffer from local maxima, ridges, and plateaux in continuous state spaces just as much as in discrete spaces. Random restarts and simulated annealing can be used and are often helpful."（Ch4 p.23） - 中文：在連續空間做局部搜尋（local search），一樣會卡在 local maxima（局部最高點）、ridges（山脊）、plateaux（高原），跟離散空間一樣；可以用 random restart（換個隨機起點重來）或 simulated annealing（模擬退火，偶爾允許往差的方向走）來補救。 - **Constrained optimization**: "A constrained optimization problem is constrained if solutions must satisfy some hard constraints on the values of the variables."（Ch4 p.24） - 中文：如果解必須滿足一些變數上的硬性限制（例如變數不能是負的、用量不能超過上限），這種最佳化問題就叫 constrained optimization（限制最佳化）。 - **Linear programming / convex optimization**: "The best-known category is that of linear programming problems, in which constraints must be linear inequalities forming a convex set and the objective function is also linear. Linear programming is probably the most widely studied and broadly useful class of optimization problems. It is a special case of the more general problem of convex optimization, which allows the constraint region to be any convex region and the objective to be any function that is convex within the constraint region."（Ch4 p.24） - 中文：最有名的限制最佳化是 linear programming（線性規劃，LP）：限制是線性不等式、圍出一個凸集合（convex set），目標函數也是線性的，是研究最多、用途最廣的一類最佳化問題。線性規劃是更廣的 convex optimization（凸最佳化）的特例，凸最佳化允許限制區域是任何凸區域、目標函數是任何在該區域內為凸的函數。 - **LP standard form: minimize cᵀx subject to Ax = b, x ≥ 0 (maximize, Ax ≥ b, Ax ≤ b are variations)**: "Formally, a linear program is an optimization problem of the form" … "In fact, these variations can all be rewritten into the standard form shown above."（Ch4 p.25） - 中文：線性規劃的標準寫法是：在 Ax = b、x ≥ 0 的限制下，minimize（最小化）cᵀx。maximize（最大化），或限制寫成 Ax ≥ b、Ax ≤ b 的各種變形，都可以改寫成這個標準形式。 ## [1:40:36](https://www.youtube.com/watch?v=S1km7opW6rw&t=6036s) 梯度的幾何意義 上一章用 x ← x + α∇f(x) 一步步往上爬；這段老師拿自己最佳化課的投影片，換個角度說明梯度為什麼指對方向。想像函數 z = f(x₁, x₂) 的圖形是一個碗，你站在碗壁上某一點 x₀。把「跟你一樣高的所有點」投影到地面，會得到一圈曲線，叫 level set（等值集合，就是地理課的等高線，寫成 f(x) = c）。梯度 ∇f(x₀) 垂直於這圈等高線，指向高度上升最快的方向；反方向 −∇f(x₀) 就是下降最快的方向。【老師強調】(1:43:49) 如果忘了上一章（本週第 04 章學過：[連續空間的梯度上升](https://app.notion.com/p/3e6fc631b030812a99d4eb793b437690)，像蒙眼爬山，每一步先用梯度找出最陡的上坡方向，再往那裡走 α 這麼遠；α 叫步長，就是一步跨多大）。向量就是一組排好順序的數字，例如 (2, 4)，可以想成地圖上的一支箭頭：往東 2、往北 4；梯度就是這樣一支箭頭。 下面收起來的手算在做什麼：拿一個簡單的碗，實際比較往四個方向各走一小步，看哪個方向高度上升最多；算出來是「沿梯度走上升最多，沿等高線走幾乎不變」，正好驗證上面那句話。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\chapter_4_search_in_complex_environments_p021.png | Ch4 p.21：碗狀曲面 z = f(x₁, x₂) 被水平面 z = c 切一刀，切口投影到地面就是等高線（level set）；梯度 ∇f(x₀) 垂直於等高線]] 圖上重點： - 標題 Introduction（簡介）。第一句：f 在 x₀ 的梯度 ∇f(x₀)，跟「通過 x₀、躺在等高線 f(x) = c 上的任何平滑曲線」的切線方向垂直。orthogonal（垂直）、tangent vector（切線方向的箭頭）、level set（等高線）。 - 第二句：函數在某一點「上升最快的方向」（direction of maximum rate of increase），垂直於通過這一點的等高線。 - 第三句：走同樣一小步（small displacement），沿梯度方向走，f 增加得比往任何其他方向都多。 - 右下圖：上面的碗是 z = f(x₁, x₂) 的圖形；Horizontal Plane（水平面）z = c 把碗切一刀；切口投影到地面就是 Level set (curve)（等高線）；地面上 x₀ 那點的箭頭 ∇f(x₀) 跟等高線成直角。 這張圖在講：梯度這支箭頭永遠跟等高線成直角，而且指向爬升最快的方向。 **注意：老師口頭說「你要往切線的這個方向走，你的海拔高度會增加最快」(1:42:59)，他指的是「垂直於等高線切線」的方向。沿著等高線本身的切線走，高度幾乎不變。考試寫投影片的版本：the gradient is orthogonal to the level set。**
要先懂什麼？偏微分和梯度是什麼？ - 偏微分（partial derivative）：多變數函數只動一個變數、其他變數當常數時的斜率。例 f(x₁, x₂) = x₁² + x₂²：∂f/∂x₁ = 2x₁（把 x₂ 當常數），∂f/∂x₂ = 2x₂。 - 梯度（gradient）：把每個變數的偏微分排成一個向量，∇f = (∂f/∂x₁, ∂f/∂x₂)。上例在點 (1, 2)：∇f = (2, 4)。 - 兩個向量互相垂直（orthogonal），就是內積等於 0。內積 (a, b)·(c, d) = ac + bd。
它到底怎麼運作？手算一次：梯度真的上升最快嗎？ 用 f(x₁, x₂) = x₁² + x₂²（碗底在原點），站在 x₀ = (1, 2)，高度 f = 5。 1. 等高線 f = 5 是半徑 √5 的圓；它在 (1, 2) 的切線方向是 (−2, 1)。 2. 梯度 (2, 4) 跟切線 (−2, 1) 的內積：2×(−2) + 4×1 = 0，所以梯度垂直於等高線。 3. 往不同方向各走 0.1（方向都縮成長度 1）： - 沿梯度 (0.447, 0.894)：f 變 5.457，上升 0.457 - 只沿 x₁ 軸 (1, 0)：f 變 5.21，上升 0.21 - 沿等高線切線 (−0.894, 0.447)：f 變 5.010，幾乎沒變（0.01 是碗的彎曲造成） - 沿梯度反方向：f 變 4.563，下降 0.437 結論：同樣走 0.1，沿梯度上升最多；要找碗底就往 −∇f 走，這就是 gradient descent（梯度下降）。
用生活例子講，等高線和梯度是什麼？ 你站在山坡上，起大霧只看得到腳邊。等高線就是「繞著山走、不上也不下」的那條路；梯度就是腳下最陡的上坡方向，它一定跟那條路成直角。滑雪的人想最快衝下山，就往梯度的反方向滑。
老師原話是什麼？ 「level set你把它想像的就是等高線的意思，在我們地理課裡面的等高線」(1:42:17) 「所以大家只需要記得一件事情就是說，你在這個function裡面的某一組解你去算他的梯度」(1:43:49) 「反之梯度的反方向就是能夠讓你快速降低海拔高度的那個方向」(1:44:09)
別人怎麼教這個？ 3Blue1Brown〈Gradient descent, how neural networks learn〉用動畫講「負梯度就是下降最快的方向」，並接到神經網路怎麼學：[YouTube](https://www.youtube.com/watch?v=IHZwWFHWa-w)
## [1:44:19](https://www.youtube.com/watch?v=S1km7opW6rw&t=6259s) 牛頓法：切線法 知道方向之後，還要決定走多遠。老師搬出牛頓法（Newton's method，又叫 Newton's method of tangents，切線法），它本來是用來解 g(x) = 0。做法是在目前的猜測 xₖ 對曲線 g(x) 畫切線，切線碰到 x 軸的位置就是下一個猜測 xₖ₊₁：xₖ₊₁ = xₖ − g(xₖ) / g′(xₖ)。通常更新兩三次就非常接近真正的根。 先記三個詞：根（root）是讓 g(x) 等於 0 的那個 x，也就是曲線碰到 x 軸的地方；切線（tangent）是貼著曲線、只碰一點的直線；g′(x)（念 g prime）是 g 的一次微分，意思是曲線在那一點的斜率，也就是切線有多陡。 下面收起來的推導和手算在做什麼：先用「斜率 = 高度 ÷ 水平距離」說明公式怎麼來，再拿「找 √2」實際跑三次，讓你看到牛頓法只要三步就準到小數點後五位。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\chapter_4_search_in_complex_environments_p022.png | Ch4 p.22：在 xₖ 畫切線，切線和 x 軸的交點是 xₖ₊₁，再畫一次得到 xₖ₊₂，很快逼近真正的根]] 圖上重點： - 標題 Newton's Method（牛頓法）。第一句：解 g(x) = 0 這種方程式的牛頓法，又叫 Newton's method of tangents（牛頓切線法）。 - 第二句：在目前的點 x⁽ᵏ⁾ 對 g(x) 畫切線，切線和 x 軸的交點（intersects the x-axis）就是 x⁽ᵏ⁺¹⁾，預期它比較接近真正的根 x*（root，答案）。投影片的 x⁽ᵏ⁾ 就是正文的 xₖ，「第 k 次的猜測」。 - 左下公式：切線斜率（slope）g′(x⁽ᵏ⁾) = g(x⁽ᵏ⁾) ÷ (x⁽ᵏ⁾ − x⁽ᵏ⁺¹⁾)；藍色箭頭表示移項後得到更新式 x⁽ᵏ⁺¹⁾ = x⁽ᵏ⁾ − g(x⁽ᵏ⁾) / g′(x⁽ᵏ⁾)。 - 右圖：從最右邊的 x⁽ᵏ⁾ 出發，沿切線滑到 x⁽ᵏ⁺¹⁾，再畫一次切線到 x⁽ᵏ⁺²⁾，已經幾乎貼在 x*（曲線碰 x 軸的地方）。 這張圖在講：每一步都用一條直線（切線）代替彎曲的曲線，找直線碰 x 軸的地方，一步一步逼近答案。
它到底怎麼運作？公式怎麼推，手算一次 √2 推導：g′(xₖ)（g 的一次微分）就是切線斜率 = 高度變化 ÷ 水平變化。切線從 (xₖ, g(xₖ)) 走到 x 軸上的 (xₖ₊₁, 0)，所以 g′(xₖ) = g(xₖ) / (xₖ − xₖ₊₁)，移項得 xₖ₊₁ = xₖ − g(xₖ) / g′(xₖ)。 手算：求 √2，就是解 g(x) = x² − 2 = 0，g′(x) = 2x，從 x₀ = 1 開始。 - 第 1 次：g(1) = −1，g′(1) = 2，x₁ = 1 − (−1)/2 = 1.5 - 第 2 次：g(1.5) = 0.25，g′(1.5) = 3，x₂ = 1.5 − 0.25/3 = 1.416667 - 第 3 次：g(1.416667) = 0.006944，g′ = 2.833333，x₃ = 1.414216 - 真正答案 √2 = 1.414214，三次後誤差只剩約 0.000002。
老師原話是什麼？ 「高中老師數學老師就告訴你說，牛頓法真的厲害，你只要update兩三次之後，你幾乎就非常非常接近真正的標準答案」(1:45:44)
別人怎麼教這個？ 3Blue1Brown〈Newton's fractal (which Newton knew nothing about)〉前段用動畫示範牛頓法怎麼用切線一步步逼近根，後段的碎形可以不看：[YouTube](https://www.youtube.com/watch?v=-RdOwhmqP5s)
## [1:47:11](https://www.youtube.com/watch?v=S1km7opW6rw&t=6431s) 牛頓法拿來找極值 找極大或極小值，就是找讓梯度等於零的 x，也就是解 ∇f(x) = 0。這跟牛頓法要解的 g(x) = 0 長得一樣，所以把 g 換成 ∇f；原本的 g′ 就變成 f 的二次微分。多變數時二次微分是一個矩陣，叫 Hessian 矩陣 Hf(x)，元素 Hᵢⱼ = ∂²f/∂xᵢ∂xⱼ。矩陣不能直接「除」，改成乘反矩陣，得到 x ← x − Hf⁻¹(x)∇f(x)。 幾個基本詞：極大值、極小值就是山頂和谷底，站在那裡四周是平的，所以梯度（坡度）等於零。矩陣是把數字排成一個方格表（幾列幾欄），多變數的資訊要用它來裝。下面表格左欄的 steepest-ascent hill climbing（最陡上升爬山法）是本週第 04 章學過的（[連續空間的梯度上升](https://app.notion.com/p/3e6fc631b030812a99d4eb793b437690)：每步沿梯度走 α 這麼遠）。 下面收起來的手算在做什麼：拿同一個碗形函數，比較牛頓法和梯度下降各要幾步才走到碗底；算出來牛頓法一步就到，梯度下降走六步還沒到，這就是表格裡「步數少」的意思。 **注意：老師口頭把牛頓法說成用來決定「最好的 α」、也就是沿梯度要走多遠的方法 (1:44:29、1:47:11)。投影片是分開講的：line search 是沿梯度方向一直延伸、直到 f 開始下降；Newton–Raphson 是另一個方法，直接解 ∇f(x) = 0，用 H⁻¹ 一次決定方向和步長，不用另設 α（p.20、p.23）。考試寫投影片的版本。**
**Steepest-ascent hill climbing****Newton–Raphson**
更新式x ← x + α∇f(x)x ← x − Hf⁻¹(x)∇f(x)
用到的資訊一次微分（梯度）一次微分＋二次微分（Hessian）
步長要自己設 αH⁻¹ 自動決定
成本每步便宜，但要走很多步每步貴（n×n 矩陣求反矩陣），但步數少，完美的碗一步到位
找到的點往上爬；改成 −α∇f 就是往下梯度為零的點，極大或極小都可能
要先懂什麼？二次微分、Hessian、反矩陣是什麼？ - 二次微分：一次微分告訴你「坡多陡」，二次微分告訴你「陡度變化多快」，也就是彎曲程度。 - Hessian 矩陣：把所有「先對 xᵢ、再對 xⱼ 偏微分」的結果排成 n×n 矩陣。例 f = x₁² + 3x₁x₂ + 2x₂²：∂f/∂x₁ = 2x₁ + 3x₂，∂f/∂x₂ = 3x₁ + 4x₂；再微一次得 H₁₁ = 2、H₁₂ = H₂₁ = 3、H₂₂ = 4。 - 反矩陣 H⁻¹：跟 H 相乘得到單位矩陣的矩陣，是矩陣版的「倒數」。矩陣沒有除法，所以「除以 H」寫成「乘 H⁻¹」。對角矩陣最好算：對角線 2、4 的反矩陣，對角線是 1/2、1/4。
它到底怎麼運作？手算一次：牛頓法一步 vs 梯度下降六步 函數 f(x₁, x₂) = (x₁ − 1)² + 2(x₂ + 2)²，碗底在 (1, −2)。從 (0, 0) 出發，目標是找最小值。 - 梯度：∇f = (2(x₁ − 1), 4(x₂ + 2))，在 (0, 0) 是 (−2, 8)。 - Hessian：對角線是 2、4，其他是 0；反矩陣的對角線是 1/2、1/4。 - 牛頓法一步：H⁻¹∇f = (−2/2, 8/4) = (−1, 2)，x ← (0, 0) − (−1, 2) = (1, −2)。一步就到碗底。 - 梯度下降（α = 0.1，x ← x − α∇f）：(0, 0) → (0.2, −0.8) → (0.36, −1.28) → (0.488, −1.568) → …，f 從 9 → 3.52 → 1.45 → 0.64，走了六步還在 (0.738, −1.907)。 為什麼一步到位？牛頓法等於用二次微分找一個碗貼住目前的函數，再直接跳到碗底。這個 f 本身就是完美的碗，所以一步就準；一般函數要多走幾步，但通常還是比梯度法少很多。
老師原話是什麼？ 「不要忘記倒三角fx已經是fx的一次微分了，它的角色就如同是這裡的gx」(1:47:46) 「如果你聽起來有點吃力呢，你就是要稍微複習一下以前的數學，這其實沒有到那麼難」(1:49:48) 「大家知道說在實數裡面我們做除法，在矩陣的運算裡面就相當於是在inverse的意思」(1:50:06)
## [1:50:14](https://www.youtube.com/watch?v=S1km7opW6rw&t=6614s) 連續空間一樣會卡住 就算用梯度、牛頓法這種比較高級的更新方式，連續空間的 local search 一樣會卡在 local maxima（局部最高點）、ridges（山脊）、plateaux（高原）。解法跟離散空間一樣：搭配 random restart（換隨機起點重來）或 simulated annealing（模擬退火，偶爾允許往差的方向走）。實務上 α 常常不去精算，而是依經驗設一個固定值，跑夠多次也不會差太多；這個 α 就是深度學習裡的 learning rate（學習率）。 這段用到的舊概念（第 2 週學過：[局部搜尋與爬山演算法](https://app.notion.com/p/3e6fc631b03081e896bdc677065a3376)）：local search 只記住目前一個解，每次往附近較好的解移動；local maximum 是「附近都比它低、但不是全世界最高」的小山頭；ridge 是一條斜斜的窄山脊，往任何單一方向走都會往下；plateau 是一片平地，四周一樣高，不知道往哪走。random restart 和 simulated annealing 是本週第 02 章學過的（[爬山法複習與模擬退火](https://app.notion.com/p/3e6fc631b03081a79865f701c688c1c4)：卡住就換個隨機起點重來；或一開始常允許往差的方向走、越後面越少）。離散空間是解一格一格數得出來（例如八皇后的棋盤），連續空間是解可以取任何小數（例如上一章的機場座標）。
要先懂什麼？深度學習的 learning rate 是什麼？ 訓練神經網路時有幾百萬個參數 θ，目標是讓 loss L(θ)（預測錯多少）最小，所以每步用 θ ← θ − α∇L(θ) 更新。α 就是 learning rate：太小要走很多步，太大會衝過頭。這跟本章的 x ← x + α∇f(x) 是同一件事，只是最大化用加、最小化用減。
老師原話是什麼？ 「你可以搭配random restart的策略，或者是simulated annealing的策略」(1:50:42) 「根據經驗設定一個固定的值，大概你跑夠多次也不會差太多啦」(1:51:24) 「其實這個alpha就是learning rate的意思」(1:51:36)
## [1:51:55](https://www.youtube.com/watch?v=S1km7opW6rw&t=6715s) 限制最佳化與線性規劃 解必須符合某些硬性限制的最佳化問題，叫 constrained optimization（限制最佳化），例如蓋機場的座標不能是負的。其中最有名、也是研究最多、用途最廣的是 linear programming（線性規劃，LP）：目標函數是線性的，限制是線性不等式，圍出一個 convex set（凸集合）。LP 是 convex optimization（凸最佳化）的特例。標準形式：在 Ax = b、x ≥ 0 的限制下 minimize cᵀx；改成 maximize、限制改成 ≥ 或 ≤ 的變形都能改寫成這個形式。 幾個基本詞：目標函數（objective function）是你想讓它最大或最小的那個分數，例如總收入；線性（linear）是指式子裡只有「數字 × 變數」再相加，沒有平方、也沒有兩個變數相乘，例如 3x₁ + 2x₂；不等式是「≤」「≥」這種上限下限，例如人力用量 ≤ 20。蓋機場的例子在本週第 04 章（[連續空間的梯度上升](https://app.notion.com/p/3e6fc631b030812a99d4eb793b437690)）。 下面收起來的兩個摺疊在做什麼：第一個用白話解釋凸集合、凸函數、cᵀx 這些符號；第二個說明「求最大」「不超過上限」這些不同寫法，怎麼統一改寫成同一種標準形式，好處是求解工具只要會處理一種格式。
要先懂什麼？凸集合、凸函數、cᵀx 是什麼？ 老師說凸函數的數學定義要自己去翻 (1:53:35)，這裡補短版： - Convex set（凸集合）：集合裡任兩點連成的線段，整條都還在集合裡。圓盤、三角形是；甜甜圈不是。每條線性不等式切出一個半平面，半平面的交集還是凸的，所以 LP 的可行區域一定是凸的。 - Convex function（凸函數）：圖形像開口朝上的碗，圖形上任兩點連成的弦都在圖形上方或貼著，即 f(λa + (1−λ)b) ≤ λf(a) + (1−λ)f(b)，0 ≤ λ ≤ 1。x² 是，sin x 不是。 - 為什麼凸很重要：在凸集合上最小化凸函數，局部最低點就是全域最低點，不會像前面的 local search 那樣卡住。 - cᵀx：c 和 x 的內積寫成矩陣乘法，例 cᵀx = c₁x₁ + c₂x₂ + c₃x₃。Ax = b 是一組聯立一次方程式（線性系統），A 是 m×n 係數矩陣。老師的例子：x₁ + x₂ + x₃ = 7、2x₁ + 3x₂ + 5x₃ = 5 合起來就是 Ax = b，A 的兩列是 (1, 1, 1)、(2, 3, 5)，b = (7, 5)。x ≥ 0 表示 x 的每個分量都 ≥ 0。
它到底怎麼運作？各種變形怎麼改寫成標準形式？ - maximize cᵀx → minimize (−c)ᵀx。利潤最大就是「負的利潤」最小。 - Ax ≤ b → 每條不等式加一個 slack variable（鬆弛變數）s ≥ 0，變成 Ax + s = b。例：x₁ + 2x₂ + x₃ + 2x₄ ≤ 20 改成 x₁ + 2x₂ + x₃ + 2x₄ + s₁ = 20，s₁ ≥ 0 的意思就是「沒用完的人力」。 - Ax ≥ b → 減一個 surplus variable（剩餘變數）s ≥ 0，變成 Ax − s = b。
老師原話是什麼？ 「constraint optimization problem這本身就是一門課，也可以是一本書的內容」(1:52:31) 「convex function我不想要講它的數學定義，總之你可以自己去翻」(1:53:35)
## [1:56:12](https://www.youtube.com/watch?v=S1km7opW6rw&t=6972s) 例子：製造商排產 製造商做 4 種產品 X₁–X₄，要用 3 種資源：人力（人週）、原料 A（公斤）、原料 B（盒），每週用量有上限（下表）。設產品 i 生產 xᵢ 份，每一列就是一條線性限制，例如人力：x₁ + 2x₂ + x₃ + 2x₄ ≤ 20，另外 xᵢ ≥ 0。投影片只給資源表；老師口頭補上目標：假設產品 1 賣 100 元、產品 2 賣 50 元，依此類推，要讓總收入最大。目標和限制都是線性的，所以這是 LP。這類問題在二戰期間快速發展，後來廣泛用在經濟學和作業研究（用數學幫組織做決策）。 人週（person-week）是「一個人工作一週」的工作量，每週上限 20 人週，大約就是 20 個人做一週。 下面收起來的手算在做什麼：把問題縮小成只做兩種產品，比較所有限制圍出的區域的幾個角，找出哪種生產組合收入最高；算出來是全部做產品 1 最賺。這只是讓你看懂 LP 在問什麼，考試不會要你解。
資源X₁X₂X₃X₄每週上限
人力（人週）121220
原料 A（公斤）6532100
原料 B（盒）3491275
**注意：LP 怎麼求解本課不講，老師說那是一整個學期的最佳化導論 (2:00:11)。**
它到底怎麼運作？手算一個縮小版 LP 完整的三條資源限制（投影片 p.26）：x₁ + 2x₂ + x₃ + 2x₄ ≤ 20（人力）、6x₁ + 5x₂ + 3x₃ + 2x₄ ≤ 100（原料 A）、3x₁ + 4x₂ + 9x₃ + 12x₄ ≤ 75（原料 B），加上 xᵢ ≥ 0。目標是 maximize 100x₁ + 50x₂ + …（產品 3、4 的售價老師沒給）。 只生產 X₁、X₂（x₃ = x₄ = 0），售價用老師說的 100、50： maximize 100x₁ + 50x₂ subject to x₁ + 2x₂ ≤ 20、6x₁ + 5x₂ ≤ 100、3x₁ + 4x₂ ≤ 75、x₁ ≥ 0、x₂ ≥ 0 LP 有一個好用的性質：所有限制圍出來的可行區域是一個凸多邊形，只要有最佳解，就一定有一個落在多邊形的角上。所以把角一個個代進去比： - (0, 0)：收入 0 - (0, 10)：人力用完，收入 500 - (14.29, 2.86)：人力和原料 A 同時用完，收入 1,571.43 - (16.67, 0)：原料 A 用完，收入 1,666.67，最大 結論：售價 100、50 時，全部做產品 1 最賺（原料 B 用不完，不影響答案）。若產品 2 漲到 150，最大值換到 (14.29, 2.86) 那個角，收入 1,857.14。
老師原話是什麼？ 「很抱歉，這個是一整個學期的課，有興趣的話請去修最佳化導論」(2:00:11) 「我們在這門課裡面呢，我們就不再講怎麼求解」(2:00:18)
## [2:00:30](https://www.youtube.com/watch?v=S1km7opW6rw&t=7230s) 課堂問答：先大步後小步 同學問：重新計算時若傾向找離原本較遠的解，會不會一直被拉回原本的解（例如很寬的丘陵，遠方有一座很窄的山峰）？老師說「對也不對」：剛開始 α 設大、敢走遠；跑了很多 iteration（更新一次叫一次迭代）之後把 α 慢慢縮小，只在附近找。α 和模擬退火的溫度 T 都隨時間改變，走過去通常不會再走回來；深度學習的 learning rate 排程也是「先冒險，後保守」。同學補充「寬丘陵旁有窄山峰」這種情況，老師承認可能在兩邊來回震盪，但多半是特殊設計的問題，真實世界很少見。 模擬退火的溫度 T（本週第 02 章學過：[爬山法複習與模擬退火](https://app.notion.com/p/3e6fc631b03081a79865f701c688c1c4)，T 高時常常允許往較差的方向走，之後慢慢降溫，越來越只接受變好的移動）。震盪就是在答案兩邊跳來跳去、停不下來。 下面收起來的手算在做什麼：用最簡單的山比較幾種不同的 α，看步長太大時為什麼會來回震盪、甚至越跳越遠，以及「先大步、後小步」為什麼能又快又穩。
它到底怎麼運作？α 太大為什麼會來回震盪？ 用最簡單的山 f(x) = −x²（山頂在 x = 0）做梯度上升：∇f = −2x，所以 x ← x + α(−2x) = (1 − 2α)x。從 x = 1 出發： - α = 0.25：x → 0.5 → 0.25 → 0.125 → …，穩穩爬向山頂 - α = 1：x → −1 → 1 → −1 → …，在山頂兩側跳來跳去，永遠到不了，這就是震盪 - α = 1.5：x → −2 → 4 → −8 → …，越跳越遠，這叫發散 - α 從 1 開始、每步減半：第一步 α = 1，x → −1；第二步 α = 0.5，x → 0，到頂了 所以「先大步、後小步」前期走得快、後期停得穩。深度學習常見排程例如：前 100 個 epoch（整份訓練資料跑一遍）用 0.1，之後每 50 個 epoch 乘 0.5（0.05、0.025…）。
老師原話是什麼？ 「一開始冒險一點，後來就越來越保守」(2:03:48) 「所以這個最佳化跟我們人生的哲理是一樣的」(2:03:52) 「我覺得那個都是要特殊設計的問題才會這樣子，我們一般在做真正實體世界的最佳化的時候，是很少遇到這樣子的東西的」(2:04:43)
## Self-check
Q1. How is the gradient ∇f(x₀) related to the level set of f through x₀? Why does gradient descent move along −∇f?（中文：梯度 ∇f(x₀) 跟通過 x₀ 的等高線有什麼關係？為什麼梯度下降要沿著 −∇f 走？） **Answer**: ∇f(x₀) is orthogonal to the level set f(x) = c through x₀ and points in the direction of maximum rate of increase: for a small displacement, f increases more along the gradient than in any other direction. So −∇f is the direction of steepest decrease, and minimization uses x ← x − α∇f(x). 中文：梯度 ∇f(x₀) 垂直於通過 x₀ 那條等高線 f(x)=c；而且沿著梯度方向走一小步，f 上升的量比往任何其他方向都多，所以梯度是上升最快的方向。反過來，−∇f（梯度的反方向）就是下降最快的方向，所以要找最小值時，更新式要寫成 x ← x − α∇f(x)，沿著負梯度走。
Q2. Give Newton's formula for solving g(x) = 0, explain it geometrically, and do two iterations for g(x) = x² − 2 from x₀ = 1.（中文：寫出解 g(x)=0 的牛頓法公式，用幾何角度說明它在做什麼，並用它對 g(x) = x² − 2、從 x₀ = 1 開始，手算兩次。） **Answer**: xₖ₊₁ = xₖ − g(xₖ) / g′(xₖ). The tangent to g(x) at xₖ intersects the x-axis at xₖ₊₁, which is expected to be closer to the root (Newton's method of tangents). With g′(x) = 2x: x₁ = 1 − (−1)/2 = 1.5; x₂ = 1.5 − 0.25/3 ≈ 1.4167 (√2 ≈ 1.4142). 中文：牛頓法的公式是 xₖ₊₁ = xₖ − g(xₖ)/g′(xₖ)。幾何上，是在目前的點 xₖ 對曲線 g(x) 畫一條切線，這條切線碰到 x 軸的地方就是下一個猜測 xₖ₊₁，通常會比 xₖ 更靠近真正的根（這也是「切線法」這個名字的由來）。用 g(x) = x² − 2（求 √2）、g′(x) = 2x、從 x₀ = 1 開始算兩次：第一次 x₁ = 1 − (−1)/2 = 1.5；第二次 x₂ = 1.5 − 0.25/3 ≈ 1.4167，已經非常接近真正答案 √2 ≈ 1.4142。
Q3. How is Newton's method used to find a maximum or minimum of f? Define the Hessian and compare with steepest-ascent hill climbing.（中文：牛頓法怎麼被拿來找 f 的最大值或最小值？定義 Hessian 矩陣，並跟 steepest-ascent hill climbing 比較。） **Answer**: An optimum needs ∇f(x) = 0, so g(x) becomes ∇f(x) and g′ becomes the second derivatives: x ← x − Hf⁻¹(x)∇f(x), where the Hessian has elements Hᵢⱼ = ∂²f/∂xᵢ∂xⱼ. Steepest ascent, x ← x + α∇f(x), uses only the gradient and a hand-chosen step size α; Newton's method uses second-order information to set direction and step together, so it needs fewer iterations, but each one must invert an n×n Hessian. Both can get stuck at local maxima, ridges, and plateaux. 中文：要找極值，就是要找讓梯度等於零的點（∇f(x)=0），所以把牛頓法公式裡的 g(x) 換成 ∇f(x)，g′ 換成二次微分，得到 x ← x − Hf⁻¹(x)∇f(x)，其中 Hessian 矩陣的元素是 Hᵢⱼ = ∂²f/∂xᵢ∂xⱼ。相比之下，steepest-ascent hill climbing（最陡上升爬山法）只用一次微分（梯度），公式是 x ← x + α∇f(x)，步長 α 要自己設；牛頓法多用了二次微分（Hessian）的資訊，能同時決定方向和步長，所以需要的迭代次數比較少，但每一步都要對 n×n 的 Hessian 矩陣求反矩陣，比較貴。兩種方法一樣會卡在 local maxima、ridges、plateaux。
Q4. Define constrained optimization and linear programming. Give the standard form of an LP and its relation to convex optimization.（中文：定義 constrained optimization 和 linear programming。寫出 LP 的標準形式，並說明它跟 convex optimization 的關係。） **Answer**: In constrained optimization, solutions must satisfy hard constraints on the values of the variables. In linear programming, the constraints are linear inequalities forming a convex set and the objective is also linear. Standard form: minimize cᵀx subject to Ax = b, x ≥ 0; maximization and Ax ≤ b or Ax ≥ b can be rewritten into it. LP is a special case of convex optimization, where the constraint region can be any convex region and the objective any function convex within it. 中文：constrained optimization（限制最佳化）是指解必須滿足變數上的一些硬性限制。linear programming（線性規劃）是其中一種：限制是線性不等式、圍出一個凸集合（convex set），目標函數也是線性的。標準形式是：在 Ax = b、x ≥ 0 的限制下 minimize（最小化）cᵀx；maximize，或限制寫成 Ax ≤ b、Ax ≥ b 的各種變形，都可以改寫成這個標準形式。線性規劃是更一般的 convex optimization（凸最佳化）的特例，凸最佳化允許限制區域是任何凸區域、目標函數是任何在該區域內為凸的函數。
讀完了嗎？下一章：[06 部分觀察與線上搜尋（2:16–2:29）](https://app.notion.com/p/3e6fc631b0308161a1a1c05842cdd2c7)｜回到週頁：[W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62)