📈 MAT3007 Week 1-3 Introduction to Optimization

Lithos

CSC3007 Week1 Basics

引入

“Nothing at all takes place in the universe in which some rule of maximum or minimum does not appear.” —— Euler

MAT 3007 是一门指导你从合法决策集中找出使某指标最优（最大或最小）的决策的课程。优化的核心词是：Decision(决策-变量或多变量组成的向量 x) + Objective(指标-优化目标 f = Objective Function) + Constraints(限制-现实或逻辑约束集 Ω)

最简通式：minx f(x) (subject to x ∈ Ω)

严格通式：$$\begin{aligned}\min_{x\in\mathbb R^n}\quad &f(x)\ \text{s.t.}\quad &g_i(x)\le0\ &h_j(x)=0 \end{aligned}$$ 有时也可能从离散集取值，比如 Zn

转换标准形式：1、max 加负号改成 min；2、多项不等式 g(x) ≥ y 改成 g(x) - si = y，反之亦然；3、si ≥ 0；4、没有符号限制的变量 xi 必须写作 a-b, s.t. a, b ≥ 0 形式。


术语

  • Rn 表示 n 维实数域，在其中取一段连续值会组成一维线段/二维圆域/三维球域…
  • Feasible point/solution：某一符合所有约束的决策 x∈Ω := {x ∈ Rn : g(x) ≤ 0, h(x) = 0}
  • Feasible region：即 Ω，所有可行解组成的集合
  • Optimal Solution：所有得到最优指标的可行解 x*，实际问题解个数可能为任意自然数。
  • Optimal Value：最优解对应的指标值 f(x*)，有时记作 f*
  • 如果 Ω = Rn 或 m = p = 0 就称问题为“无约束”(unconstrained)，反之就是“有约束”。
  • 分类：Linear (LP)/Nonlinear (NLP)：指标是否为 n 元一次多项式，LP 是最基础的；Continuous/Discrete aka. Integer (IP)：决策 x 取值的集是否连续。每一对在特定情况下可以互相等价转换。一般优化问题默认为连续的。
  • Ω 空称为 infeasible。min 问题中 Optimal Value为 +∞ 称为 infeasible，−∞ 称为 unbounded；max 相反。
  • inf 代表上界，sup 代表下界；inf ∅ = +∞, sup ∅ = −∞

Quick Example

在固定周长 C 的最大矩形问题中，决策是长和宽组成的 x = $\begin{bmatrix} l \ w \end{bmatrix}$；指标是 max(A = l·w)；约束是周长固定和长宽非负——$${\begin{aligned}\max_{l,w}&lw\ \ \ \ \text{s.t.}\ 2l+2w\le80;\ l,w\ge0\end{aligned}}$$

这是一个非线性优化 (NLP)，具体来说是 Constrained-Nonlinear-Continuous Optimization

相比 MAT1001 Calculus，更关心问题的建模而非只求结果


Minimizer/Maximizer

邻域的定义：open ball $B_\epsilon(y)={x\in\mathbb R^n:|x-y|<\epsilon}$ 即以 y 为中心、半径为 ε 的小邻域。x*满足以下条件时称为：

  • 局部极小值点 (local minimizer)：存在 ε>0 使 open ball 中对应的可行值 f* ≤ 邻域中所有其他 f

  • 严格局部极小值点 (strict local minimizer)：局部极小值且 x ∈ (Ω ∩ B∈(x*)){x*}（谷值唯一而非连续值）

  • 全局极小值点 (global minimizer)：属于Ω 且对应的可行值 f* ≤ 所有其他 f（严格全局极小值点类似），全局极小值点等价于 Optimal Solution。

⚠️ 不要滥用求导：f’(x) 只说明 x ∈ Stationary Point。f’’>0 为 LMin，f’’<0 为 LMax


最优解的四种情况

