形式陈述

标准凸优化问题写为

$$ \begin{aligned} \text{minimize}\quad & f_0(x)\\ \text{subject to}\quad & f_i(x)\le0,\quad i=1,\ldots,m,\\ & Ax=b, \end{aligned} $$$$\begin{array}{rl}\text{minimize}& f_0(x)\\ \text{subject to}& f_i(x)\le 0,i=1,\dots ,m,\\ & Ax=b,\end{array}$$

其中 $f_0,f_i$$f_0,f_i$ 均为凸函数，等式约束必须是仿射的。于是可行域是凸集。若 $x^*$$x^{\ast }$ 是局部最优解，则它也是全局最优解；若目标在凸可行域上严格凸，则最优解至多一个。若可微凸目标定义在开凸域上，且 $x^*$$x^{\ast }$ 是域内点，则无约束条件 $\nabla f_0(x^*)=0$$\mathrm{\nabla }{f}_0(x^{\ast })=0$ 对全局最优既必要又充分；有约束情形需使用法锥或 KKT 条件并核对约束资格。

直觉

凸可行域允许在任意两个方案间插值，凸目标保证插值不会产生隐藏的更高“山脊”。因此局部信息能够控制全局最优。

例子与边界

线性规划、最小二乘、二次规划（半正定 Hessian）、范数正则化和半定规划都是凸优化。约束 $g(x)=0$$g(x)=0$ 即使 $g$$g$ 凸也通常产生非凸集合，例如 $x^2=1$$x^2=1$；所以等式必须仿射。把最大化凹函数改写为最小化其负值仍属凸优化。问题的某种代数写法看似非凸，不代表其本质不可凸化；反之，只有目标凸而可行域非凸也不属于标准凸问题。全局最优性质不自动保证最优解存在，仍需闭性、紧性或强制性等条件。

推论与应用

凸优化提供可验证的全局最优性、对偶下界和成熟算法，是统计估计、机器学习、控制和资源分配的共同数学框架。

参考资料

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004，Ch. 4, convex optimization problems and optimality。
• R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1970，§§27–28, minimization of convex functions and constraints。