优化基础系列 - 0. 基本问题和底层逻辑

0. 动机

这一系列的 blog 讨论优化问题的重要概念和相关求解方法。 在开始之前，我们需要梳理清楚优化问题中的

• 基本问题
• 基础概念
• 数学工具
• 求解方法
• 重要结论

What：什么是优化问题

优化问题的组成三要素：

• 优化变量
• 目标函数
• 约束条件

Why：优化问题的目的是什么

优化问题的目的

• 在满足约束条件前提下
• 寻找可以使得目标函数最小化（或最大化）的变量，
• 目标函数最小化（或最大化）的数值

How：如何求解优化问题

优化问题的求解手段

• 直接求解：如果最优解满足一个方程，推导出这个方程，直接求解这个方程
• 迭代求解：通过迭代的方式，逐步逼近最优解
• 转化求解：将原问题转化为等价问题（这种问题转换要保证等价问题的最优解与原问题的最优解相同，并且转化后的问题更加易于求解，这样问题转化才有意义）

优化理论的基本问题

优化理论的基本问题：

• 基本问题 1：关于最优解本身的描述，怎么更加科学的描述优化问题的最优解（几何、代数、对偶）
• 基本问题 2：描述优化问题的最优解时，需要考虑哪些因素
• 基本问题 3：如何将最优解与所有非最优解进行比较
• 基本问题 4：关于最优解的性质
  • 是否可以直接找到优化问题的最优解满足某个方程
  • 是否可以通过求解该方程来得到最优解
• 基本问题 5：优化问题的求解方法
  • 是否可以通过迭代的方式寻找优化问题的最优解
  • 如何证明这种迭代方法的有效性
• 基本问题 6：优化问题的转换方法
  • 是否可以将原始优化问题转换为一个新的优化问题
  • 并且这种问题转换是有意义的：
    • 新问题更加易于求解
    • 新问题与原始问题等价（二者的最优解相同）

优化理论的底层逻辑

优化的核心是把 在可行集上比所有点都好 转化为 可计算、可证明的条件

• 切锥：定义“所有可行方向”；
• 法锥：把无穷多方向条件压缩成一条包含；
• CQ：保证法锥能用约束梯度生成；
• 乘子：生成系数（坐标），从而得到 KKT；
• 激活集+互补松弛：解决不等式的单边性与分段性；
• 对偶：提供全局下界、误差证书与影子价格，使“比较所有非最优解”变得可操作。

优化理论的数学工具

顺着 定义最优 → 切/法几何 → KKT/乘子/CQ → 对偶/证书 → 迭代算法与收敛证明 → 等价变换 这条逻辑链，优化理论所需要的数学工具，大致可以分成 8 组。每一组都对应它在链条里解决的“基本问题”。

---

1) 分析学与微积分（把“比较”变成“导数条件”）

用来做什么： 从\(f(x^*)\le f(x)\)转成“一阶/二阶必要条件”、方向导数、泰勒展开。

典型工具：

• 方向导数、梯度、Hessian、泰勒定理与余项
• 隐函数定理（等式约束形成流形时）
• Lipschitz 连续、光滑性（L-smooth）、强凸性等正则性
• 不等式估计（用于收敛率、步长条件）

2) 线性代数（把几何对象写成可计算表达）

用来做什么： 约束梯度的线性无关/秩条件（LICQ），投影、正交分解、谱性质（强凸、条件数、收敛速度）。

典型工具：

• 子空间、正交补、投影算子
• 矩阵秩、伪逆、QR/SVD
• 正定性、特征值界、条件数
• Schur 补（尤其在 LMI/控制优化里）

3) 凸分析（把“局部条件”升级为“全局最优 + 证书”）

用来做什么： 解释为什么凸问题 KKT 常充分、为什么对偶是下界、强对偶何时成立。

典型工具：

• 凸集、凸函数、严格凸/强凸
• 次梯度、次微分 \(\partial f\)、支撑超平面
• 共轭函数（Fenchel conjugate）、Fenchel–Young 不等式
• 分离定理、Hahn–Banach（对偶与证书背后的核心）
• 单调算子与 resolvent（prox 的理论底座）

4) 变分分析与广义导数（处理不光滑与约束几何：切锥/法锥）