情况 x optimal value
Infeasible (min) Ω = ∅ 约定 f*=+∞
Unbounded below feasible x 存在 f*→-∞
Finite but unattainable feasible x 存在，不存在 feasible x*，如超出约束/边界缺失或x→±∞ f* ∈ R
Finite and attainable 存在 feasible x* f* ∈ R，且f(x*) = f*

inf A = −∞ if A is unbounded below

supA = +∞ if A is unbounded above（最大值问题）



建模

生产问题

公司生产两种合金，要决定各生产多少：

\ Steel Iron Copper Profit
Alloy 1 1 0 1 1
Alloy 2 0 2 1 2
Available 100 200 150

Coefficients of LP：0, 1, 100, 200, 150……

Decision Var.：x = [x1, x2]⊤（x1, x2 为 Alloy1/2 的生成量）

Objective Func.：Profit f(x) = x1 + 2x2

Constraint：x1 ≤ 100，x2 ≤ 100，x1 + x2 ≤ 150，x1, x2 ≥ 0

$$\boxed{ \begin{aligned} \max_{x_1,x_2}\quad &x_1+2x_2\ \text{s.t.}\quad &x_1\le100\ &2x_2\le200\ &x_1+x_2\le150\ &x_1,x_2\ge0 \end{aligned}}$$


Shortest Path

对于一个有向图 (左下)：G=(V,E)，每条边 (i, j) ∈ E 都有长度 wij ≥ 0。从 S 到 T 走哪条路，总长度最短？

📈 MAT3007 Week 1-3 Introduction to Optimization 相关图片

建模时不能直接表示复杂对象，而是把复杂决策拆成很多简单变量。比如“走某条路”在数学上过于模糊，但如果对于每条 (i, j) ∈ E 定义：xij ∈ {0, 1}（不使用/使用该边）于是“一条路径”就被编码成了一大堆 0/1，这里的决策变量就被转化为一个 11 维向量。

目标函数就是：$$\min_x \sum_{(i,j)\in E}w_{ij}x_{ij}$$（典型的 0/1建模）

约束：路径不能乱选，一定要“连续”且出现 S 和 T 恰好一次。换句话说，S 只出，T 只进，其余节点进出次数相等——

📈 MAT3007 Week 1-3 Introduction to Optimization 相关图片

线性目标函数，flow constraints 也是线性，但变量是离散的，所以这是这是整数 (离散) 线性优化 Integer Linear Optimization。


另一个 0/1建模问题 (右上) 对一个 G，选最少的节点，使每条边至少有一个端点被选中。

决策变量：xi ∈ {0, 1}（不使用/使用该边）

目标函数：$$\min\sum_{i\in V}x_i$$

约束：对于任意边 (i, j) ∈ E 必须选一个端点，即 xi + xj ≥ 1

显然这也是 Integer Linear Optimization。




CSC3007 Week2 Linear Algebra

Matrix version of LP

Matrix Notion: Standard form of LP ——

$$ \boxed{ \begin{aligned} \min\quad &c^Tx\\ \text{s.t.}\quad &Ax=b,\\ &x\ge0. \end{aligned}} $$

  • 无常数线性多项式的向量的**内积 (点积)**表示：cTx = [c1, … cn] [x1, … xn]T = c1x1 + … + cnxn

  • 矩阵 x 列向量 = 矩阵的每一行分别和向量做点积，结果是列向量：$(Ab)i=\sum{k=1}^n a_{ik}b_k$

  • Ax = b 中，原本一条限制转为 A 的一行；一个 decision variable 就是 A 的一列——

    比如 x1 ≤ 42; 2x2 ≤ 400; x1 + x2 ≤ 150

$$ A= \begin{bmatrix} 1&0\\ 0&2\\ 1&1 \end{bmatrix}, \qquad x= \begin{bmatrix} x_1\\x_2 \end{bmatrix}, \qquad b= \begin{bmatrix} 100\\200\\150 \end{bmatrix}. $$

  • A ∈ Rmxn 说明 A 矩阵 m 行 n 列

  • b = Ax ∈ Rm 代表限制 (变量上限)

    相当于有 n 个变量；优化目标是它们的线性加权 (cT) 和；有 m 条线性方程限制它们；变量还必须非负。



