Notation

符号 含义
∥x∥\| \boldsymbol{x} \| 向量 x\boldsymbol{x} 的范数
Rn\mathbb{R}^n nn 维实向量空间
∇f\nabla f 函数 ff 的梯度向量
∇2f\nabla^2 f 函数 ff 的 Hesse 矩阵（二阶导数矩阵）
min⁡\min / max⁡\max 最小化 / 最大化
s.t.\mathrm{s.t.} 受约束于（subject to）
inf⁡\inf / sup⁡\sup 下确界（infimum） / 上确界（supremum）
arg⁡min⁡\arg\min 使函数取得最小值的参数值
θ∈[0,1]\theta \in [0,1] 凸组合系数
η\eta 学习率（步长参数）
x≥0\boldsymbol{x} \geq \boldsymbol{0} 向量 x\boldsymbol{x} 的每个分量非负
δk=xk+1−xk\delta_k = x_{k+1} - x_k 参数迭代差值向量
yk=∇f(xk+1)−∇f(xk)y_k = \nabla f(x_{k+1}) - \nabla f(x_k) 梯度差值向量
L(x,λ,ν)L(x, \lambda, \nu) 拉格朗日函数
g(λ,ν)g(\lambda, \nu) 拉格朗日对偶函数
p∗p^* / d∗d^* 原始问题 / 对偶问题的最优值
Gk\boldsymbol{G}_k / Bk\boldsymbol{B}_k 拟牛顿法中 Hesse 矩阵逆 / 原矩阵的近似
⪰\succeq 广义不等式
dom\mathrm{dom} 函数的定义域
α\alpha / λ\lambda / ν\nu 标量参数（步长、拉格朗日乘数等）
H\boldsymbol{H} Hesse 矩阵
dk\boldsymbol{d}_k 搜索方向向量
BtB_t 随机梯度下降中的小批量样本集合
f∈C2f \in C^2 函数 ff 二阶连续可微

最优化问题的数学基础

范数

若实值函数∥⋅∥:Rn→Rn\| \boldsymbol{·} \|: \boldsymbol{R}^n \to \boldsymbol{R}^n满足以下条件:

  1. 正定性:∥x∥≥0,∀x∈Rn\| \boldsymbol{x} \| \geq 0,\forall \boldsymbol{x} \in \boldsymbol{R}^n;∥x∥=0\| \boldsymbol{x} \| = 0当且仅当x=0\boldsymbol{x = 0};
  2. 齐次性:∥αx∥=α∥x∥,∀α∈R,x∈Rn\| \alpha\boldsymbol{x} \| = \alpha\| \boldsymbol{x} \|,\forall \alpha \in \boldsymbol{R},\boldsymbol{x} \in \boldsymbol{R^n};
  3. 三角不等式:∥x+y∥≤∥x∥+∥y∥,∀x,y∈Rn\|\boldsymbol{x + y}\| \leq \|\boldsymbol{x}\| + \| \boldsymbol{y} \|,\forall \boldsymbol{x},\boldsymbol{y} \in \boldsymbol{R}^n.
    则∥⋅∥\| \boldsymbol{·} \|称Rn\boldsymbol{R}^n上的范数。

Hesse矩阵

设f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}是一个二阶连续可微函数，则:

∇2f(x0)=[∂2f∂x12∂2f∂x1∂x2⋯∂2f∂x1∂xn∂2f∂x2∂x1∂2f∂x22⋯∂2f∂x2∂xn⋮⋮⋱⋮∂2f∂xn∂x1∂2f∂xn∂x2⋯∂2f∂xn2]\boldsymbol{\nabla^2}f(\boldsymbol{x_0}) = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{bmatrix}

称为点x0=(x1,x2,…,xn)\boldsymbol{x_0} = (x_1, x_2, \dots, x_n)处的 Hesse 矩阵。

锥

一个非空集合C⊆RnC \subseteq \mathbb{R}^n称为锥，如果满足:

∀x∈C, ∀λ≥0,λx∈C\forall \boldsymbol{x} \in C, \, \forall \lambda \geq 0, \quad \lambda \boldsymbol{x} \in C

即对任意点x∈C\boldsymbol{x} \in C和非负标量λ\lambda，其缩放结果λx\lambda \boldsymbol{x}仍属于CC。

半空间

设a∈Rn\boldsymbol{a} \in \boldsymbol{R}^n且a≠0,b∈R\boldsymbol{a} \neq 0,b \in \boldsymbol{R}，则集合

{X∣aT>b,X∈Rn}\{X | \boldsymbol{a}^T > b,X \in \boldsymbol{R}^n\}

称为Rn\boldsymbol{R}^n的半空间。

凸集

对于集合C⊆RnC \subseteq \mathbb{R}^n，若满足:

∀x1,x2∈C, ∀θ∈[0,1],θx1+(1−θ)x2∈C\forall \boldsymbol{x}_1, \boldsymbol{x}_2 \in C,\ \forall \theta \in [0,1], \quad \theta\boldsymbol{x}_1 + (1-\theta)\boldsymbol{x}_2 \in C

则称CC为凸集。

凸锥

集合C⊆RnC \subseteq \mathbb{R}^n称为凸锥，如果它既是锥又是凸集。等价定义为:

∀x1,x2∈C, ∀θ1,θ2≥0,θ1x1+θ2x2∈C\forall \boldsymbol{x}_1, \boldsymbol{x}_2 \in C, \, \forall \theta_1, \theta_2 \geq 0, \quad \theta_1 \boldsymbol{x}_1 + \theta_2 \boldsymbol{x}_2 \in C

即对任意两点x1,x2∈C\boldsymbol{x}_1, \boldsymbol{x}_2 \in C和非负标量θ1,θ2\theta_1, \theta_2，其线性组合仍属于CC。

凸集分离定理

设 C1C_1 和 C2C_2 是 Rn\mathbb{R}^n 中两个非空集合，H={X∣pTX=α}H = \{ X \mid p^T X = \alpha \} 为超平面，如果对 ∀X∈C1\forall X \in C_1 都有 pTX≥αp^T X \geq \alpha，对 ∀X∈C2\forall X \in C_2，都有 pTX≤αp^T X \leq \alpha（或情形恰好相反），则称超平面 HH 分离集合 C1C_1 和 C2C_2。

凸函数

设函数f:C→Rf: C \to \mathbb{R} 定义在凸集CC 上，若满足:

∀x1,x2∈C, ∀θ∈[0,1],f(θx1+(1−θ)x2)≤θf(x1)+(1−θ)f(x2)\forall \boldsymbol{x}_1, \boldsymbol{x}_2 \in C,\ \forall \theta \in [0,1], \quad f(\theta\boldsymbol{x}_1 + (1-\theta)\boldsymbol{x}_2) \leq \theta f(\boldsymbol{x}_1) + (1-\theta)f(\boldsymbol{x}_2)

则称ff 凸函数。

凸函数的判定

定理1 设 f:C⊆Rn→R1f: C \subseteq \mathbb{R}^n \to \mathbb{R}^1 是可微函数，其中 CC 为凸集，则
(1) ff 为凸函数的充要条件是 ∀X1,X2∈C\forall X_1, X_2 \in C，都有

f(X2)≥f(X1)+∇f(X1)T(X2−X1);f(X_2) \geq f(X_1) + \nabla f(X_1)^T (X_2 - X_1);

(2) ff 为严格凸函数的充要条件是 ∀X1,X2∈C\forall X_1, X_2 \in C 且 X1≠X2X_1 \neq X_2，都有

f(X2)>f(X1)+∇f(X1)T(X2−X1).f(X_2) > f(X_1) + \nabla f(X_1)^T (X_2 - X_1).

定理2 设 f:C⊆Rn→R1f: C \subseteq \mathbb{R}^n \rightarrow \mathbb{R}^1 是二次可微函数，CC 为非空开凸集，则 ff 为 CC 上凸函数的充要条件是 Hesse矩阵 ∇2f(X)\nabla^2 f(X) 在 CC 上任意点均半正定。

次梯度

如果一个函数不可导，那如何用那些梯度方法呢？对于这类函数，我们引进了次梯度(Subgradient)的概念。对于一个凸实值函数f:Rn→Rf:\mathbb{R}^n \to \mathbb{R}和向量g∈Rn\boldsymbol{g} \in \mathbb{R}^n,如果对于任意的y\boldsymbol{y}，都有

f(y)≥f(x)+gT(y−x)f(\boldsymbol{y})≥f(\boldsymbol{x})+\boldsymbol{g}^T(\boldsymbol{y}−\boldsymbol{x})

那么称g\boldsymbol{g}是一个ff在x\boldsymbol{x}点处的次梯度。

线性规划

线性规划模型的一般形式

为了讨论一般的线性规划问题的求解，我们首先给出线性规划模型的一般形式如下:

min⁡ f(x1,x2,…,xn)=c1x1+c2x2+⋯+cnxn\min \, f(x_1, x_2, \ldots, x_n) = c_1x_1 + c_2x_2 + \cdots + c_nx_n

