凸优化是数学优化的一个分支，研究如何在凸的可行集上最小化凸函数。其核心性质是：每个局部极小值也是全局极小值。这使它有别于一般的非线性优化，后者的局部最优解可能并非全局最优。凸性还使某些一阶最优性条件成为充分条件，为数学分析和数值求解方法奠定了基础。(mit.edu)
数学表述
集合 (C\subseteq\mathbb{R}^n) 若包含其任意两点之间的整条线段，就称为凸集： [ \theta x+(1-\theta)y\in C \quad\text{其中 }x,y\in C,\quad 0\leq\theta\leq1. ] 函数 (f:C\to\mathbb{R}) 若满足 [ f(\theta x+(1-\theta)y) \leq \theta f(x)+(1-\theta)f(y), ] 就称为凸函数。也就是说，它在插值点处的函数值不超过端点函数值的相应插值。凸函数不一定可微。(mit.edu)
标准的约束问题可表述为 [ \begin{aligned} \operatorname{minimize}_{x}\quad &f_0(x)\ \operatorname{subject\ to}\quad &f_i(x)\leq0,\quad i=1,\ldots,m,\ &Ax=b, \end{aligned} ] 其中，目标函数 (f_0) 和不等式约束函数 (f_i) 在一个共同的凸定义域上都是凸函数。等式约束是仿射的。它们与凸的不等式下水平集的交集也是凸集，因此上述表述定义了一个凸优化问题。在凸集上最大化凹函数，只需将目标函数取负，即可转化为等价的凸优化问题。(web.stanford.edu)
最优性与对偶
对于可微凸函数，梯度给出一个全局下界： [ f(y)\geq f(x)+\nabla f(x)^{T}(y-x). ] 因此，在无约束问题中，满足 (\nabla f(x)=0) 的驻点就是全局最优点。在凸集 (C) 上，相应的条件为 [ \nabla f(x)^{T}(y-x)\geq0 \quad\text{对所有 }y\in C. ] 与一般非线性优化不同，这一条件不仅必要，而且充分。(mit.edu)
拉格朗日对偶为约束问题引入拉格朗日函数： [ L(x,\lambda,\nu) =f_0(x)+\sum_i\lambda_i f_i(x)+\nu^{T}(Ax-b). ] 对 (x) 取下确界，就得到对偶函数。在 (\lambda_i\geq0) 的约束下最大化该函数，便得到对偶问题；其可行目标值都是原问题最小值的下界。原问题与对偶问题最优值之差称为对偶间隙。(see.stanford.edu)
强对偶意味着这一间隙为零。在适当的约束资格条件下，强对偶成立，其中尤为重要的是斯莱特条件：其标准形式要求存在一个满足等式约束的点，该点位于共同定义域的相对内部，并严格满足所有不等式约束。对于可微的凸优化问题，卡鲁什—库恩—塔克条件——原问题可行性、对偶可行性、驻点条件和互补松弛条件——是最优性的充分条件；在适当的约束资格条件下，它们也是必要条件。(see.stanford.edu)
重要的问题类别
线性规划采用仿射目标函数和仿射约束。凸二次规划允许目标函数具有如下形式： [ \tfrac12x^{T}Qx+c^{T}x, ] 其中 (Q) 是对称半正定矩阵，约束则为仿射约束。这些类别展示了如何通过明确的代数结构检验凸性。(web.stanford.edu)
二阶锥规划包含如下范数约束： [ |Ax+b|_2\leq c^{T}x+d. ] 半正定规划在线性目标函数下求最小值，其约束要求对称矩阵的仿射组合为半正定矩阵。它推广了若干常见的优化问题形式，并用于工程分析与设计。(web.stanford.edu)
识别这些标准形式十分重要，因为它们的结构为专用求解器、对偶理论和复杂性分析提供了基础。应用问题有时需要重新表述，其凸结构才会显现出来。(stanford.edu)
数值方法
梯度下降按下式更新无约束问题的迭代点： [ x_{k+1}=x_k-\alpha_k\nabla f(x_k). ] 对于梯度满足利普希茨连续性的凸目标函数，适当的步长可以保证收敛。在标准假设下，目标函数值的误差以 (O(1/k)) 的速率下降。若函数具有强凸性，则采用适当步长可以实现几何收敛。这些保证依赖于光滑性和曲率，而不只是凸性。(mit.edu)
投影梯度法将梯度更新后的点投影到闭凸集上，以恢复可行性。近端梯度法处理形如 (f+g) 的复合目标函数，其中 (f) 是光滑函数，而 (g) 可以是非光滑函数。这类方法将针对 (f) 的梯度步与针对 (g) 的近端最小化相结合，因此在非光滑部分的近端算子易于计算时尤其适用。(ocw.mit.edu)
牛顿法利用二阶信息，而内点法通过障碍函数或原始—对偶表述来求解约束问题。在指定假设下，许多标准凸优化问题类别都具有多项式时间复杂度保证。不过，实际性能仍取决于维数、数值条件、稀疏性，以及计算相关量或求解基础子问题的成本。(ocw.mit.edu)
应用与适用范围
凸优化为机器学习、统计学、信号处理、通信和控制理论提供支持。最小二乘拟合、凸损失最小化以及适当的正则化惩罚项，都是重要的统计应用实例。其工程应用包括资源分配、电路设计和系统分析。(web.stanford.edu)
对于非凸问题，凸松弛用易于求解的凸近似替代难以处理的约束或目标函数结构。这类表述可以提供界和近似解，但并不保证得到原问题的最优解。特别是，整数规划的凸松弛可能给出分数值而非整数值的决策变量。(stanford.edu)
因此，不能把凸性等同于计算必然容易的普遍保证：问题的表示方式、所要求的精度，以及计算时能够如何获取问题信息，仍然是其计算复杂性的重要组成部分。(stanford.edu)