Linear Algebra Basics

Transpose (转置)：把矩阵沿主对角线翻一下，也就是“行变列、列变行”—— (AT)ij = Aji

  • (AB)T = BTAT；(A+B)T = AT + BT
  • Symmetric Matrix (对称矩阵)：转置之后还是自己，即沿主对角线两边镜像对称

Inner Product (内积/点积)：两个同维向量对应位置相乘再相加

  • xTy = x1y1 + x2y2 + … + xnyn，结果是一个数 (scalar)，不是 vector
  • xTy = 0 ⇒ x 与 y orthogonal (正交/垂直)

Norm (范数 / 向量长度)：衡量 vector 的“大小/长度”，写成 ||x||

  • L2 norm：||x||2 = √(x12+ … + xn2)，即欧氏距离。||x||22 = xTx
  • L1 norm：||x||₁ = |x₁| + … + |xₙ|
  • L∞ norm：||x||∞ = max |xᵢ|

Matrix Multiplication：A 是 m×n，B 是 n×p，才能计算 AB：(m×n)(n×p) → (m×p)

  • (AB)ij = A 的第 i 行 · B 的第 j 列——通常 AB ≠ BA，所以矩阵乘法不能随便换顺序

Linear Independence (线性无关)：一组向量中，没有任何一个能由其他向量线性组合出来

Span (张成空间)：一组向量通过“随便乘系数再相加” (线性组合 LC) 能够制造出来的所有向量的集合

  • 比如 span{[1, 2]T, [0, 1]T} = R2，n 维空间 Rn 至少需要 n 个线性无关的向量张成——

  • 这样的向量集合称为 Basis (基)：描述整个空间所需要的一套“不重复的基本方向”

Rank (秩)：矩阵中有多少个独立的方向；等价于 线性独立列/行 的最大数量

  • 对于 Am×n，rank(A) ≤ min(m,n)
  • rank(A) = rank(AT)；rank(AB) ≤ min(rank(A), rank(B))
  • Full rank (满秩)：rank 已经达到可能的最大值 (m 和 n 的较大值)

Identity Matrix (单位矩阵)：矩阵的“1”，写作 I；主对角线全是 1，其他位置都是 0

  • AI = IA = A

Inverse（逆矩阵）：矩阵版本的“倒数”；AA−1 = A−1A = I。所以 A−1 可理解成撤销 A 做的线性变换

  • A 是 n×n square matrix + full rank 才可逆

  • (A−1)−1 = A；(AB)−1 = B−1A−1

  • Orthogonal Matrix (正交矩阵)：各列都是互相垂直、长度为 1 的 vectors

    ATA = AAT = I，所以 A−1 = AT

    ⚠️ 2维方阵取逆公式：

    $$ A^{-1}={{1}\over{ad-bc}}\begin{pmatrix}d&-b\\-c&a\end{pmatrix} $$

3 维方阵取逆公式：

$$ \boxed{A^{-1}={{1}\over{a(ei-fh)-b(di-fg)+c(dh-eg)}}\begin{pmatrix}ei-fh & ch-bi & bf-ce\\fg-di & ai-cg & cd-af\\dh-eg & bg-ah & ae-bd\end{pmatrix}} $$

PSD/SD (半正定/正定矩阵)：PSD 对任意 x 有 xTAx ≥ 0；PD 对任意 非 0 x 有 xTAx > 0

  • ATA 和 AAT 一定是 PSD

