首页 > 搜索 > 优化算法中内点法重要吗,为什么凸优化这么重要?

优化算法中内点法重要吗,为什么凸优化这么重要?

互联网 2020-10-23 17:13:07
在线算命,八字测算命理

觉得有必要写在前面的话:本答案主要面向运筹学、管理科学、运营管理、工业工程、系统工程等相关专业的以及其他对凸优化感兴趣的朋友。本人对机器学习、深度学习以及人工智能所知甚少,在此不便置喙。

以下是原答案。

我基于自己的理解聊一聊凸优化,具体实际中的凸优化的用处各位答主也给出了相应的答案,在此就不赘述。因为不了解题主的背景和基础,就尽量浅显地谈起吧,不会放太多理论推导。不过在看我的回答之前,可以先了解下凸函数、凸集、凸锥(简称“三凸”)的定义。

首先,我们还是要看下,什么是凸优化?抛开凸优化中的种种理论和算法不谈,纯粹的看优化模型,凸优化就是:1、在最小化(最大化)的要求下,2、目标函数是一个凸函数(凹函数),3、同时约束条件所形成的可行域集合是一个凸集。以上三个条件都必须满足。而世间万物千变万化,随便抽一个函数或集合它都可能不是凸的。

所以,先回答题主的第一个问题,这个世上的绝大部分优化问题当然不是凸优化问题。既然如此,为什么凸优化这么重要呢,以及凸优化有什么用呢?(另外,凸优化并不能看成是某一种优化方法)无非三点:

1、还是有相当一部分问题是或等价于凸优化问题。有许多问题都可以直接建立成凸优化模型(比如:线性规划LP(Linear Programming)、某些特殊的二次规划QP(Quadratic Programming)、锥规划CP(Conic Programming)其中包括:要求约束中变量落在一个二阶锥里的二阶锥规划SOCP(Second Order Cone Programming)、要求约束中变量是半正定矩阵的半定规划SDP(Semi-Definite Programming)等)。以上这些类型,总之就是要符合凸优化上述的要求。需要说明的就是,许多可行域都可以看作是凸锥(Convex Cone)的交集,所以将以上一些类型的约束混合起来,依然是凸优化问题。

另外还有一些问题,可以等价的转化为凸优化问题。例如 Linear-Fractional Programming (LFP),目标函数是两个仿射函数(Affine Function)的比,约束是一个多面体。这种目标函数具有既是拟凸又是拟凹的性质,通过一个叫做 Charnes-Cooper transformation 的转化,可以变成一个线性规划。同时,如果我们要最大化 LFP 的目标函数,且其约束仅是一个0-1整数约束(这显然不是一个凸集),我们可以将其直接松弛(Relax)成0到1的约束,并且和原问题等价。因为最大化拟凸函数,最优值一定可以落在可行域的极点上。这个结论可以用来帮助解决 Multi Nomial Logit(MNL)选择模型下的商品搭配问题( Assortment Optimization)。

又例如,与组合优化相关的整数规划模型里,当最小化一个线性函数 c^Tx ,变量 x 只能取整数,约束条件为 Ax\geq b 时,如果 b 为整数向量且 A 是完全幺模(Totally Unimodular)的矩阵,我们可以将原问题松弛,即将整数约束去掉,变成线性规划。此时的最优解必然仍为整数,且即是原问题的最优解。这一结论经常用于调度(Scheduling)问题和指派(Appointment)问题。以上两类问题即是与凸优化直接等价的问题,还有一些优化问题本身就是NP-Hard,怎么处理我们后面再说。

2、大部分凸优化问题解起来比较快,也即多项式时间可解问题(P)。如果你的问题能直接或间接(但必须是等价的)转化成上面我提到的那些类型,那恭喜你,后面的事儿基本就可以交给solver啦,当然大规模问题还需要考虑诸如列生成(Column Generation)之类的方法,提高运算效率。

那为什么大部分凸优化解起来比较快呢?这涉及到凸函数的局部最优即全局最优的性质以及凸集分离定理(Seperation Theorem)。我们形象一点来思考这个问题,而不拘泥于理论。如果了解凸函数(或凹函数)的定义,我们可以想象成站在函数的曲线上去搜索最优解,所要做的无非就是向下到底(或向上到顶),需要考虑的是用什么样的角度迈出第一步以及每的步子要迈多大才更快的到达最优值。同时,作为凸集的可行域,让我们更容易在有限范围内迅速锁定最优解,而不用四处打探。(以下为简单说明这个道理,脑补了一段情节,对理论熟悉的可以略过)