s.t.{a11x1+a12x2+⋯+a1nxn=(≥,≤)b1,a21x1+a22x2+⋯+a2nxn=(≥,≤)b2,⋮am1x1+am2x2+⋯+amnxn=(≥,≤)bm,x1,x2,…,xn≥0.\text{s.t.} \quad \begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n =(\geq,\leq) b_1, \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n =(\geq,\leq) b_2, \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n =(\geq,\leq) b_m, \\ x_1, x_2, \ldots, x_n \geq 0. \end{cases}

线性规划模型的标准形式

一般线性规划问题总可以写成下列标准形式:

min⁡∑j=1ncjxjs.t.∑j=1nαijxj=bi,i=1,2,…,m,xj≥0,j=1,2,…,n.\begin{array}{l} \min & \sum_{j = 1}^n c_{j}x_{j} \\ \mathrm{s.t.} & \sum_{j = 1}^n \alpha_{ij}x_{j} = b_{i},i = 1,2,\dots,m, \\ & x_{j} \geq 0,j = 1,2,\dots,n. \end{array}

或用矩阵表示:

min⁡cxs.t.Ax=b,x≥0.\begin{array}{l} \min & \boldsymbol{cx} \\ \mathrm{s.t.} & \boldsymbol{Ax = b}, \\ & \boldsymbol{x} \geq \boldsymbol{0}. \end{array}

其中A\boldsymbol{A}是m×nm × n矩阵 ，c\boldsymbol{c} 是 nn 维行向量 ，b\boldsymbol{b} 是 mm 维列向量。

单纯形法

基本单纯形法解线性规划问题示例

无约束优化算法

本节考虑如下无约束优化问题:

min⁡x∈Rnf(x)\begin{align} \min_{x \in \mathbb{R}^n} f(x) \end{align}

其中f(x)f(x)是Rn→R\mathbb{R}^n \to \mathbb{R}的函数。无约束优化问题是众多优化问题中最基本的 问题，它对自变量 xx 的取值范围不加限制，所以无需考虑 xx 的可行性．

线搜索方法

设目标函数为f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R}，当前迭代点为xk∈Rnx_k \in \mathbb{R}^n，搜索方向为dk∈Rnd_k \in \mathbb{R}^n（通常为下降方向，即∇f(xk)⊤dk<0\nabla f(x_k)^\top d_k < 0）。线搜索算法的目标是寻找步长α>0\alpha > 0，使得迭代更新

xk+1=xk+αdkx_{k+1} = x_k + \alpha d_k

能够使f(xk+1)f(x_{k+1})相对于f(xk)f(x_k)充分减小。

Armijo 准则

设k=0,1,2,…k = 0,1,2,\dots为第kk次迭代， dkd^k 是点 xkx^k 处的下降方向，若

f(xk+αdk)≤f(xk)+c1α∇f(xk)Tdk,f(x^k + \alpha d^k) \leq f(x^k) + c_1 \alpha \nabla f(x^k)^T d^k,

则称步长 α\alpha 满足 Armijo 准则，其中 c1∈(0,1)c_1 \in (0, 1) 是一个常数。

在优化算法的实现中，寻找一个满足 Armijo 准则的步长是比较容易的，一个最常用的算法是 回退法。给定初值 α^\hat{\alpha}，回退法通过不断以指数方式缩小试探步长，找到第一个满足 Armijo 准则 (6.1.2) 的点。具体来说，回退法选取

αk=γj0α^,\alpha_k = \gamma^{j_0} \hat{\alpha},

其中

j0=min⁡{j=0,1,⋯∣f(xk+γjα^dk)≤f(xk)+c1γjα^∇f(xk)Tdk},j_0 = \min\left\{j = 0, 1, \cdots \mid f(x^k + \gamma^j \hat{\alpha} d^k) \leq f(x^k) + c_1 \gamma^j \hat{\alpha} \nabla f(x^k)^T d^k\right\},

参数 γ∈(0,1)\gamma \in (0, 1) 为一个给定的实数。

梯度类算法

梯度下降法（Gradient Descent, GD）和随机梯度下降法（Stochastic Gradient Descent, SGD）是用于优化目标函数的迭代算法，其核心思想是通过计算梯度更新参数以逼近最小值。

梯度下降法

设目标函数为整个训练集的平均损失:

J(θ)=1N∑i=1NL(θ;xi,yi),J(\theta) = \frac{1}{N} \sum_{i=1}^{N} L(\theta; x_i, y_i),

其中 θ\theta 为模型参数，NN 为样本总数，L(θ;xi,yi)L(\theta; x_i, y_i) 为第 ii 个样本的损失函数。在每次迭代中，GD 计算目标函数关于 θ\theta 的梯度，并按负梯度方向更新参数:

θt+1=θt−η⋅∇J(θt)=θt−η⋅1N∑i=1N∇L(θt;xi,yi),\theta_{t+1} = \theta_t - \eta \cdot \nabla J(\theta_t) = \theta_t - \eta \cdot \frac{1}{N} \sum_{i=1}^{N} \nabla L(\theta_t; x_i, y_i),

其中 η>0\eta > 0 为学习率，∇J(θt)\nabla J(\theta_t) 表示目标函数在 θt\theta_t 处的梯度。

随机梯度下降法

随机梯度下降法每次迭代仅随机选取一个样本 (xit,yit)(x_{i_t}, y_{i_t}) 计算梯度，并更新参数:

θt+1=θt−η⋅∇L(θt;xit,yit),\theta_{t+1} = \theta_t - \eta \cdot \nabla L(\theta_t; x_{i_t}, y_{i_t}),

其中 iti_t 从 {1,2,…,N}\{1, 2, \ldots, N\} 中均匀随机采样。若使用大小为 mm 的小批量样本（Mini-batch SGD），则更新公式为:

θt+1=θt−η⋅1m∑i∈Bt∇L(θt;xi,yi),\theta_{t+1} = \theta_t - \eta \cdot \frac{1}{m} \sum_{i \in B_t} \nabla L(\theta_t; x_i, y_i),

其中 BtB_t 为第 tt 次迭代时随机选取的样本子集，∣Bt∣=m|B_t| = m。随机梯度下降法通过减少单次迭代的计算量，以更高的方差换取更快的收敛速度。

牛顿法

设目标函数f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}满足f∈C2(Rn)f \in C^2(\mathbb{R}^n)（即二次连续可微）。给定初始点x0∈Rnx_0 \in \mathbb{R}^n，牛顿法通过以下迭代公式生成序列{xk}k=0∞\{x_k\}_{k=0}^{\infty}以寻找ff的局部极小值:

xk+1=xk−(∇2f(xk))−1∇f(xk),k≥0,x_{k+1} = x_k - \left( \nabla^2 f(x_k) \right)^{-1} \nabla f(x_k), \quad k \geq 0,

其中∇f(xk)∈Rn\nabla f(x_k) \in \mathbb{R}^n是ff在点xkx_k处的梯度，∇2f(xk)∈Rn×n\nabla^2 f(x_k) \in \mathbb{R}^{n \times n}是ff在点xkx_k处的Hesse矩阵。该迭代持续进行，直到满足预设的收敛准则（如梯度范数∥∇f(xk)∥\|\nabla f(x_k)\|足够小或迭代步长∥xk+1−xk∥\|x_{k+1} - x_k\|足够小）。

eg.1 设目标函数为:

f(x,y,z)=x2+2y2+3z2+xy+yz+4f(x, y, z) = x^2 + 2y^2 + 3z^2 + xy + yz + 4

试找到使 f(x,y,z)f(x, y, z)最小的点(x∗,y∗,z∗)(x^*, y^*, z^*)。

1. 计算梯度（一阶导数）
梯度是一个向量，表示每个变量的变化率:

∇f=[∂f∂x∂f∂y∂f∂z]=[2x+y4y+x+z6z+y]\nabla f = \begin{bmatrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \\ \frac{\partial f}{\partial z} \end{bmatrix} = \begin{bmatrix} 2x + y \\ 4y + x + z \\ 6z + y \end{bmatrix}

2. 计算 Hesse 矩阵（二阶导数）
Hesse 矩阵是一个对称矩阵，表示函数的曲率信息:

H=[∂2f∂x2∂2f∂x∂y∂2f∂x∂z∂2f∂y∂x∂2f∂y2∂2f∂y∂z∂2f∂z∂x∂2f∂z∂y∂2f∂z2]=[210141016]H = \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} & \frac{\partial^2 f}{\partial x \partial z} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} & \frac{\partial^2 f}{\partial y \partial z} \\ \frac{\partial^2 f}{\partial z \partial x} & \frac{\partial^2 f}{\partial z \partial y} & \frac{\partial^2 f}{\partial z^2} \end{bmatrix} = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 4 & 1 \\ 0 & 1 & 6 \end{bmatrix}

具体计算演示

假设初始点为 (x0,y0,z0)=(1,1,1)(x_0, y_0, z_0) = (1, 1, 1)。

第一步:计算梯度

∇f(1,1,1)=[2(1)+14(1)+1+16(1)+1]=[367]\nabla f(1,1,1) = \begin{bmatrix} 2(1) + 1 \\ 4(1) + 1 + 1 \\ 6(1) + 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 6 \\ 7 \end{bmatrix}

第二步:计算 Hesse 矩阵的逆

Hesse 矩阵 ( H\boldsymbol{H} ) 是固定的（因为函数是二次的），直接求逆:

H=[210141016],H−1=142[23−61−612−21−27]H = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 4 & 1 \\ 0 & 1 & 6 \end{bmatrix}, \quad H^{-1} = \frac{1}{42} \begin{bmatrix} 23 & -6 & 1 \\ -6 & 12 & -2 \\ 1 & -2 & 7 \end{bmatrix}

第三步:更新参数

[x1y1z1]=[111]−142[23−61−612−21−27]⋅[367]\begin{bmatrix} x_1 \\ y_1 \\ z_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - \frac{1}{42} \begin{bmatrix} 23 & -6 & 1 \\ -6 & 12 & -2 \\ 1 & -2 & 7 \end{bmatrix} \cdot \begin{bmatrix} 3 \\ 6 \\ 7 \end{bmatrix}

