首页课程笔记自动化系凸优化

# 等式约束

  1. 问题形式

    等式约束（凸）优化问题：

    min⁡f(x)s.t.Ax=b\begin{align*} \min \quad & f(x) \\ \text{s.t.} \quad & Ax = b \end{align*}

    其中：

    • f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}，定义域为 dom f\text{dom}\ f
    • A∈Rp×nA \in \mathbb{R}^{p \times n}，rank(A)=p<n\text{rank}(A) = p < n
    • p∗=f(x∗)=min⁡{f(x)∣s.t. Ax=b}p^* = f(x^*) = \min\{f(x) \mid \text{s.t. } Ax = b\} 为有限值

    基本假设：

    1. ff 是具有连续二阶导数的凸函数
    2. AA 行满秩（rank(A)=p<n\text{rank}(A) = p < n）
    3. 最优值 p∗p^* 为有限值

    KKT 条件：

    存在 x∗∈Rnx^* \in \mathbb{R}^n，v∗∈Rpv^* \in \mathbb{R}^p，使得：

    ∇f(x∗)+ATv∗=0,Ax∗=b\nabla f(x^*) + A^T v^* = 0, \quad Ax^* = b

  2. 三种处理方法

    对于等式约束优化问题，一般有三种选择：

    选择一：消除等式约束（Eliminating Equality Constraints）

    通过参数化可行域，将问题转化为无约束优化问题。

    选择二：推导对偶（Deriving the Dual）

    通过拉格朗日对偶，将问题转化为对偶问题。

    选择三：等式约束牛顿方法（Equality-Constrained Newton）

    在许多情况下，这是最直接的选择。

  3. 选择一：消除等式约束

    基本思想

    假设已知 x^∈dom f\hat{x} \in \text{dom}\ f 满足 Ax^=bA \hat{x} = b。

    用 F∈Rn×(n−p)F \in \mathbb{R}^{n \times (n-p)} 表示 AA 的零空间 {x∣Ax=0}\{x \mid Ax = 0\} 的基矩阵（AF=0AF = 0）：

    rank(F)=n−p,{x∣Ax=0}={Fz∣z∈Rn−p}\text{rank}(F) = n-p, \quad \{x \mid Ax = 0\} = \{Fz \mid z \in \mathbb{R}^{n-p}\}

    因此：

    {x∣Ax=b}={Fz+x^∣z∈Rn−p}\{x \mid Ax = b\} = \{Fz + \hat{x} \mid z \in \mathbb{R}^{n-p}\}

    原问题等价于：

    min⁡z∈Rn−pf~(z)=f(Fz+x^)\min_{z \in \mathbb{R}^{n-p}} \tilde{f}(z) = f(Fz + \hat{x})

    这是一个无约束优化问题。

    例子：资源约束的最优分配

    考虑问题：

    minimizef1(x1)+f2(x2)+⋯+fn(xn)subject tox1+x2+⋯+xn=b\begin{align*} \text{minimize} \quad & f_1(x_1) + f_2(x_2) + \cdots + f_n(x_n) \\ \text{subject to} \quad & x_1 + x_2 + \cdots + x_n = b \end{align*}

    消除 xn=b−x1−⋯−xn−1x_n = b - x_1 - \cdots - x_{n-1}，即选择：

    x^=ben,F=[I−1T]∈Rn×(n−1)\hat{x} = b e_n, \quad F = \begin{bmatrix} I \\ -\mathbf{1}^T \end{bmatrix} \in \mathbb{R}^{n \times (n-1)}

    约化问题：

    minimizef1(x1)+⋯+fn−1(xn−1)+fn(b−x1−⋯−xn−1)\text{minimize} \quad f_1(x_1) + \cdots + f_{n-1}(x_{n-1}) + f_n(b - x_1 - \cdots - x_{n-1})

    变量为 x1,…,xn−1x_1, \ldots, x_{n-1}。

  4. 选择二：对偶方法

    拉格朗日对偶函数

    拉格朗日对偶函数：

    g(v)=−bTv+inf⁡x(f(x)+vTAx)=−bTv−sup⁡x(−f(x)−(ATv)Tx)=−f∗(ATv)−bTv\begin{aligned} g(v) &= -b^T v + \inf_x (f(x) + v^T Ax) \\ &= -b^T v - \sup_x (-f(x) - (A^T v)^T x) \\ &= -f^*(A^T v) - b^T v \end{aligned}

    其中 f∗(⋅)f^*(\cdot) 是 f(⋅)f(\cdot) 的共轭函数，强对偶成立。

    如果幸运，我们可以用最优对偶变量 v∗v^* 表示最优原变量 x∗x^*。

    例子：等式约束的凸二次规划

    考虑问题：

    min⁡{f(x)=12xTPx+qTx+r∣s.t. Ax=b}\min \left\{f(x) = \frac{1}{2} x^T P x + q^T x + r \mid \text{s.t. } Ax = b\right\}

    其中 P∈S+nP \in S_+^n（半正定），AA 行满秩。

    根据 KKT 方程：

    [PATA0][xv]=[−qb]\begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ v \end{bmatrix} = \begin{bmatrix} -q \\ b \end{bmatrix}

    解的情况可确定三种可能：

    1）唯一最优解

    KKT 矩阵 [PATA0]\begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} 非奇异。

    在给定条件下，[PATA0]\begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} 非奇异等价于 [PA]\begin{bmatrix} P \\ A \end{bmatrix} 列满秩；或者等价的 P+ATA≻0P + A^T A \succ 0。

    2）无穷多最优解

    KKT 矩阵 [PATA0]\begin{bmatrix} P & A^T \\ A & 0 \end{bmatrix} 奇异，但上述 KKT 方程有解。

    3）无下界

    如果 KKT 系统不可解，则二次优化问题无下界或不可行。

    在这种情况下，存在 v∈Rnv \in \mathbb{R}^n 和 w∈Rpw \in \mathbb{R}^p 使得：

    Pv+ATw=0,Av=0,−qTv+bTw>0Pv + A^T w = 0, \quad Av = 0, \quad -q^T v + b^T w > 0

    设 x^\hat{x} 是任意可行点。点 x=x^+tvx = \hat{x} + tv 对所有 tt 都是可行的，且：

    f(x^+tv)=f(x^)+t(vTPx^+qTv)+12t2vTPv=f(x^)+t(−x^TATw+qTv)−12t2wTAv=f(x^)+t(−bTw+qTv)\begin{aligned} f(\hat{x} + tv) &= f(\hat{x}) + t(v^T P \hat{x} + q^T v) + \frac{1}{2} t^2 v^T P v \\ &= f(\hat{x}) + t(-\hat{x}^T A^T w + q^T v) - \frac{1}{2} t^2 w^T Av \\ &= f(\hat{x}) + t(-b^T w + q^T v) \end{aligned}

    当 t→∞t \to \infty 时，函数值无界下降。

    例子：等式约束的解析中心

    考虑问题：

    minimizef(x)=−∑i=1nlog⁡xisubject toAx=b\begin{align*} \text{minimize} \quad & f(x) = -\sum_{i=1}^n \log x_i \\ \text{subject to} \quad & Ax = b \end{align*}

    其中 A∈Rp×nA \in \mathbb{R}^{p \times n}，隐式约束 x≻0x \succ 0。

    使用 f∗(y)=∑i=1n(−1−log⁡(−yi))=−n−∑i=1nlog⁡(−yi)f^*(y) = \sum_{i=1}^n (-1 - \log(-y_i)) = -n - \sum_{i=1}^n \log(-y_i)（dom f∗=−R++n\text{dom}\ f^* = -\mathbb{R}_{++}^n），对偶问题为：

    maximizeg(ν)=−bTν+n+∑i=1nlog⁡(ATν)i\text{maximize} \quad g(\nu) = -b^T \nu + n + \sum_{i=1}^n \log(A^T \nu)_i

    其中 (ATν)i(A^T \nu)_i 表示 ATνA^T \nu 的第 ii 个分量。

  5. 选择三：等式约束牛顿方法

    在许多情况下，等式约束牛顿方法是最直接的选择。这将在下一节详细讨论。