用来做什么： 把“可行方向集合”与“法锥包含”严谨化；处理不光滑、边界、激活集切换。

典型工具：

• 切锥/切空间（Bouligand tangent cone 等）
• 法锥/正规锥（normal cone）、极锥关系
• 指示函数 \(\delta_{\mathcal F}\)（把约束写进目标）
• Clarke 次微分、广义梯度（非光滑情形）
• 变分不等式（VI）：\(0\in \nabla f(x)+N_{\mathcal F}(x)\)

5) 约束资格条件与最优性系统（让“乘子存在”并形成 KKT）

用来做什么： 解释为什么能用“约束梯度线性组合”刻画法锥；保证乘子存在、KKT 有意义。

典型工具：

• LICQ / MFCQ / CRCQ / Slater（各类 CQ）
• Farkas 引理（线性约束的核心“存在性”工具）
• 二阶必要/充分条件（临界锥、关键锥、约化 Hessian）
• 互补系统（complementarity system）与活跃集理论

6) 对偶理论（把原问题变成“最好下界/鞍点/证书”）

用来做什么： 解释“为什么要最好下界”“强对偶/弱对偶”“影子价格/敏感性”。

典型工具：

• 拉格朗日对偶：(q(,)=_x L(x,,))
• KKT ↔︎ 鞍点（saddle point）理论
• 强对偶条件（Slater、闭性/约束资格等）
• 敏感性分析、包络定理（影子价格公式）
• Fenchel 对偶、锥对偶（conic duality：LP/SOCP/SDP）

7) 数值算法与收敛证明工具（迭代法“为什么有效”）

用来做什么： 把最优性系统变成可迭代的算子/不动点；证明下降性、收敛性、速率。

典型工具：

• 不动点理论：Banach 压缩映射、平均算子、非扩张映射
• Lyapunov/势函数（descent lemma、三点不等式）
• 单调性与 cocoercivity（梯度法/前向后向分裂的底座）
• 误差界（error bound）、KL 性质（非凸收敛分析常用）
• 原始-对偶间隙（gap）作为证书与停止准则

8) 概率与统计（随机优化与学习中的优化）

用来做什么： SGD、随机近似、样本平均逼近（SAA）、泛化误差与收敛率。

典型工具：

• 条件期望、马氏差分、浓度不等式（Hoeffding/Bernstein）
• 随机逼近（Robbins–Monro）
• 随机梯度噪声模型与收敛分析
• 统计学习理论的一些界（泛化/复杂度）

逻辑链 ↔︎ 数学工具

• 最优的科学描述（比较所有点） → 分析学 + 凸分析
• 切锥/法锥（局部几何） → 变分分析
• 线性组合/乘子/KKT → 线性代数 + CQ + Farkas + 二阶理论
• 对偶/最好下界/影子价格 → 凸分析 + 分离定理 + 对偶理论 + 敏感性
• 迭代求解与有效性证明 → 不动点/单调算子/势函数/误差界
• 新问题更易解且等价 → 对偶、分裂、增广拉格朗日、锥优化等结构化理论

最小闭环工具集

• 只学一套最核心的数学（例如：凸分析 + 变分不等式 + 单调算子），
• 就能把切/法锥、KKT、对偶、prox/ADMM/原始对偶算法串起来；
• 再在需要时补二阶与非凸。

---

---

1. 基本问题 1 - 最优解的描述

1.1 最优解的 几何描述：没有可行下降方向

最优点 \(x^\ast\) 的本质：

• 在可行集 \(\cal{F}\) 里，不存在 可行方向 使得
  • 目标函数（的一阶）下降
  • 目标函数（的一阶）下降后，约束条件仍保持可行
• 可行方向→ 切空间/切锥
• 不能下降→ 梯度与这些方向的内积条件

1.2 最优解的 代数描述：把“所有方向”压缩成一个条件

“对所有可行方向 \(d\)”是无限多个条件，不好验证。于是引入

• 法空间/法锥：把“所有切方向”的正交/对偶对象集中表示；
• 简洁的数学表述 (负梯度必须属于可行集的法锥)： \(0\in\nabla f(x^\ast) + N_\cal{F}(x^\ast)\)， 其中 \(N_\cal{F}(x^\ast)\) 为 \(\cal{F}\) 的法锥