计算矩阵乘法:

[23⋅3+(−6)⋅6+1⋅7−6⋅3+12⋅6+(−2)⋅71⋅3+(−2)⋅6+7⋅7]=[69−36+7−18+72−143−12+49]=[404040]\begin{bmatrix} 23 \cdot 3 + (-6) \cdot 6 + 1 \cdot 7 \\ -6 \cdot 3 + 12 \cdot 6 + (-2) \cdot 7 \\ 1 \cdot 3 + (-2) \cdot 6 + 7 \cdot 7 \end{bmatrix} = \begin{bmatrix} 69 - 36 + 7 \\ -18 + 72 - 14 \\ 3 - 12 + 49 \end{bmatrix} = \begin{bmatrix} 40 \\ 40 \\ 40 \end{bmatrix}

最终更新结果:

[x1y1z1]=[111]−4042[111]=[1−40421−40421−4042]=[242242242]≈[0.04760.04760.0476]\begin{bmatrix} x_1 \\ y_1 \\ z_1 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - \frac{40}{42} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 - \frac{40}{42} \\ 1 - \frac{40}{42} \\ 1 - \frac{40}{42} \end{bmatrix} = \begin{bmatrix} \frac{2}{42} \\ \frac{2}{42} \\ \frac{2}{42} \end{bmatrix} ≈ \begin{bmatrix} 0.0476 \\ 0.0476 \\ 0.0476 \end{bmatrix}

第四步:验证是否收敛

此时梯度为:

∇f(0.0476,0.0476,0.0476)≈[000]\nabla f(0.0476, 0.0476, 0.0476) ≈ \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}

说明已到达最小值点！

拟牛顿法

拟牛顿条件

对∇f(x)\nabla f(x)做泰勒展开可得

∇f(x)=gk+Hk(x−xk)\nabla f(x) = g_{k} + H_{k}(x-x_{k})

令x=xk+1x = x_{k+1}，则

gk+1−gk=Hk(xk+1−xk)g_{k+1} - g_{k} = H_{k}(x_{k+1}-x_{k})

记 yk=gk+1−gky_{k}=g_{k+1}−g_{k},δk=xk+1−xk\delta_k=x_{k+1}−x_{k}，则

yk=HkδkHk−1yk=δk\begin{align} y_{k} = H_{k}\delta_{k} \\ H_{k}^{-1}y_{k}=\delta_{k} \end{align}

上式为拟牛顿条件。
拟牛顿法将GkG_{k}作为Hk−1H_{k}^{-1}的近似，要求矩阵GkG_{k}满足同样的条件:每次迭代矩阵是正定的，满足拟牛顿条件。

DFP算法(Davidon-Fletcher-Powell Algorithm,DFP Algorithm)

Algorithm: DFP Algorithm

Input: 目标函数f:Rn→Rf: \mathcal{R}^n \rightarrow \mathcal{R}，梯度函数∇f\nabla f，初始点x0∈Rnx_0 \in \mathcal{R}^n，收敛阈值ϵ>0\epsilon > 0；

Output: 近似最优解x∗x^*。

  1. 初始化:设初始点x=x0x = x_0，近似Hesse逆矩阵H0=IH_0 = I（单位矩阵），计算初始梯度g=∇f(x)g = \nabla f(x)，迭代次数k=0k = 0；
  2. While ∥g∥≥ϵ\|g\| \geq \epsilon:
    • 计算搜索方向:dk=−Hkgd_k = -H_k g；
    • 通过线搜索确定步长αk\alpha_k，满足arg⁡min⁡α>0f(xk+αdk)\arg \min_{\alpha > 0} f(x_k + \alpha d_k)；
    • 更新参数:xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_k；
    • 计算新梯度:gk+1=∇f(xk+1)g_{k+1} = \nabla f(x_{k+1})；
    • 计算差值向量:sk=xk+1−xks_k = x_{k+1} - x_k，yk=gk+1−gky_k = g_{k+1} - g_k；
    • 更新Hesse逆矩阵:

      Hk+1=Hk+sksk⊤sk⊤yk−Hkykyk⊤Hkyk⊤Hkyk\begin{array}{c} H_{k+1} = H_k + \frac{s_k s_k^\top}{s_k^\top y_k} - \frac{H_k y_k y_k^\top H_k}{y_k^\top H_k y_k}\end{array}

    • 令k=k+1k = k + 1；
  3. 返回x∗=xkx^* = x_k。

BFGS算法(Broyden-Fletcher-Goldfarb-Shanno Algorithm,BFGS Algorithm)

Algorithm: BFGS Algorithm

Input: 目标函数f:Rn→Rf: \mathcal{R}^n \rightarrow \mathcal{R}，梯度函数∇f\nabla f，初始点x0∈Rnx_0 \in \mathcal{R}^n，收敛阈值ϵ>0\epsilon > 0；