⚠️ 行列式 det(A) ≠ 0 ⇔ A 可逆 ⇔ 如果 A 为方阵，满秩且rank(A) = n ⇔ A 的 n 个 columns 和 rows 线性无关 ⇔ Ax = 0 只有零解 x = 0 ⇔ 对任意 b，Ax = b 有唯一解 ⇔ A 的 columns 构成 Rⁿ 的一个 basis

  • det(AB) = det(A)det(B)、det(AT) = det(A)、det(A−1) = 1/det(A)、det(I) = 1


Machine Learning & Vector Machine

Support Vector Machine 支持向量机：一个机器学习问题怎么转为优化问题

ML 中的 sample 即将某对象的各种 numerical features 打包成向量 x

一个 training sample (Supervised Learning) 就是 (xi, yi) 其中 y 代表这个实例的 (分类) 答案

hard-margin SVM

假设现在只有两个 features，对象可以画成平面上的点，现在想找一条直线 (linear classifier) 把两个类型分开，两类答案记作 y = 1 和 y = -1

直线 l(x) = ωTx + b = 0 ⇔ ω1x1 + ω2x2 + b = 0

在 SVM optimization 里，ω 和 b 是决策变量，给定一些 (xi, yi) 作为训练样本

Find ω, b s.t. yi (ωTxi + b) ≥ 1，(feasibility problem：min ω, b 优化问题的特殊情况)

SVM 想让分类尽量分宽 (边界冗余最大)，规定人为边界 ωTx + b = -1 (type1 附近) 和 ωTx + b = 1 (type-1 附件)，中间的最优 classifier 就是 ωTx + b = 0，它距离两个边界有相等的 margin = 2/||ω||，显然要 maximize margin，即——

minω, b ||ω||2/2 s.t. yi (ωTxi + b) ≥ 1


soft-margin SVM

Hard-margin SVM 有一个很强的要求：每个点都必须被正确分开，而且在 margin 外面。

如果任意直线都不能完美分开就属于 non-linearly separable / non-separable data

只能允许犯错，但犯错要付代价 (Hinge loss)

Hinge loss = max{0, 1 − yi(wᵀxi+b)} 处罚所有不满足 yi (ωTxi + b) ≥ 1，即进入 margin 区域的点——比如落在 l(x) 上罚 1。可理解为这个 sample 离“hard-margin 合格线”还差多少——

minω, b ||ω||2/2 + Σi max{0, 1 − yi (wᵀxi + b)}

s.t. yi (ωTxi + b) ≥ 1

这是一个 unconstrained + nonlinear + continuous Optimization


Linear-fication of SVMs

min Σiti s.t. ti = maxi{a, b} 可以宽松写作 ti ≥ maxi{a, b}，进一步写成 s.t. ti ≥ a AND ti ≥ b。

有时候不需要用 constraint 强迫相等；objective 自己会把 inequality 推到边界。

min abs(f) 可以宽松写作 f ≤ t, -f ≤ t s.t. t ≥ 0



Linear-fication

LP：Objective function 和所有 constraints 都必须对决策变量是线性的。

  • 即，它们可以写作线性多项式等式或不等式 (ωTx ≥ b 或 ωTx = b)

类似于 SVM 的例子，我们通常想把 NLP 转为更简单的 LP：

$$ \boxed{ \begin{aligned} \min\quad &c^Tx\\ \text{s.t.}\quad &Ax=b,\\ &x\ge0. \end{aligned}} $$

要求 Amxn full row rank (行独立) 且 m < n (限制方程数量少于决策变量数的宽阵)，故 rank(A) = m

  • 因为如果多元线性方程组数量 ≥ 变量数要么直接解出答案要么解不出 (不属于优化问题)

⚠️ 转换为标准 LP：

1、max 加负号改成 min；

2、多项不等式 aᵀx ≤ b 改成 g(x) + si = b (si ≥ 0)，反之亦然；

3、xi ≤ 0 改成 xi = -yi, yi ≥ 0

4、没有符号限制的变量 (free var.) xi 必须写作 a-b, s.t. a, b ≥ 0 形式。


Maximin & Minimax

