凸优化

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

来源:维基百科
简介

凸优化是具有如下形式的优化问题:

寻找$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) $

对于任意的实数xy和任意的实数$\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)等。

[描述来源:维基百科URLhttps://en.wikipedia.org/wiki/Convex_optimization#Examples]

发展历史

描述

关于凸优化的研究历史悠久,也非常多。1947年,当George Dantzig还在为美国空军工作时,他发明了单纯形法(simplex algorithm),这是一种在数学优化领域中常用于线性规划问题的数值求解。单纯形是N维中的N+1 个顶点的凸包,是一个多胞体:直线上的一个线段,平面上的一个三角形,三维空间中的一个四面体等等,都是单纯形。在20世纪70年代Claude LemaréchalPhil Wolfe针对凸最小化问题提出了下降的束方法Kiwiel则提出了我们现在更熟悉的束方法的形式和对其的完全收敛分析。内点法的想法最早是由John von Neumannti提出的,但是由NesterovNemirovski 首先指出内点方法可以解决许多凸优化问题的,他们证明算法的迭代次数受解决方案的维数和精度的多项式限制。

使用凸优化来寻找非凸性问题的范围是凸优化问题的研究重点之一,GoemansWilliamson提出了随机逼近算法(randomized approximation algorithm),其使用了一种简单而优雅的技术,将解决方案随机舍入为非线性编程放松,这种松弛既可以被视为一个半定规划(semidefinite program),也可以被视为一个特征值最小化问题(eigenvalue minimization problem)。

Nesterov1998年研究了具有对角二次约束的全局二次优化问题的半定松弛(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

NesterovNemirovski 首先指出内点方法可以解决许多凸优化问题,他们证明算法的迭代次数受解决方案的维数和精度的多项式限制

Nesterov, Y. and Nemirovskii, A. (1994). Interior-Point Polynomial Methods in Convex Programming. Society for Industrial and Applied Mathematics.

5

1995

GoemansWilliamson提出了随机逼近算法(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

相关人物
乔治·B·丹茨格
乔治·B·丹茨格
克劳德
克劳德
ClaudeLemaréchal是法国应用数学家,也是法国格勒诺布尔附近INRIA的前高级研究员。 在数学优化中,ClaudeLemaréchal因其在非线性优化的数值方法方面的工作而出名,特别是对于不可扭曲扭结问题。 Lemaréchal和菲尔。沃尔夫开创了用于凸面最小化的束下降方法。 机构: 法国国家信息与自动化研究所
阿卡迪亚·内米洛夫斯基
阿卡迪亚·内米洛夫斯基
佐治亚理工学院斯图尔特工业和系统工程系的教授。他一直是连续优化领域的领导者,并因其在椭球法、现代内点法和鲁棒优化方面的工作而闻名。曾获得2003年冯‧诺伊曼运筹学理论奖。
帕布洛·A·帕里罗(音译)
帕布洛·A·帕里罗(音译)
麻省理工学院的Pablo A. Parrilo于2016年被任命为电气和电子工程师协会的研究员,负责半定优化和平方和优化。他于2018年被任命为SIAM研究员。
冯·诺依曼
冯·诺依曼
约翰·冯·诺伊曼(德语:John von Neumann,1903年12月28日-1957年2月8日),原名诺依曼·亚诺什·拉约什(匈牙利语:Neumann János Lajos),出生于匈牙利的美国籍犹太人数学家,现代电子计算机与博弈论的重要创始人,在泛函分析、遍历理论、几何学、拓扑学和数值分析等众多数学领域及计算机学、量子力学和经济学中都有重大贡献。
简介
相关人物