以线性规划为例(目标函数既凸且凹,所以最大化最小化皆可),想象你在目标函数那个超平面上一路狂奔,因为是最小化(或最大化),你得往觉得最轻松(或费劲)的下坡(上坡)方向跑,跑着跑着,你就碰到可行域这个多面体的墙壁了。没关系,你感觉贴着壁的某个方向还是可以轻松(或费劲)地继续跑,跑着跑着到了一个拐角,即所谓的极点。你觉得再走下去就费劲(或省力)了,这样就找到了一个最优的极小值(极大值),否则,你可以沿着墙壁继续走下去。如果,这个时候的可行域不是凸集,而是被人胡乱咬了一口,形成了凹凸不平的缺口。如上方法搜索,你可能已经到达这个缺口的某一个角落,前方已经没有任何能改善你可行解的道路了,你可以就此停止吗?不能!因为想象有另一个你,也如上所述,跑到了这个缺口的另一个无处可走的角落,他也认为自己可以停止了,那你们就还需要比较两个各自所在的位置的解,哪一个会更优。当然,可能还有第三个你,第四个你。。。但不要忘了,每一个你的搜索都需要时间,最终的比较也需要时间(除非你们之间没有缺口,可能都会继续跑下去,到达了一个共同的最优值)。所以非凸的可行域要比一个凸集的可行域麻烦的多。(注:以上形象化的描述的未必就是多项式时间的算法。现实中如单纯形法就不是多项式时间的算法,但实际运用中仍然很高效。)

当然,也有例外,即虽然是凸优化但不是多项式时间可解的。比如在约束中,要求变量是一个Copositive 矩阵或者 Completely Positive 矩阵,这两种矩阵所在的锥恰为对偶锥。此类问题很难解的原因在于,你要去检查一个矩阵是不是落在这样的锥里,就已经不是多项式时间可以解决的了,更不用说整个优化问题。

3、很多非凸优化或NP-Hard的问题可以转化(并非是等价的)为P的凸优化问题。并给出问题的界或近似。这对如何设计合理的算法,或衡量算法结果的优劣起到很大的帮助非凸优化的问题基本上都是NP-Hard的,所以要找到其最优解,理论上是不确定有一个多项式时间的算法的,所以这时候会考虑设计一些近似算法,或者启发式算法,就要依靠凸优化。要把一个优化问题转化为凸优化的方法和例子有很多,以下试举几例说明。

对偶(Duality)是每个学习运筹学或者凸优化的人都必须熟练掌握的方法,对偶有很多种,本科运筹就教会大家写一个线性规划的对偶形式,高等数学里面也会提到用到拉格朗日乘子之类的约束优化问题,也即解拉格朗日对偶或者KKT条件。一般的,对于许多非凸优化的问题,我们仍然可以写出它的拉格朗日对偶。如原问题如下 \{\min_{x}f(x),\ \text{s.t.}\ g_i(x)\geq 0\} ,拉格朗日对偶为 \max_{\lambda\geq 0}\min_{x}f(x)-\lambda^Tg(x) ,其中 \ g(x)=(g_1(x)...g_n(x))^T 。可以看到 f(x)-\lambda^Tg(x) 是关于 \lambda 的线性函数,因此 \min_{x}f(x)-\lambda^Tg(x) 一定是一个关于 \lambda 的凹函数。因此,由我们之前给的定义来看,拉格朗日对偶永远都是一个关于对偶变量的凸优化问题,并且根据弱对偶定理,可以给出原问题的下界。

松弛(Relaxation)也是常用的方法之一,在第一点里,我们举了一些例子可以通过松弛,去掉整数约束,使其等价为凸优化。通常情况下,我们松弛原问题,只能得到一个可行域更大的问题,如果原问题是求最小,则松弛后的问题的最优值一定小于等于原问题的最优值,这也是一种给出下界的方法。松弛不仅仅用于整数约束,只要利于将可行域非凸变为凸集皆可。例如,某问题有一约束为 x^2+bx+c=0 ,就不构成一个凸集,但等价于 x^2+bx+c\leq 0x^2+bx+c\geq 0 ,前一个不等式即构成凸集,因此我们可以将后一个不等式从约束中去除,就得到原问题的一个凸优化松弛问题。

我们还可以举一个同时用到对偶加松弛的例子,在第二点的最后,我们聊到Copositive(CoP) 矩阵与 Completely Positive(CP)矩阵,他们的锥与半正定(PSD)矩阵锥的关系是 CP\subset PSD\subset CoP 。组合优化中很多问题都可以松弛成一个Completely Positive规划(去掉一个矩阵为Rank 1 的条件),由于Copositive和Completely Positive互为对偶锥,所以我们可以先写出对偶,写成 Copositive 规划,然后在某些假设之下,能证明 Copositive 规划与原问题等价。当然,如果没有那些假设,还可以尝试将Completely Positive约束,松弛成半正定矩阵的约束,因为Completely Positive必然是半正定,同时还加上Completely Positive的性质,如矩阵的所有元素都大于等于0。这样我们就得到了原问题的一个凸优化且易解的对偶松弛问题,一个SDP Relaxation。

当然,相应的处理方法还有很多,面临一些随机优化(Stochastic Optimization)、机会约束规划(Chance Constrained Programming)、鲁棒优化(Robust Optimization)、离散凸优化(Discrete Convex Optimization)问题,还有更多其他的处理方法,就不在此一一道来。更多内容,可以看各位答案里推荐的书籍,都是经典教材。

综上三个方面,供题主参考,也请各位多多指教,谢谢!

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多