[人工智慧導論](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) ## 重點 - 梯度 ∇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） - **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) - **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） - **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） - **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） - **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） - **Constrained optimization**: "A constrained optimization problem is constrained if solutions must satisfy some hard constraints on the values of the variables."（Ch4 p.24） - **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） - **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） ## [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) ![Ch4 p.21：碗狀曲面 z = f(x₁, x₂) 被水平面 z = c 切一刀，切口投影到地面就是等高線（level set）；梯度 ∇f(x₀) 垂直於等高線](file-upload://3e7fc631-b030-814a-bd34-00b26e08bdcb) **注意：老師口頭說「你要往切線的這個方向走，你的海拔高度會增加最快」(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ₖ)。通常更新兩三次就非常接近真正的根。 ![Ch4 p.22：在 xₖ 畫切線，切線和 x 軸的交點是 xₖ₊₁，再畫一次得到 xₖ₊₂，很快逼近真正的根](file-upload://3e7fc631-b030-81f2-a24c-00b25ed40306)
它到底怎麼運作？公式怎麼推，手算一次 √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)。 **注意：老師口頭把牛頓法說成用來決定「最好的 α」、也就是沿梯度要走多遠的方法 (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（學習率）。
要先懂什麼？深度學習的 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、限制改成 ≥ 或 ≤ 的變形都能改寫成這個形式。
要先懂什麼？凸集合、凸函數、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。這類問題在二戰期間快速發展，後來廣泛用在經濟學和作業研究（用數學幫組織做決策）。
資源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 排程也是「先冒險，後保守」。同學補充「寬丘陵旁有窄山峰」這種情況，老師承認可能在兩邊來回震盪，但多半是特殊設計的問題，真實世界很少見。
它到底怎麼運作？α 太大為什麼會來回震盪？ 用最簡單的山 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? **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). 中文重點：梯度垂直等高線、指向上升最快；要最小化就往負梯度走。
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. **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 軸的交點就是下一個猜測；兩步就到 1.4167。
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. **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. 中文重點：g 換成 ∇f、g′ 換成 Hessian；牛頓法步數少但每步貴，一樣會卡住。
Q4. Define constrained optimization and linear programming. Give the standard form of an LP and its relation to 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. 中文重點：LP ＝ 線性目標＋線性限制，是凸最佳化的特例；標準形式 min cᵀx, Ax = b, x ≥ 0。