1.3 最优解的 全局描述：是不是全局最优？距离全局最优还有多远？

这就需要对偶：提供“最优值的下界”和“误差证书”

---

2. 基本问题 2 - 描述最优解需要考虑的因素

• 可行性：\(x^\ast\in\cal{F}\)
• 局部几何：\(\cal{F}\) 在 \(x^\ast\) 附近长什么样？
  • 用 切空间/切锥 表示“允许动的方向”
  • 用 法空间/法锥 表示“阻止你出界的方向”
• 约束是否起作用：哪些约束真的“顶住了”
  • 用 激活集（active set）刻画。
• 正则性：把几何变成梯度线性组合是否可靠
  • 需要 约束正则性（constraint qualification, CQ）
  • 否则“梯度生成法锥”可能失败，乘子可能不存在
• 全局性
  • 用 对偶 给出下界、gap、敏感性（影子价格）

---

3. 基本问题 3 - 如何把最优解与所有非最优解比较？

这是你列的最核心“科学性”问题：不是只找到一个点，而是能说“它比所有别的点好”。

原始域比较：

• 直接用定义 \(f(x^*)\le f(x), \forall x\in\cal{F}\)
• 注意：这是最强但最难用的比较，因为要比较所有可行点。

局部比较：用切锥上的“一阶不能下降”

• 把“所有点”降维成“所有方向”：\[ \nabla f (x^\ast)^\top d \ge 0, \forall d\in T_{\mathcal{F}}(x^\ast) \] 其中 \(T_{\cal{F}}(x^*)\) 是切锥/切空间
• 意义：你不用枚举所有 \(x\)，只看局部能走的方向。

再压缩：用法锥的一条包含关系

• 把“所有方向”再压缩成：\(-\nabla f (x^\ast)^\top \in N_\cal{F}(x^\ast)\)，其中 \(N_\cal{F}(x^\ast)\) 是法锥
• 这一步就是从切锥到法锥的“对偶化”：切锥与法锥互为极锥
• 切锥与法锥的解释：一个描述“能走哪儿”，一个描述“会被哪儿挡住”

全局数值比较：对偶下界

• 对偶构造 \(d^\ast\) 使得： \[d^\ast\le f(x), \forall x\in \cal{F}\]
• 只要找到一个可行解 \(x\) 和一个对偶可行解（下界） \(d(\lambda,ν)\)，就有 \[ d(\lambda,v) \le f(x^\ast) \le f(x), \forall x\in \cal{F} \]
• 两边夹住，中间差距就是可证明误差（primal-dual gap）。
• 这就是对偶“最好下界”的意义：它给出一个能比较所有非最优解的统一标尺。

---

4. 基本问题 4 - 能否“直接找到最优解满足某个方程”，通过解方程得到最优解？

可以，但要讲清“方程”是什么层级：

4.1 最底层：法锥包含（这是个 变分不等式）

最“科学”也最统一的方程形式（严格说是包含关系） \[ 0\in \nabla f(x) + N_{\mathcal F}(x) \]

4.2 光滑约束 + CQ条件 = KKT 方程

若 - \(\mathcal{F}=\{x|h(x)=0,\ g(x)\le 0\}\) - 并且约束 \(h(x)\) 和 \(g(x)\) 满足 CQ 条件，

则 - 法锥可由约束梯度生成 - 于是可以得到 KKT方程：KKT方程不是凭空出现，而是法锥表示被“梯度生成”之后的坐标化表达 \[ \begin{align} \nabla f(x^\star)+\nabla h(x^\star)\lambda^\star+\nabla g(x^\star)\nu^\star=&0, \\ \nu^\star\ge& 0,\\ \nu^\star\circ g(x^\star)=&0 \end{align} \]

4.3 重要提醒：解 KKT ≠ 一定得到全局最优

• 非凸：KKT 多是必要非充分，解 KKT 可能只是鞍点/局部极值；
• 凸 + Slater：KKT 才与全局最优等价。

---

5. 基本问题 5 - 能否用迭代方式找最优解？如何证明有效性？

迭代法要“有效”，通常要回答三件事（这恰好对应前面概念）：

5.1 迭代逼近依据的是什么“刻画方式”？

