凸优化是具有如下形式的优化问题：
寻找$f_{0}(x)$的最小值，同时满足$f_{i}<=b_{i} i=1,...,m$的条件
其中$f_{0},...,f_{m}:R^n \rightarrow R$是凸的，即：
$f_{i}(\alpha x + \beta y) <= \alpha f_{i}(x) + \beta f_{i}(y) $
对于任意的实数x，y和任意的实数$\alpha$, $\beta$，需要满足$\alpha + \beta =1$且$\alpha>=0$, $\beta>=0$。
最小二乘问题和线性规划问题都是一般凸优化问题的特例。
一般而言，对于凸优化问题的解决方案没有解析公式，但是（与线性规划问题一样）现存的解决这些问题的方法一般非常有效。内点法（Interior-point method）在实践中工作得很好，已经证明在某些情况下，该方法通过一些不超过问题维数的多项式的操作可以将问题解决到指定的精度。与解线性程序的方法一样，这些方法也相当可靠。我们可以轻松解决当前台式计算机上数百个变量和数千个约束条件下的问题，最多只需要几十秒。通过利用问题结构（例如稀疏性），我们可以解决更大的问题，甚至包含数千个变量和约束条件。
我们还不能断言求解一般凸优化问题是如同求解最小二乘或线性规划问题那样的成熟的技术。对于解决一般非线性凸优化(general nonlinear convex optimization)的内点方法的研究仍然是一个非常活跃的研究领域，最好的方法是什么尚未达成共识。
[描述来源：Boyd, S.; Vandenberghe, L. (2004). Convex Optimization . Cambridge University Press]
最小二乘、线性规划、具有线性约束的凸二次最小化、具有凸二次约束的二次最小化、圆锥优化、几何编程、二阶锥规划、半定规划和具有适当约束的熵最大化都是凸最小化问题，或者可以通过变量变换将其转化为凸最小化问题。目前常用于求解凸优化问题的方法有：捆集法/束方法（"Bundle methods" ）、次梯度投影方法（Subgradient projectionmethod）、内点法（Interior-point method）等。
[描述来源：维基百科URL：https://en.wikipedia.org/wiki/Convex_optimization#Examples]
发展历史
描述
关于凸优化的研究历史悠久，也非常多。1947年，当George Dantzig还在为美国空军工作时，他发明了单纯形法（simplex algorithm），这是一种在数学优化领域中常用于线性规划问题的数值求解。单纯形是N维中的N+1 个顶点的凸包，是一个多胞体：直线上的一个线段，平面上的一个三角形，三维空间中的一个四面体等等，都是单纯形。在20世纪70年代Claude Lemaréchal和Phil Wolfe针对凸最小化问题提出了下降的“束方法”，Kiwiel则提出了我们现在更熟悉的束方法的形式和对其的完全收敛分析。内点法的想法最早是由John von Neumannti提出的，但是由Nesterov和Nemirovski 首先指出内点方法可以解决许多凸优化问题的，他们证明算法的迭代次数受解决方案的维数和精度的多项式限制。
使用凸优化来寻找非凸性问题的范围是凸优化问题的研究重点之一，Goemans和Williamson提出了随机逼近算法（randomized approximation algorithm），其使用了一种简单而优雅的技术，将解决方案随机舍入为非线性编程放松，这种松弛既可以被视为一个半定规划（semidefinite program），也可以被视为一个特征值最小化问题（eigenvalue minimization problem）。
Nesterov于1998年研究了具有对角二次约束的全局二次优化问题的半定松弛（semidefinite relaxation）的质量，并证明了这样的松弛可以以μ=（π/ 2）-1的相对精度近似准确解。Parrilo随后证明如何构造已经证明不可行的完整的多项式大小的半定规划条件（semidefinite programming condition）集合，其所采用的主要工具是多元多项式的平方和分解的半定规划公式（semidefinite programming formulation），以及来自实代数几何的一些结果。
除了在统计分析模型和数学理论中被广泛研究，凸分析还是经济和金融的核心，也是许多研究结果的基础。例如，分离超平面定理和无套利假设一起用于推导价格和风险中性概率的存在。凸自动优化，特别是我们解决半定规划的能力，最近在自动控制理论中受到了特别的关注。嵌入式（凸面）优化的一个很好的例子是模型预测控制，这是一种自动控制技术，需要在每一步中求解（凸）二次方程。模型预测控制现在也广泛用于化学过程控制行业。电子电路设计是凸面优化（尤其是几何编程）历史悠久的另一个应用领域。可以说，凸优化是现代经济与工业发展的重要基础。
主要事件
A | B | C | |
1 | 年份 | 事件 | 相关论文/Reference |
2 | 1947 | George Dantzig发明了单纯形法（simplex algorithm） | Dantzig, G. (2016).Linear Programming and Extensions.Princeton University Press. |
3 | 1985 | Kiwiel则提出了我们现在更熟悉的束方法的形式和对其的完全收敛分析 | Kiwiel, K.(1985). Methods of Descent for Nondifferentiable Optimization. Berlin: Springer Verlag. p. 362 |
4 | 1994 | Nesterov和Nemirovski 首先指出内点方法可以解决许多凸优化问题，他们证明算法的迭代次数受解决方案的维数和精度的多项式限制 | Nesterov, Y. and Nemirovskii, A. (1994). Interior-Point Polynomial Methods in Convex Programming. Society for Industrial and Applied Mathematics. |
5 | 1995 | Goemans和Williamson提出了随机逼近算法（randomized approximation algorithm） | Goemans, M. X. and Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the Association for Computing Machinery, 42(6):1115–1145. |
6 | 1998 | Nesterov研究了具有对角二次约束的全局二次优化问题的半定松弛（semidefinite relaxation）的质量，并证明了这样的松弛可以以μ=（π/ 2）-1的相对精度近似准确解 | Y. Nesterov. Semidefinite relaxations and nonconvex quadratic optimization. Optimization Methods and Software, 9(1-3):141–160, 1998. |
7 | 2003 | Parrilo证明如何构造已经证明不可行的完整的多项式大小的半定规划条件（semidefinite programming condition）集合 | P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming Series B, 96:293–320, 2003. |
发展分析
瓶颈
有关凸优化的研究已经比较成熟，并且凸优化问题的复杂度实际上也不高，在实际应用中，很少有问题是真正的凸优化问题，大部分需要对约束进行宽松转为凸优化问题求解。
未来发展方向
主要是向非线性凸优化或非凸优化问题方向进行研究，进行更实际的应用分析，以及对算法的复杂度和分析效率进行研究。
By Yuanyuan Li