Output: 近似最优解x∗x^*。

  1. 初始化:设初始点x=x0x = x_0，近似Hesse矩阵B0=IB_0 = I（单位矩阵），计算初始梯度g=∇f(x)g = \nabla f(x)，迭代次数k=0k = 0；
  2. While ∥g∥≥ϵ\|g\| \geq \epsilon:
    • 计算搜索方向:dk=−Bk−1gd_k = -B_k^{-1} g（或通过求解Bkdk=−gB_k d_k = -g）；
    • 通过线搜索确定步长αk\alpha_k，满足arg⁡min⁡α>0f(xk+αdk)\arg \min_{\alpha > 0} f(x_k + \alpha d_k)；
    • 更新参数:xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_k；
    • 计算新梯度:gk+1=∇f(xk+1)g_{k+1} = \nabla f(x_{k+1})；
    • 计算差值向量:sk=xk+1−xks_k = x_{k+1} - x_k，yk=gk+1−gky_k = g_{k+1} - g_k；
    • 更新Hesse矩阵:

      Bk+1=Bk+ykyk⊤yk⊤sk−Bksk(Bksk)⊤sk⊤Bksk\begin{array}{c}B_{k+1} = B_k + \frac{y_k y_k^\top}{y_k^\top s_k} - \frac{B_k s_k (B_k s_k)^\top}{s_k^\top B_k s_k}\end{array}

    • 令k=k+1k = k + 1；
  3. 返回x∗=xkx^* = x_k。

约束优化与对偶

本节考虑如下约束优化问题:

min⁡x∈Rnf(x)s.t.Ax≤bx≥0\begin{align*} \min_{\boldsymbol{x} \in \mathbb{R}^n} \quad & f(\boldsymbol{x}) \\ \mathrm{s.t.} \quad & \boldsymbol{Ax} \leq \boldsymbol{b} \\ & \boldsymbol{x} \geq \boldsymbol{0} \end{align*}

其中f(x)f(\boldsymbol{x})是Rn→R\mathbb{R}^n \to \mathbb{R}的函数.

线性规划下的对偶

设原线性规划问题为