空管想要最大化 n 架客机的最短降落时间间隔：maximize min{tj+1−tj}

Linear-fication：Def ∆ = minj=1,…,n-1 {tj+1−tj}，宽松 ∆ ≤ tj+1−tj，然后 max ∆ 即可

和 SVM 中 max 的处理方式相对应：

Minimax (soft-bound SVM)：min maxᵢ fᵢ(x) ——

min t s.t. t ≥ fᵢ(x), ∀i

“t 在所有东西上面，然后往下压”

Maximin (ATC problem)：max minᵢ fᵢ(x) ——

max t s.t. t ≤ fᵢ(x), ∀i

“t 在所有东西下面，然后往上顶”


类似的，绝对值 |wᵀx+b| 相当于 max{wᵀx+b, -wᵀx-b}

比如 min abs(f) 可以宽松写作 f ≤ t, -f ≤ t s.t. t ≥ 0

⚠️ 如果你希望 t = f(x) 但放宽到 t ≥ f(x)，那么必须有某种原因迫使 t 变小，例如 min t。


LFP (Linear Fractional Programming)

min (cTx+d)/(eTx+a) s.t. Ax≤b, eᵀx+a > 0（显然不是 LP）

定义：y = x/(eTx+a)、z = 1/(eTx+a)

因为 y = zx，所以 (cTx + d)/(eTx + a) = z(cTx + d) = cTy + dz

Ax ≤ b ≡ zAx ≤ bz ≡ Ay - bz ≤ 0，因为 z(eTx+a) = 1 所以 eᵀy+az=1

minimize　cᵀy+dz

s.t. Ay−bz≤0, eᵀy+az=1, z≥0




CSC3007 Week3 LP: Geometry

Graphical Method

几何角度理解 Rn-LP：先把所有约束画出来，交集就是 feasible region (可行域 Ω)，目标函数是 n-1维线性点集。

以R2-LP 为例，右下图中粉色区域即满足约束的 (x1, x2) 区域，目标函数是平面上的直线。我们的目标是最大化，所以不断把这条线往数值增大的方向平移。最后一条仍碰到 feasible region 的线，就是 optimum x*，点值就是 optimum value f*。

📈 MAT3007 Week 1-3 Introduction to Optimization 相关图片

① LP feasible region 是 polyhedron (多面体) ② optimum 往往可以在 corner/vertex (边缘/角点) 找到 ③ optimum 处有一些 constraints 正好取等号


Polyhedron

多边形是可以做成 {x ∈ RN : Ax ≥ b} 形式的点集（其中 Amxn, b ∈ Rm），一种由有限 (m) 个 N-1 维线性不等式切出来的 N-维区域。

回顾：标准 LP 约束是 s.t. Ax = b, x ≥ 0

  • 它就是多边形，因为：Ax = b, x ≥ 0 ⇔ Ax ≥ b AND -Ax ≥ -b, I · x ≥ 0 (I 即单位向量)

Convex Set & Convex Combinations

Convex Set (凸集)：集合中任意两个点连一条线段，整条线段上的点都在集合里。

凸集合 S ⊆ Rn 满足对 ∀ x,y ∈ S 和 λ ∈ [0,1]，λx + (1-λ)y ∈ S 恒成立

出于直觉，我们刚才⚠️ 用 Ax ≥ b 约束出的多边形一定是凸集：

  1. 理解：线性约束 aiTx ≥ bi 对应一条直线及其一侧的半平面，如果围成凹多边形，其豁口 (凹部) 至少由 k 条约束构成 (k ≥ 2)，而它们作为直线继续延伸而不可能在凹口处停止，对应半平面约束将凹口某侧的部分区域排除掉。因此所有约束同时成立 (交集-AND) 后，可行域必然凸
  2. 这就是为什么 LP 一定天然是 Convex Optimization

Convex Combination (凸组合)：对几个点做“加权平均”。

