覃含章作者

浅谈变分不等式与凸优化

【编者按】

变分不等式(Variational Inequality,以下简称VI),其实是一种很有意思的建模思路。不过即使在我和做优化的同行的日常交流当中,一般话题也很少能交流到VI上。本回答,我将给一个关于VI直观和大概的介绍,并指出它的一些潜在价值。

的正式数学形式定义为:任给定义在巴纳赫空间 的一个子集上的泛函 ,其中的对偶空间。等价于求满足下列条件的点 ,使得 (注意内是一定存在的)

为了直观起见,我们只考虑是n维实数域上任意的闭凸集(closed convex set)。这当然只是VI能够model的很小一部分情况,不过在对本篇回答旨在给的直观介绍已经足够了。

在研究VI这个领域方面,我国的何炳生老师应该是国内领先,他也是专注了一辈子这个方向的研究。比如之前他和斯坦福的叶荫宇老师在证明ADMM算法收敛性的工作里就集中使用了VI相关的技巧。本文也是主要参考了何老师主页上关于VI的讲义,如果大家对VI想有更深入的了解(比如具体不同算法的设计和分析理论),强烈建议阅读何老师网站上更加深入的讲义内容。

首先我们指出一般的光滑凸优化都可以看成一个单调的VI问题

我们考虑凸优化问题:        

,注意是定义在上的可微凸函数。利用凸优化的最优条件,我们知道该问题的最优解等价于在该点上的所有可行方向都不是梯度下降方向。证明也很简单,必要性方向用反证法:给定一个 ,如果存在这样一个方向,那么必然就存在使得,这和的定义矛盾。充分性方向利用凸函数的局部极小=全局极小的性质也是显然的。

然而上述条件就等价于的定义!

我们还可以进一步指出,当我们想显式求解一个凸优化问题的时候(比如我们将X 定义为,这个时候我们等价的形式为将VI mapping拓展为 。请读者自行练习,应该基于前一部分的基础是很容易推导的(提示:拉格朗日对偶;KKT条件)。

另外,我们指出可微并不是必要的,不然就有违我一开始所说的VI非常general了。这个时候,我们的凸优化问题仍然等价于求对应拉格朗日函数的鞍点,即定义 ,那么鞍点等价于满足条件

这个时候的等价VI形式仍然留给大家做练习。值得注意的是,这个时候的VI会长的和之前我们看到的形式略有区别,这也叫做混合变分不等式,但很多时候也就不加区分统称VI了。(提示:可以将中分离出来)都不可微的情况当然也是可以的,不过这个时候就要使用次梯度(subgradient)来定义了。

VI还和一类更general的非线性互补问题等价。具体来说,非线性互补问题描述了一类集合,这类问题在资源供给,交通疏导中都有广泛的运用。

最后,我想着重提一下VI在刻画multi-agent system,即具有可分离结构的优化问题中的应用。不失一般性,我们就考虑2-block的情形,考虑如下优化问题 ,即我们的目标函数对于变量可分离,我们的线性约束同样对于变量可分离。简单起见,假设 可微,我们对于这个问题的等价中的F取为 .

这个时候,虽然本文我并没有讲VI的算法应该如何设计,但大家应该已经能感觉到VI的mapping已经抓到了这个问题的可分离结构,即我们完全可以分布式地更的值而不需要知道另一个变量准确的值(当然,对偶变量的更新需要所有变量的值,可以把对偶变量看作coordinator)。那么,假设原问题里我们可以把原空间分解成大量小的子问题(比如我们有n个可分离的目标函数和一个n-block可分离的约束矩阵),我们可以想象这个VI具有一个可以高度分布式的算法。这也是n-block ADMM算法(虽然一般来说n>=3理论上的收敛性就不太好保证了)在实际中可以使用的思路。

最后的最后,如果我们考虑更一般的情形,约束具有可分离结构但不一定是线性的,这类multi-agent optimization问题实际上代表了计算一类generalized Nash equilibrium:直观来说,也就是每个agent都有自己private的目标函数和约束,且在决策时也只能控制自己的那一部分变量,VI同样能给出计算这类equilibrium的一个formulation。具体详情请有兴趣的同学可以参阅参考文献[4]。

参考文献

[1] http://maths.nju.edu.cn/~hebma/

[2] Chen, Caihua, et al. "The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent." Mathematical Programming 155.1-2 (2016): 57-79.

[3] He, Bingsheng, Min Tao, and Xiaoming Yuan. "Convergence rate analysis for the alternating direction method of multipliers with a substitution procedure for separable convex programming." Mathematics of Operations Research 42.3 (2017): 662-691.

[4] Facchinei, Francisco, and Christian Kanzow. "Generalized Nash equilibrium problems." 4OR 5.3 (2007): 173-210.

运筹OR帷幄
运筹OR帷幄

『运筹OR帷幄』是大数据人工智能时代的运筹学,普及运筹学和优化理论,及其在人工智能和供应链中的应用。

入门梯度下降凸优化变分不等式
2
相关数据
收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

凸优化技术

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

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

推荐文章
暂无评论
暂无评论~