KNOWECON WIKI

ARTICLE

Convex Optimization

凸优化 (Convex Optimization) 凸优化是数学优化中一类具有特殊结构的优化问题：其目标函数为凸函数，且可行域为凸集。凸优化问题的一个核心优良性质是：任何局部最优解必为全局最优解，这使得此类问题在理论和算法上高度可处理。凸优化广泛应用于经济学、金融学、机器学习、自动控制和运筹学等多个学科，是现代计算科学和工程数学的基石之一。 凸集与凸函数 凸

浏览 0 更新 2025-10-31

凸优化 (Convex Optimization)

凸优化是数学优化中一类具有特殊结构的优化问题：其目标函数为凸函数，且可行域为凸集。凸优化问题的一个核心优良性质是：任何局部最优解必为全局最优解，这使得此类问题在理论和算法上高度可处理。凸优化广泛应用于经济学、金融学、机器学习、自动控制和运筹学等多个学科，是现代计算科学和工程数学的基石之一。

凸集与凸函数

凸集是指集合中任意两点之间的线段完全包含于该集合内。形式化地，集合 C⊆RnC \subseteq \mathbb{R}^n 为凸集当且仅当对任意 x,y∈Cx, y \in C 和 θ∈[0,1]\theta \in [0, 1]，均有：

θx+(1−θ)y∈C\theta x + (1 - \theta) y \in C

常见的凸集包括：仿射子空间、半空间、多面体、范数球、半正定锥等。凸集的保凸运算——如交集、仿射变换、透视函数和线性分式变换——提供了构造复杂凸集的系统方法。

凸函数 f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} 定义在凸集上，满足对于任意 x,yx, y 和 θ∈[0,1]\theta \in [0, 1]：

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) f(y)

即函数在任意弦上不高于弦的端点连线，几何上意味着函数图像的上方区域（上方图）为凸集。对于可微函数，凸性等价于其一阶泰勒展开为全局下界：

f(y)≥f(x)+∇f(x)⊤(y−x),∀x,yf(y) \geq f(x) + \nabla f(x)^\top (y - x), \quad \forall x, y

对于二次可微函数，等价于 Hessian 矩阵处处半正定：∇2f(x)⪰0\nabla^2 f(x) \succeq 0。验证凸性的常用方法包括直接使用定义、一阶条件、二阶条件，以及利用保凸运算（非负加权和、仿射复合、逐点最大值等）。

标准形式与对偶理论

凸优化问题的标准形式为：

minimize⁡f0(x)subject tofi(x)≤0,i=1,…,maj⊤x=bj,j=1,…,p\begin{aligned} \operatorname{minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, \ldots, m \\ & a_j^\top x = b_j, \quad j = 1, \ldots, p \end{aligned}

其中目标函数 f0f_0 和不等式约束函数 fif_i 均为凸函数，等式约束为仿射函数。线性规划、二次规划、半正定规划和锥规划均为凸优化的特殊子类。

拉格朗日对偶性是凸优化的核心理论基础。引入 Lagrange 乘子 λi≥0\lambda_i \geq 0（不等式约束）和 νj\nu_j（等式约束），定义Lagrange 函数：

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνj(aj⊤x−bj)L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{j=1}^{p} \nu_j (a_j^\top x - b_j)

由此定义Lagrange 对偶函数 g(λ,ν)=inf⁡xL(x,λ,ν)g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)，它是原问题最优值的下界。对偶问题为在 λ⪰0\lambda \succeq 0 约束下最大化 g(λ,ν)g(\lambda, \nu)，该问题始终为凹最大化问题，因而易于求解。

弱对偶性 d∗≤p∗d^* \leq p^* 恒成立。当原问题为凸优化且满足 Slater 条件（存在严格可行内点）时，强对偶性 d∗=p∗d^* = p^* 成立，即对偶间隙为零。强对偶性使得许多凸优化问题可通过求解对偶问题获得原问题的最优解。

Karush-Kuhn-Tucker (KKT) 条件给出凸优化问题最优解的充要条件：若强对偶成立且所有函数可微，则 x∗x^* 为最优解当且仅当存在 λ∗,ν∗\lambda^*, \nu^* 满足驻点条件、原始可行性、对偶可行性和互补松弛条件 λi∗fi(x∗)=0\lambda_i^* f_i(x^*) = 0。KKT 条件是凸优化算法设计和收敛性分析的理论基石。

求解算法

  • 梯度下降法：最基础的迭代优化方法。沿负梯度方向 −∇f(x)-\nabla f(x) 更新，步长由线搜索或固定学习率确定。对于光滑凸函数，梯度下降以速率 O(1/k)O(1/k) 收敛；对于强凸函数，可达到线性收敛速率 O(γk)O(\gamma^k)。随机梯度下降（SGD）及其变体在大规模机器学习的非凸训练中也被广泛使用。
  • 牛顿法：利用目标函数的二阶信息（Hessian 矩阵），更新方向为 −∇2f(x)−1∇f(x)-\nabla^2 f(x)^{-1} \nabla f(x)。牛顿法具有二阶收敛速率，精度极高，但每次迭代计算 Hessian 和求解线性系统的代价高昂，适用于中小规模问题。
  • 内点法：求解带约束凸优化问题的一类核心算法。通过在目标函数中加入对数障碍函数将不等式约束转化为惩罚项，求解一系列无约束或等式约束子问题逼近原问题的最优解。内点法具有多项式时间复杂度，是线性规划、二次规划和半正定规划的主流求解方法，也是 CVX、Gurobi 等现代求解器的底层技术。
  • 交替方向乘子法 (ADMM)：求解可分解的大规模凸优化问题。将原问题拆分为若干子问题交替求解，结合对偶上升法和对偶分解，特别适用于分布式优化和统计学习中含正则化项的各类问题。ADMM 在高维回归、矩阵补全和图像处理中表现出色。

在经济学中的应用

凸优化为经济学中的诸多核心问题提供了统一的数学框架。

消费者理论中，效用最大化问题是在预算约束 p⊤x≤wp^\top x \leq w 下最大化拟凹效用函数 u(x)u(x)——等价于最小化 f(x)=−u(x)f(x) = -u(x)（当 uu 为凹函数时 ff 为凸函数），构成凸优化问题。由此导出的需求函数满足 Walras 定律、零次齐次性和 Slutsky 方程的负半定性。由凸优化对偶理论可直接推导出支出最小化问题为效用最大化的对偶问题，支出函数 e(p,u)e(p, u) 即为值函数，两者通过对偶性紧密联系。

生产者理论中，成本最小化给定技术约束下的要素投入组合是典型的凸优化问题，且成本函数与生产函数之间同样满足对偶关系。利润最大化通常是非凸问题，但在完全竞争市场假设下，利润函数可表示为成本函数的共轭函数，再次利用凸共轭的对偶结构。

福利经济学中，帕累托最优配置可通过求解社会规划者问题——最大化社会福利函数的加权和——实现，该问题在凸偏好和凸技术假设下为凸优化。这一性质构成了福利经济学第二定理的数学基础：任何帕累托最优配置在适当的转移支付下均可由竞争性市场均衡实现。

计量经济学中，最小二乘法和各类惩罚回归（LASSO、岭回归）本质上是无约束或带范数约束的凸优化问题。最大似然估计对于指数族分布的对数似然函数为凹函数，因此最大化似然等价于凸优化。工具变量估计中的广义矩方法（GMM）和现代高维统计中的 Dantzig 选择器等均依赖于凸优化算法的数值稳定性。