# 等式约束下的牛顿方法

  1. 基本思想

    对于等式约束优化问题：

    min⁡f(x)s.t.Ax=b\begin{align*} \min \quad & f(x) \\ \text{s.t.} \quad & Ax = b \end{align*}

    等式约束牛顿方法通过求解 KKT 系统来更新迭代点。

  2. KKT 系统

    在每次迭代中，需要求解 KKT 系统：

    [HATA0][vw]=−[gh]\begin{bmatrix} H & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = -\begin{bmatrix} g \\ h \end{bmatrix}

    其中：

    • H=∇2f(x)H = \nabla^2 f(x) 是 Hessian 矩阵
    • g=∇f(x)g = \nabla f(x) 是梯度
    • h=Ax−bh = Ax - b 是约束残差
    • vv 是搜索方向
    • ww 是对偶变量（拉格朗日乘子）的更新

  3. 通过消除法求解

    可以通过消除法求解：

    AH−1ATw=h−AH−1g,Hv=−(g+ATw)AH^{-1} A^T w = h - AH^{-1} g, \quad Hv = -(g + A^T w)

    首先求解第一个方程得到 ww，然后求解第二个方程得到 vv。

  4. 例子：网络流问题

    问题形式

    考虑网络流问题：

    min⁡∑i=1nϕi(xi)s.t.Ax=b\begin{align*} \min \quad & \sum_{i=1}^n \phi_i(x_i) \\ \text{s.t.} \quad & Ax = b \end{align*}

    其中：

    • xix_i：通过弧 ii 的流量
    • ϕi\phi_i：弧 ii 的流量成本函数（ϕi′′(x)>0\phi_i''(x) > 0）
    • 节点-关联矩阵 A~∈R(p+1)×n\tilde{A} \in \mathbb{R}^{(p+1) \times n} 定义为：

      A~ij={1弧 j 离开节点 i−1弧 j 进入节点 i0否则\tilde{A}_{ij} = \begin{cases} 1 & \text{弧 } j \text{ 离开节点 } i \\ -1 & \text{弧 } j \text{ 进入节点 } i \\ 0 & \text{否则} \end{cases}

    • 约化节点-关联矩阵 A∈Rp×nA \in \mathbb{R}^{p \times n} 是 A~\tilde{A} 去掉最后一行
    • b∈Rpb \in \mathbb{R}^p 是（约化）源向量
    • 如果图是连通的，则 rank A=p\text{rank}\ A = p

    KKT 系统

    [HATA0][vw]=−[gh]\begin{bmatrix} H & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = -\begin{bmatrix} g \\ h \end{bmatrix}

    其中 H=diag(ϕ1′′(x1),…,ϕn′′(xn))H = \text{diag}(\phi_1''(x_1), \ldots, \phi_n''(x_n)) 是正定对角矩阵。

    求解

    通过消除法求解：

    AH−1ATw=h−AH−1g,Hv=−(g+ATw)AH^{-1} A^T w = h - AH^{-1} g, \quad Hv = -(g + A^T w)

    稀疏性

    系数矩阵的稀疏模式由图的连通性给出：

    (AH−1AT)ij≠0⟺(AAT)ij≠0⟺节点 i 和 j 由一条弧连接(AH^{-1} A^T)_{ij} \neq 0 \Longleftrightarrow (AA^T)_{ij} \neq 0 \Longleftrightarrow \text{节点 } i \text{ 和 } j \text{ 由一条弧连接}

    这允许使用稀疏线性代数技术高效求解。

# 线性矩阵不等式的解析中心

  1. 解析中心的定义

    凸不等式和线性方程的集合的解析中心：

    fi(x)≤0,i=1,…,m,Fx=gf_i(x) \leq 0, \quad i = 1, \ldots, m, \quad Fx = g

    定义为以下问题的最优点：

    minimize−∑i=1mlog⁡(−fi(x))subject toFx=g\begin{align*} \text{minimize} \quad & -\sum_{i=1}^m \log(-f_i(x)) \\ \text{subject to} \quad & Fx = g \end{align*}

    特点：

    • 比最小体积椭球（MVE）或 Chebyshev 中心更容易计算
    • 不仅仅是可行集的性质：两组不等式可以描述同一个集合，但有不同的解析中心

  2. 线性不等式的解析中心

    线性不等式 aiTx≤bi,i=1,…,ma_i^T x \leq b_i, i = 1, \ldots, m 的解析中心：

    xacx_{\text{ac}} 是以下函数的最小值点：

    ϕ(x)=−∑i=1mlog⁡(bi−aiTx)\phi(x) = -\sum_{i=1}^m \log(b_i - a_i^T x)

    内椭球和外椭球

    从解析中心得到的内椭球和外椭球：

    Einner⊆{x∣aiTx≤bi,i=1,…,m}⊆Eouter\mathcal{E}_{\text{inner}} \subseteq \{x \mid a_i^T x \leq b_i, i = 1, \ldots, m\} \subseteq \mathcal{E}_{\text{outer}}

    其中：

    Einner={x∣(x−xac)T∇2ϕ(xac)(x−xac)≤1}Eouter={x∣(x−xac)T∇2ϕ(xac)(x−xac)≤m(m−1)}\begin{aligned} \mathcal{E}_{\text{inner}} &= \left\{x \mid (x - x_{\text{ac}})^T \nabla^2 \phi(x_{\text{ac}})(x - x_{\text{ac}}) \leq 1\right\} \\ \mathcal{E}_{\text{outer}} &= \left\{x \mid (x - x_{\text{ac}})^T \nabla^2 \phi(x_{\text{ac}})(x - x_{\text{ac}}) \leq m(m-1)\right\} \end{aligned}

  3. 线性矩阵不等式的解析中心

    问题形式

    考虑问题：

    minimize−log⁡det⁡Xsubject totr(AiX)=bi,i=1,…,p\begin{align*} \text{minimize} \quad & -\log \det X \\ \text{subject to} \quad & \text{tr}(A_i X) = b_i, \quad i = 1, \ldots, p \end{align*}

    变量 X∈SnX \in S^n（n×nn \times n 对称矩阵）。

    最优性条件

    X∗≻0,−(X∗)−1+∑j=1pνj∗Ai=0,tr(AiX∗)=bi,i=1,…,pX^* \succ 0, \quad -(X^*)^{-1} + \sum_{j=1}^p \nu_j^* A_i = 0, \quad \text{tr}(A_i X^*) = b_i, \quad i = 1, \ldots, p

  4. 牛顿方法

    牛顿方程

    在可行点 XX 处的牛顿方程：

    X−1ΔXX−1+∑j=1pwjAi=X−1,tr(AiΔX)=0,i=1,…,pX^{-1} \Delta X X^{-1} + \sum_{j=1}^p w_j A_i = X^{-1}, \quad \text{tr}(A_i \Delta X) = 0, \quad i = 1, \ldots, p

    这来自线性近似 (X+ΔX)−1≈X−1−X−1ΔXX−1(X + \Delta X)^{-1} \approx X^{-1} - X^{-1} \Delta X X^{-1}。

    变量：ΔX,w\Delta X, w，共 n(n+1)/2+pn(n+1)/2 + p 个变量。

  5. 块消除法求解

    消除 ΔX\Delta X

    从第一个方程消除 ΔX\Delta X：

    ΔX=X−∑j=1pwjXAjX\Delta X = X - \sum_{j=1}^p w_j X A_j X

    代入第二个方程

    将 ΔX\Delta X 代入第二个方程：

    ∑j=1ptr(AiXAjX)wj=bi,i=1,…,p\sum_{j=1}^p \text{tr}(A_i X A_j X) w_j = b_i, \quad i = 1, \ldots, p

    这是一个关于变量 w∈Rpw \in \mathbb{R}^p 的稠密正定线性方程组。

  6. 计算复杂度

    使用 Cholesky 分解 X=LLTX = LL^T 的浮点运算次数（主要项）：

    • 形成 pp 个乘积 LTAjLL^T A_j L：(3/2)pn3(3/2) p n^3
    • 形成 p(p+1)/2p(p+1)/2 个内积 tr((LTAiL)(LTAjL))\text{tr}((L^T A_i L)(L^T A_j L))：(1/2)p2n2(1/2) p^2 n^2
    • 通过 Cholesky 分解求解（2）：(1/3)p3(1/3) p^3

    总计算复杂度主要由 O(pn3)O(p n^3) 项主导。