• 逼近原始问题：KKT方程/法锥包含（一阶最优性）
• 逼近对偶问题：对偶最优（最好下界）
• 同时逼近：（原始-对偶算法）

5.2 为什么会收敛？典型证明套路

• 下降性：构造一个量（目标值、拉格朗日、Lyapunov）单调下降/上升；
• 可行性/残差收敛：约束违背趋于 0；
• 不动点/非扩张/收缩：把最优性写成 \(x=T(x)\)，证明 \(T\) 是（平均/非扩张/收缩），或在某域内是压缩；
• 对偶间隙：用 gap 作为误差证书，证明 gap → 0。

5.3 这些套路与概念的对应关系

• 切/法锥：定义“残差应该朝哪儿消失”（比如投影梯度、镜像下降）；
• 激活集/互补松弛：解释为什么边界会“切换”，以及算法为何可能分段；
• 对偶：给出收敛证书（gap）、给出乘子更新意义（价格调整）；
• CQ：保证你收敛到的点真的满足 KKT（而不是几何退化导致的“假驻点”）。

---

6. 基本问题 6 - 能否把原问题转换成一个新问题？为什么这种转换有意义？

优化里最常见的“有意义转换”，本质上都在做一件事：

• 把 难比较、难处理的可行集几何 换成 更好处理的代数结构，并保留 最优性信息。

下面把你提到的“等价/更易解”对应到三种经典转换：

6.1 对偶：从“找最小”变成“找最好下界”

• 新问题：(q(,))

• 意义：

  • 给出下界证书；
  • 有时更易分解、更易计算；
  • 强对偶时与原问题等价（同最优值，KKT 连接原始与对偶解）。

6.2 鞍点：把约束问题变成 \(\min\max\)（而不是 \(\min\)）

• 关键点：不是“变无约束最小化”，而是“变成鞍点问题”；
• 意义：鞍点的一阶条件就是 KKT；算法上可用原始-对偶迭代。

6.3 罚函数/增广拉格朗日：把“硬约束”变成“软惩罚 + 乘子迭代”

• 新问题序列往往更易解；
• 但逻辑上它们服务的是“逼近 KKT/鞍点”，不是替代 KKT。

---

7 总结：上述概念都在回答什么问题

下面按“每个概念回答什么基本问题”来梳理（这比定义更有用）：

7.1 切空间 / 切锥：回答“可行集允许往哪儿动？”

• 动机：最优性来自“没有可行下降方向”；你必须先定义“可行方向集合”。
• 等式 → 切空间（线性子空间）；不等式 → 切锥（因为单边边界）。

7.2 法空间 / 法锥：回答“什么力量阻止你出界？一阶最优性可否压缩成一句话？”

• 动机：把“对所有切方向的条件”压缩成一个包含关系。
• 法锥是切锥的对偶对象：切描述“能走”，法描述“会被挡”。

7.3 拉格朗日乘子（线性组合）：回答“如何把法锥用有限个梯度坐标化？”

• 动机：法锥是几何对象，不好算；若它能由约束梯度生成，就能写成“梯度线性组合=0”。
• 乘子就是这个生成/坐标化的系数。

7.4 约束正则性（CQ）：回答“梯度生成法锥这件事靠不靠谱？乘子是否存在？”

• 动机：没有 CQ，几何法锥可能比“梯度生成的锥”更大/更怪，导致 KKT 可能失败。
• CQ 是把几何真实与线性化模型对齐的条件。

7.5 激活集：回答“哪些不等式约束真的在最优点处起作用？”

• 动机：不等式并非都重要；真正决定局部几何的是边界上那几条。
• 激活集让问题“降维/分段”：只需考虑激活约束的梯度。

7.6 互补松弛：回答“约束是否起作用 与 价格是否非零 的逻辑对应”

• 动机：不等式是单边的，乘子必须非负；于是自然得到

  • 约束松 ⇒ 价格 0
  • 价格正 ⇒ 约束紧

• 它把“几何激活”与“代数乘子”精确绑定。

7.7 对偶：回答“如何把最优与所有非最优进行全局比较？如何给出误差证书？影子价格从哪来？”

• 动机：原始问题直接比较所有点困难；对偶用下界做全局比较，并给出 gap。
• 影子价格从对偶的敏感性解释自然出现（最优值对约束右端的导数）。

---