对 ∀ x1, … xn 和 λ1, … λn ≥ 0 满足 ∑ λi = 1，将 ∑ λixi 称为 x 的凸组合


Extreme Point

Extreme Point，即 vertex/角点：相当于多边体的顶点。

角点 x 不能由可行域中两个不同点的凸组合得到—— ∀ y≠z ∈ Ω, λ ∈ [0, 1]：x ≠ λy + (1-λ)z



Basic Solution

对于矩阵形式的 LP 的约束条件 Ax = b，要求 Amxn ：1、full row rank (行独立)；2、m < n (限制方程数量少于决策变量数的宽阵) 故 rank(A) = m

  • 如果多元线性方程组数量 ≥ 变量数，可直接解出答案/可行域为∅ (不属于优化问题)
  • 如果 rows 不独立
    • 要么某个 constraint 是 redundant → 删除；
    • 要么 constraints 互相矛盾 → 根本没有 feasible solution。

把 A 看成 n 个列向量：A = [ A₁ A₂ A₃ … Aₙ ]，那么 Ax = A₁x₁ + A₂x₂ + … + Aₙxₙ = b

  1. 选 m 个线性独立列 AB(1)~B(m)，称为 basic columns (基列)，对应 xB(1)~B(m) 为基变量

    B(1)~B(m) 为基序数 (basic indices)

  2. 将剩下 n-m 个 non-basic 变量全部设成 0

  3. 解 AB xB = b，因为 m 个 m-维基列独立，AB 基矩阵可逆：xB = AB-1 b

    于是得到一个 Basic Solution (BS)，其最多含有 m 个非 0 变量 (解出来的基变量可能等于 0——degenerate case)

⚠️ 某一 LP 最多有 C(n,m) = $n \choose m$ = n!/(m!(n-m)!) 种 BS (必然有限)，存在不独立列时可能更少。

BFS (Basic Feasible Solution)：Basic Solution 且 x ≥ 0 (满足所有剩余约束)


Extreme Points & BFS

几何和代数概念的对应：LP 根本不必用 Graphic Method 画图找 vertex，Extreme points 等价于 BFS。

例题：

📈 MAT3007 Week 1-3 Introduction to Optimization 相关图片

$$ Ax=b \qquad A = \begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{bmatrix}, \qquad b = \begin{bmatrix} 100 \\ 200 \\ 150 \end{bmatrix}. $$

m=3, n=5，我们随便选三个列，以 1, 2, 3 列为例：

$$ x_B=A_B^{-1}b \qquad A_B= \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&1&0 \end{pmatrix}, \qquad b= \begin{pmatrix} 100\\200\\150 \end{pmatrix} $$

关键技巧：

⚠️ 看到 B-1b，别硬求 B-1，直接把它看成解方程 Bx=b。

$$ \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&1&0 \end{pmatrix} \begin{pmatrix} u\\v\\w \end{pmatrix} = \begin{pmatrix} 100\\200\\150 \end{pmatrix} $$

  • 即 u + w = 100; 2v = 200; u + v = 150 → xB = (50, 100, 50)T

  • 剩余变量被我们设为 0，所以 BS = (x1, x2, x3, s1, s2) = (50, 100, 50, 0, 0)，变量均 ≥ 0，故这就是一个 BFS。

如此，根据选择的独立列不同，可以解出 8 个 BS ({1, 3, 5} 和 {2, 4, 5} 不独立不可解 BS)

  • 其中三个 BS 存在负数参数，不属于 BFS，它们正好对应了 Graph 中直线的三个在可行域外的交点 (∉ 所有条件的交集)

📈 MAT3007 Week 1-3 Introduction to Optimization 相关图片


Fundamental Thm. of LP

对于标准 LP，如果 A 行满秩 m：

  1. 若 Ω ≠ ∅，一定存在 BFS

  2. 若存在最优解，一定存在一个 BFS 最优解

    故而找最优解只需看有限个 BFS



Simplex Method

comments powered by Disqus