max⁡Z=c1x1+c2x2+⋯+cnxns.t.{a11x1+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋯am1x1+am2x2+⋯+amnxn≤bmxj≥0(j=1,2,⋯ ,n)\begin{array}{l} \max\quad & Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ \mathrm{s.t.} \quad & \left\{ \begin{array}{l} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n \leq b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n \leq b_2 \\ \cdots \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n \leq b_m \\ x_j \geq 0 \quad (j = 1, 2, \cdots, n) \end{array} \right. \end{array}

则称下列线性规划问题

max⁡W=b1y1+b2y2+⋯+bmyms.t.{a11y1+a21y2+⋯+am1ym≥c1a12y1+a22y2+⋯+am2ym≥c2⋯a1ny1+a2ny2+⋯+amnym≥cnyi≥0(i=1,2,⋯ ,m)\begin{array}{l} \max \quad & W = b_1 y_1 + b_2 y_2 + \cdots + b_m y_m \\ \mathrm{s.t.} \quad & \left\{ \begin{array}{l} a_{11} y_1 + a_{21} y_2 + \cdots + a_{m1} y_m \geq c_1 \\ a_{12} y_1 + a_{22} y_2 + \cdots + a_{m2} y_m \geq c_2 \\ \cdots \\ a_{1n} y_1 + a_{2n} y_2 + \cdots + a_{mn} y_m \geq c_n \\ y_i \geq 0 \quad (i = 1, 2, \cdots, m) \end{array} \right. \end{array}

上述对偶问题称为对称型对偶问题。原问题简记为 §，对偶问题简记为 (D) 。

重点:
1）目标函数的目标互为相反。(max⁡,min⁡\max,\min)
2）目标函数的系数是另一个约束条件的右端向量
3）约束系数矩阵是另一个的约束系数矩阵的转置
4）约束方程的个数与另一个的变量的个数相等

拉格朗日对偶(Lagrange duality)

我们考虑标准形式的优化问题:

min⁡xf(x)s.t.hi(x)≤0, i=1,…,mℓj(x)=0, j=1,…,r\begin{align*} \min_{x} \quad & f(x) \\ \mathrm{s.t.} \quad & h_i(x) \leq 0, \, i = 1, \ldots, m \\ & \ell_j(x) = 0, \, j = 1, \ldots, r \end{align*}

其中变量为 x∈Rnx \in \mathbf{R}^n。假设其定义域 D=⋂i=0mdom hi  ∩  ⋂j=1rdom ℓj\mathcal{D} = \bigcap_{i=0}^m \mathbf{dom}\,h_i \,\,\cap\,\, \bigcap_{j=1}^r \mathbf{dom}\,\ell_j 非空，并将该问题的最优值记为 p∗p^*。我们不假设该问题是凸的。
拉格朗日对偶的基本思想是通过将目标函数与约束函数的加权和相结合，将问题的约束条件纳入考虑。我们定义与该问题关联的拉格朗日函数 L:Rn×Rm×Rr→RL: \mathbf{R}^n \times \mathbf{R}^m \times \mathbf{R}^r \to \mathbf{R} 为:

L(x,λ,ν)=f(x)+∑i=1mλihi(x)+∑j=1rνjℓj(x),L(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) + \sum_{j=1}^r \nu_j \ell_j(x),

其定义域为 dom L=D×Rm×Rr\mathbf{dom}\,L = \mathcal{D} \times \mathbf{R}^m \times \mathbf{R}^r。我们将 λi\lambda_i 称为与第 ii 个不等式约束 hi(x)≤0h_i(x) \leq 0 关联的拉格朗日乘数；类似地，νj\nu_j 称为与第 jj 个等式约束 ℓj(x)=0\ell_j(x) = 0 关联的拉格朗日乘数。向量 λ\lambda 和 ν\nu 称为该问题的对偶变量或拉格朗日乘数向量。
对于每一组满足 λ⪰0\lambda \succeq 0 的对偶变量 (λ,ν)(\lambda, \nu)，拉格朗日对偶函数 g(λ,ν)g(\lambda, \nu) 给出了优化问题最优值 p⋆p^\star 的一个下界。因此，我们得到一个依赖于参数 λ\lambda 和 ν\nu 的下界。我们不禁想问:从拉格朗日对偶函数中能获得的最佳下界是什么？
由此引出了以下优化问题:

maxg(λ,ν)s.t.λ⪰0\begin{array}{l} \mathrm{max} & g(\lambda, \nu) \\ \mathrm{s.t.} & \lambda \succeq 0 \end{array}

此问题称为与原问题关联的拉格朗日对偶问题。在此上下文中，原问题有时被称为原始问题。术语对偶可行（描述满足 λ⪰0\lambda \succeq 0 且 g(λ,ν)>−∞g(\lambda, \nu) > -\infty 的对偶变量 (λ,ν)(\lambda, \nu)）此时具有明确含义:它表示 (λ,ν)(\lambda, \nu) 对应对偶问题的可行性。若 (λ⋆,ν⋆)(\lambda^\star, \nu^\star) 是对偶问题的最优解，则称其为对偶最优解或最优拉格朗日乘数。
无论原始问题是否为凸问题，拉格朗日对偶问题始终是凸优化问题，因为其目标函数（需最大化）是凹函数，而约束条件是凸的。

弱对偶、强对偶与Slater约束条件

弱对偶性（Weak Duality）

对于任意满足 λ⪰0\lambda \succeq 0 的对偶可行解 (λ,ν)(\lambda, \nu)，其对偶函数值 g(λ,ν)g(\lambda, \nu) 始终是原始问题最优值 p⋆p^\star 的下界，即:

g(λ,ν)≤p⋆.g(\lambda, \nu) \leq p^\star.

这意味着拉格朗日对偶问题的最优值 d⋆d^\star（称为对偶最优值）满足:

d⋆≤p⋆.d^\star \leq p^\star.

弱对偶性对任意优化问题（无论凸或非凸）均成立，其本质为对偶问题提供了原始问题的理论下界。

强对偶性（Strong Duality）

若对偶最优值 d⋆d^\star 与原始最优值 p⋆p^\star 相等，即:

d⋆=p⋆d^\star = p^\star

则称强对偶性成立。强对偶性并非普遍成立，其有效性依赖于问题结构与约束条件。

Slater约束准则（Slater’s Constraint Qualification）

标准形式
若原始问题为凸（即目标函数 f(x)f(x) 和不等式约束 hi(x)h_i(x) 均为凸函数，等式约束 ℓj(x)\ell_j(x) 为仿射函数），且存在一点 x∈relint Dx \in \mathbf{relint}\,\mathcal{D} 满足:

{hi(x)<0,i=1,…,m,ℓj(x)=0,j=1,…,r\begin{cases} h_i(x) < 0, & i=1,\ldots,m,\\ \ell_j(x) = 0, & j=1,\ldots,r \end{cases}

则称Slater条件成立，此时强对偶性必然成立。

仿射约束的弱化条件
若前 kk 个不等式约束 h1,…,hkh_1, \ldots, h_k 为仿射函数，则Slater条件可放宽为:存在 x∈relint Dx \in \mathbf{relint}\,\mathcal{D} 满足:

{hi(x)≤0,i=1,…,k,hi(x)<0,i=k+1,…,m,ℓj(x)=0,j=1,…,r.\begin{cases} h_i(x) \leq 0, & i=1,\ldots,k, \\ h_i(x) < 0, & i=k+1,\ldots,m, \\ \ell_j(x) = 0, & j=1,\ldots,r. \end{cases}

KKT条件(Karush-Kuhn-Tucker Conditions）

  • 平稳性:0∈∂x(f(x)+∑i=1muihi(x)+∑j=1rvjℓj(x))0 \in \partial_x \left( f(x) + \sum_{i=1}^m u_i h_i(x) + \sum_{j=1}^r v_j \ell_j(x) \right)
  • 互补松弛性:ui⋅hi(x)=0u_i \cdot h_i(x) = 0 （对所有 ii）
  • 原始可行性:hi(x)≤0h_i(x) \leq 0，ℓj(x)=0\ell_j(x) = 0 （对所有 i,ji, j）
  • 对偶可行性:ui≥0u_i \geq 0 （对所有 ii）

实例

考虑以下凸优化问题:

min⁡xx12+x22+x1x2s.t.x1+x2≤2x1−x2=0\begin{align*} \min_{x} \quad & x_1^2 + x_2^2 + x_{1} x_{2}\\ \mathrm{s.t.} \quad & x_1 + x_2 \leq 2 \\ & x_1 - x_2 = 0 \end{align*}

  1. 拉格朗日对偶
    对于问题:

min⁡xx12+x22+x1x2s.t.x1+x2≤2x1−x2=0\begin{align*} \min_{x} \quad & x_1^2 + x_2^2 + x_1 x_2 \\ \mathrm{s.t.} \quad & x_1 + x_2 \leq 2 \\ & x_1 - x_2 = 0 \end{align*}

构造拉格朗日函数:

L(x,λ,ν)=x12+x22+x1x2+λ(x1+x2−2)+ν(x1−x2),L(x, \lambda, \nu) = x_1^2 + x_2^2 + x_1 x_2 + \lambda (x_1 + x_2 - 2) + \nu (x_1 - x_2),

其中 λ≥0\lambda \geq 0，ν∈R\nu \in \mathbb{R}。

对偶函数为:

g(λ,ν)=inf⁡xL(x,λ,ν).g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu).

通过求解梯度 ∇xL=0\nabla_x L = 0，得到 x1x_1 和 x2x_2 的表达式:

x1=−λ−3ν3,x2=−λ+3ν3.x_1 = \frac{-\lambda - 3\nu}{3}, \quad x_2 = \frac{-\lambda + 3\nu}{3}.

将 x1,x2x_1, x_2 代入 L(x,λ,ν)L(x, \lambda, \nu)，化简得:

g(λ,ν)=−λ23−ν2−2λ.g(\lambda, \nu) = -\frac{\lambda^2}{3} - \nu^2 - 2\lambda.

对偶问题为:

max⁡λ≥0,ν∈Rg(λ,ν).\max_{\lambda \geq 0, \nu \in \mathbb{R}} g(\lambda, \nu).

  • 对 ν\nu 求极大值，得 ν=0\nu = 0。
  • 对 λ≥0\lambda \geq 0 求极大值，得 λ=0\lambda = 0。
    对偶最优值为 g(0,0)=0g(0, 0) = 0，与原问题最优值一致，验证强对偶成立。
  1. 弱对偶、强对偶与Slater条件
  • 弱对偶:对偶问题的解始终小于等于原问题的解，即 g(λ,ν)≤p∗g(\lambda, \nu) \leq p^*（原问题最优值）。
  • 强对偶:若对偶间隙为零（g∗=p∗g^* = p^*），则强对偶成立。

Slater条件:

  • 存在严格可行点:例如 x1=x2=0x_1 = x_2 = 0，满足 x1+x2=0<2x_1 + x_2 = 0 < 2（不等式严格成立），且 x1−x2=0x_1 - x_2 = 0。
  • 因此，Slater条件成立，强对偶成立。
  1. KKT条件
    最优解 x1=x2=0x_1 = x_2 = 0 满足以下KKT条件:

{x1+x2=0≤2,x1−x2=0.λ=0≥0.λ(x1+x2−2)=0⋅(−2)=0.∇xL=[2x1+x2+λ+ν2x2+x1+λ−ν]=[0+0+0+00+0+0−0]=0.\left\{ \begin{array}{l} x_1 + x_2 = 0 \leq 2, \quad x_1 - x_2 = 0.\\ \lambda = 0 \geq 0.\\ \lambda (x_1 + x_2 - 2) = 0 \cdot (-2) = 0.\\ \nabla_x L = \begin{bmatrix} 2x_1 + x_2 + \lambda + \nu \\ 2x_2 + x_1 + \lambda - \nu \end{bmatrix} = \begin{bmatrix} 0 + 0 + 0 + 0 \\ 0 + 0 + 0 - 0 \end{bmatrix} = 0. \end{array} \right.

所有KKT条件均被满足，验证了解的最优性。