一步一步走向锥规划 - QP

一般来说凸优化(Convex Optimization, CO)中最一般的是锥规划 (Cone Programming, CP) 问题, 前面我们介绍了点 最小二乘(Least Square, LS)线性规划(Linear Programming, LP)问题, 现在我们介绍一点二次规划(Quadratic Programming)。

引子

Joseph-Louis Lagrange 拉格朗日是变分法(calculus of variations)的建立者之一, 变分法是自微积分发明以后一个重大突破, 对应到离散算法领域, 动态规划(dynamic programming)可以看成是一种变分法。 拉格朗日出生于意大利政府官员家庭, 但是他爸本该留下大笔财富,但是却经营不善, 家道衰落。 于是他爸想让他成为律师, 他从小最喜欢的课程是拉丁文, 对几何有点厌恶。 直到17岁, 他读了天文学家Edmond Halley 哈雷的一片论文, 发现里面有些地方看不完全明白, 就这样迷上了数学, 然后整整1年沉浸在数学之中, 1年后, 他由于数学才华, 而被本地公爵任命为助理教师, 来给部队讲解如何应用Leonhard Euler欧拉的学术来研究弹道理论(ballistics theories)。 从此一发不可收拾踏上微积分的不归路。拉格朗日后期的成就离不开与欧拉的广泛交流和提拔。

对此, 我想说的是, 不喜欢文学,历史,天文学的数学家不是一个好数学家。 其次, 1年在新方向的学习,足以改变一生的命运, 所以当你希望改变时候, 你就在一个新的感兴趣的领域坚持一年的沉浸。 再次, 数学不要深入的太早, 14岁之前还是练练记忆力吧。

随便说一下, 拉格朗日身体一直一般, 但是骗妹妹的水平还是不错的, 第一个老婆是他一个远房的侄女, 但是她身体也不错, 不久就去世了。 第二个老婆是他好友的女儿, 在一片反对声中, 她嫁给了他。 另外, 拉格朗日做人也是相当有一套, 中庸之道学的很好, 他见证了法国各种革命,每次都继续被重用, 但是没有人想过要伤害他。 他的信条之一就是, 我是个小心的外来者, 我得恪守这里的规矩。 对比,他的好友, 大化学家拉瓦锡, 就不幸被处决了。

这次描述的二次规划, 简直就是见证拉格朗日奇迹的旅程。 不管是内值法(interior point),增强拉格朗日法, 还是对偶问题(duality)都离不开拉格朗日。

QP,二次规划概述

在1940年左右(1939年 Leonid Kantorovich 总结发表了线性规划), 线性规划LP被提出来, 10年后, QP作为Non-Linear Programming, NLP被总结发表。

顾名思义, 二次规划就是把一次规划(线性规划, LP)的目标公式扩展到二次函数:

这里 Q 是对称矩阵(Symmetric Matrix)

那么这样修改目标之后, 会带来什么改变?

首先从图上来看, 最大的变化就是二次带来等高线( contour line )不再是直线, 这样使得最值点不再是限制多面体的角上,可能是边上,或者内部。

我们来看一下, 三维立体的情况:

另外, 一般来说, 二次关系带来的还可能是凸和非凸情况产生:

但是对于非凸的情况下, 对应的对称阵是一个不定矩阵(indefinite), 但是对于凸的情况下, 对应的对称阵是一个正定矩阵(positive-definite)。

同时, 这样改变之后有什么好处?

QP第一次统一了LP和LS, 前面我们提到, 当利用不同的距离公式的时候,最优回归参数,可能是LS的情况, 也可能是LP情况。

  1. 欧式距离: 最小二乘法,LS
  2. Hamitton 距离,或者Chebyshev距离: 线性回归, LP

这样,基于利用QP就可以统一描述不同距离公式下的回归的参数求解。

前面, 我们说了QP是LP和LP在不同角度的扩展:

1. QP是LP的扩展, LP是QP在二次项系数为0时候(Q=0)的特例。

2. QP是LS的扩展, LS是QP在一次项系数为0, 二次项系数为I(单位阵),并且没有限制的时候的特例:

所以, QP是把LS的二次项对称单位阵扩展到任意对称阵Q, 再加上LP的一次项。 因为Q是对称矩阵(symmetric matrix),利用矩阵分解 Q = LL^T, 那么QP的二次项可以看成特殊的最小二乘法:

这样我们描述了QP作为LP和LS一般性扩展(特例)的意义

再进一步,为什么要有QP?

依然从LS和LP的扩展说起:

1. Constrained LS 依赖于QP:

2. Randomized LP 依赖于QP:

这样我们描述了QP作为LP和LS必要性扩展的意义

QP 求解概述

在求解之前, 我们先看一下, 求解大概会遇到哪些情况?如下图, 不管semi-definite,还是indefinite的情况下, 大部分情况(大致有如下4种情况), 最值点是分布在feasible region的边界上, 但是在definite情况下, 可能最是内部最值点。

QP怎么求解的?

一般来说, QP的求解主要有两大方面的限制(如下图所示):

首先是Q矩阵, Q矩阵是不是半正定(Semi-Definite)的, 如果不失意味着, 目标函数是非凸(non-convex)的情况。

其次是条件关系, 是不是全部是等式(eqality-constrained), 如果是的话, 就是一个可以直接求解的KKT系统(KKT System), 否则的话,就是一般情况下的Convex QP问题。

KKT 系统是什么?

什么是KKT呢?KKT是3个人的姓的首字母, 分别是Karush, Kuhn和Tucker, 更多细节参考 “一挑三, FJ vs KKT”。

前面我们说了KKT系统是利用KKT条件进行求解的, (in)-equality constraint情况下的Convex QP求解方式。

常见的解法包括:

  1. Direct solution of the KKT system
    1. Full space method
    2. Range space method
    3. Null space method
  2. Active set strategies
  3. Interior-point methods
    1. Central path method
    2. Logarithmic barrier functions

Direct solution of the KKT system

如果目标公式是一个equality-constrainted quadratic programming,EQP。 我们可以直接利用KKT System进行求解。

KKT System 是利用KKT条件进行建模求解, 然后构建一个KKT矩阵matrix的系统。

KKT Matrix 是巧妙的构建的一个对称矩阵(Symmetric)矩阵。

这里要注意的时候, 这里Z是A矩阵的零空间null space的基。 更多关于Null Space的细节,请参考“矩有四子”。

根据KKT条件, 我们知道, A是満秩 (full rank)矩阵, 并且Z'QZ是正定(positive definite), 那么是一个凸系统(更多细节参考 “一挑三 FJ vs KKT ”), 那么可以知道存在唯一全局最优解(global optimum)。

如果Q是对称symmetric的!

如果Q是正定,而且很容易求逆!

如果A容易实现LU分解LU factorization!

我们把x分解到Col(A)和Nul(A), (更多关于Null Space的细节,请参考“矩有四子”)。这样我们得到:

由于我们知道b是固定的, 那么这种分解之后, x0就是固定的了。

这样, 我们就可以求解到最佳的w*。

这样我们解释了直接利用EQP问题的KKT System进行求解, 并且分析了Range-space method和Null-space method的适用情况。

Active set strategies

Active set的基本思想和Simplex方法(Simplex方法参考 “一步一步走向锥规划 - LP”)的基本思想大体一致,就是要先找到一个可行解 feasible solution, fs, 然后沿着边或者面继续找可行解。 但是对应到QP和LP还是有很不一样的,就是LP的最优解肯定是在角(extreme points)上, 但是QP不是,并且如果QP对应的不是凸问题(non-convex),那么Active set可能只能找到一个局部最优(local optimum)。

前面我大体对比了Active Set和Simplex的基本思想, 下面我们详细说一下Active Set的思路。 为了, 囊括前面的4种情况, Active Set算法, 首先从feasible region, FR里面选择一个点, 然后沿着梯度方向(如果有最值definite,就是最值方向, 如果没有最值indefinite,就是梯度方向), 直到feasible region, FR 的边界, 如果最值点在FR里面inner, 那么就找到最值。但是如果不在, 那么就找到一个边界点。 那么沿着前面的限制和梯度夹角小的方向继续前进。 这时候可能又遇到另外一个限制, 这时候就找到一个顶点, 然后继续沿着新遇到的限制和梯度夹角小的方向前行。 直到在某个点,限制方向和梯度方向垂直了。

什么叫 active set 和 inactive set ?

这个问题相对比较简单,就是如果在一个点x所在的feasible region的所有边界就叫这些边界在x这个点被active, 而其他边界就是 inactive。

给定一个可行点, 如何找到这点和最优点的方向(点0')?

如下图所示,随机给定一个可行点 feasible point, 但是如果这个点是一个内部点inner, 那么这个点对应的active set就是空集。既然是空集, 那么就是一个unconstrained/equality constrained quadratic problem, 所以对应的最优点(optimum)就是0'点。

给定一个可行点, 如何找到这点和最优点方向上的限制点(点1)?

这时候, 我们利用截距之间的比例,计算到占比uk, 然后根据uk计算出dk于边界的交点的位置。 有三点要注意:

1, 选择最大的uk是为了保证最接近无限制极值点0'。 越接近越优

2, 如果uk>1意味着无限制极值点就在可行区域(feasible region)里面, 那么直接用这个点。

3, 限制ai dk > 0为了保证求到的方向上是向着区域外面的,这样才有交点。

如果找到一个交点(点1), 如何找到下一个交点(点2)?

换到术语来说, 就是已经 有一个working set了,如何换到另外一个working set。

在找到一个交点(点1)之后我们就找到了一个限制, 然在这个限制下我们求解 equality-constrainted QP, EQP 就找一个新的最优点1', 再通过截距比例就得到了两个限制的交点了(点2)这时候,就会更新2对应的working set, 然后就可以同理求解到点3了。

算法什么时候停止呢?

其实很简单, 当我们发现对应的最优点x*和working set都无法再更新了, 那么算法就停止了。 譬如上图对应的最优点3, 对应的限制直线,已经在我们的working set里面了, 那么就无法再更新了, 意味着我们已经求解到了最优解了。

这样我们把Active Set的算法小结一下如下:

再举个例子!

随意一个点(2,0)x0 出发确定了直线A限制, 然后找到A和B的交点(x1)加入直线B限制, 然后找到最优点(x2),不是交点,更新到B, 然后再找, 发现和D的交点(x4), 然后再找到x5,然后发现点和working set都不再更新了。

另外可以看到本质上, active set算法和simplex算法思想一致, 所以active set算法不是多项式polynomial时间算法。 另外, 对于非凸情况, 由于梯度方向不太一致, 算法会变得很复杂。

Interior-point methods

一般来说Path-following methods ,或者 trajectory-following, 或者 barrier 都是 interior-point methods 的别称或者一种。

前面我们讲了active set本质思想是和simplex思想一致的, 但是这样的算法复杂度依赖于限制条件组成的边或者角数量,所以都不是多项式复杂度的。 在线性问题中,我们提到了Karmarkar算法的基本思想(参考 “一步一步走向锥规划 - LP”), 通过仿射投影(affine projection)的方法,通过内部(interior)向最优点靠近。 在QP里面, 主要利用了central path 和 barrier的两种思想。

什么是central path?

在我们利用标准形式(Standard) [ Ax = b, x >= 0 ] 进行KKT条件求解之后, 我们发现, primal feasible, dual feasible一起满足形式F(x, y, z) = 0, 所以一个KKT条件解要满足F=0。 为了一步步达到这个目标,我们让F = [0, 0, t I ]^T。 然后让 t -> 0 逐步逼近, 而这个逼近的途径叫做central path。

而要求解一个函数与自变量轴的交点(F(x,y,z)=0),牛顿法是一个很好的办法。 因此接下来,经常用牛顿法进行优化处理。

至此, 我们似乎完美的搞定了这个问题了, 其实没有, 如何找到第一个满足要求的点呢?v( t0 ) 必须可以取到,从而使得 t0 > 0。还记得在讲述Simplex算法的时候, 也有类似的经历, 如何找到第一个可行解(feasible solution), 那时候我们讲述了Big-M的思想(参考 “一步一步走向锥规划 - LP”), 这个思想改造了目标公式进行求解到第一个可行解。 这里我们讲述另外一个思想, barrier思想, 也是类似, 对目标公式进行改造求解到第一个可行解。

什么barrier思想?

由于沿着边界会带来复杂度不可以控制, 那么如何避免接近边界呢?这里分了两步走:

  1. 引入slack variables把限制形式标准化, 把不等式放到第一象限。
  2. 定义barrier function 函数,使得接近边界时候变得过大。

其实Logarithmic Barrier Method最早是由 K.R. Frisch在他的书 Principles of linear programming中提出来的, 大概1954年就提出来了。 最后Barrier思想的完善是下面两位牛人完成的, Anthony Fiacco和 Garth McCormick。 他们都是美国最早研究nonlinear programming, NLP方面的早期奠基人。 但是这个方法在大型线性规划的时候,过于复杂,直到来自印度的Karmarkar 在1984年提出基于递归的仿射投影的了Karmarkar算法(参考 “一步一步走向锥规划 - LP”)。 从此极大促进了NLP的发展。

Logarithmic barrier functions是什么?

在barrier思想要求下, 很容易就扎到一个Logarithmic Barrier函数

直接通过图示来看是如何避开原点的和坐标轴的。

为什么要选择log函数呢?

其实log函数有一些很好的性质导致的:

  1. log函数是凸函数
  2. log函数可以模拟indicatorfunction 指示函数
  3. log函数的导数形式比较好。

大家会不会想起, 逻辑回归里面的sigmoid函数么。

对应的一阶和二阶导数的形式, 在Gradient decent,或者Newton method里面会用到。

有人就问了, 既然是为了模拟指示函数indicator function, 那么别的函数也可以的吧? 对的, 除了logarithmic barrier还有inverse barrier等。

如何做到interior的?

这样我们再来看, 如果feasible region, FE里面的点, 离边界越近的点, 在logarithmic barrier情况下, 越难以取到, 那么容易取到的就是中线的点了。 从而实现了interior!

具体的数学上, barrier是如何一步一步实现的呢?

通过利用log函数极好的 导数性质, 我们通过构建找到了一个关系式, 刚好满足central path的要求。 所以我们就可以通过logarithmic的关系来替代原来的形式。 这就是log barrier 强大的地方。 把一个有限制的形式, 通过

Central Path 其他情况?

除了利用Log Barrier method进行求解, 还有一些实用的方法可以改进central path的适用范围, 譬如引入scalar function进行缩放, 再引入centering parameter,引入bias。

另外,对于非凸情况的时候, Central Path的表现就要很奇怪了,要看起始点的位置了。

QP 对偶(duality)

什么是QP对偶?

QP对偶, 就是通过lagrange 对偶构造后得到的对偶问题, 前面在线性规划LP里面, 我们直接给出线性规划的对偶(参考 “一步一步走向锥规划 - LP”), 但是在QP中,已经没有了形式上的完美的对称关系,需要从对偶的本质进行构造了。

怎么得到对偶? 什么是 Lagrange duality construction?

对偶的构造, Lagrange提出了很好的一个构造过程, 这里就不详细讲述更多数学上的充要条件了(更多细节参考 “一挑三, FJ vs KKT”)。

如何理解 Lagrange duality construction ?

如同线性规划里面一致, 我们依然可以通过类似资源(原料)价格的关系理解, 通过购买的原料, 造出产品后, 产品的成本价格(cost price)在最大的情况下应该和原料价格最低一致(resource cost), 这样达到资源配置最优(optimum), 没有浪费。 下面给出了图形化的理解, 在线性规划里面有一个详细的线性规划的例子(参考 “一步一步走向锥规划 - LP”)可以作为类比。

这样, 我们来看最大化这个截距(与L线的交点)的高度是如何等价于求 Lagrange duality?

由此我么对比一下convex和strong duality的关系:

再进一步, 在对偶间隙duality gap的基础上我们再来看一下,在公式上, Interior-point method是如何发展而来的?

相比active set method, ASM, interior point method, IPM 还是有很多优势的, 对于中大型问题, 部分IPM可以保证polynominal时间复杂度。 这还是极大的优势!

QP的扩展概述

二次限制QP, QCQP

QCQP 是Robust QP的一种数学体现。 所谓Robust,就是我们对x分布的方差进行限制, 有一个上限。 更多细节就不展开了。

在引入了二次限制后, 就顺带引入 augmented Lagrangian 和 Penalty method 思想了。 这里就举个例子引入一下:

引入了Penalty思想和Augmented Lagrangian之后, 我们就能把二次限制转换成无限制的二次规划。 简单对比active set method, ASM和penalty method, PM,可以看到penalty方法还是有很大的局限性的, iterations次数多,而且,找的点不够精确。

小结, 这里我们总结了一下QP的作为 LSLP 扩展的含义, 以及QP里面拉格朗日和对偶是如何发挥作用的, 尤其是active set和interior point method是如何工作的。 下次, 我们会进一步理解 Second order cone programming (SOCP) 是如何进一步扩展QP的。再补充下下, QP是个爆发式发展和应用的部分, 不可能一个短文介绍到所有, 这里抛砖引玉的介绍下基本思想, 希望有讲清楚。 如果大家捧场, 以后希望继续多介绍点QP的其他方面, 譬如iteraltive 的KKT system求解, interior point方法的收敛性。

参考:

http://www.cs.cityu.edu.hk/~cheewtan/CS8292Class/Lec4.pdf

https://neos-guide.org/content/quadratic-programming-algorithms

https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf

http://www.math.uiuc.edu/documenta/vol-ismp/41_cottle-richard.pdf

https://www-user.tu-chemnitz.de/~helmberg/workshop04/vandenbussche.pdf

http://faculty.uml.edu/hung_phan/572optim/ntKKT.pdf

https://gilkalai.wordpress.com/2008/11/04/a-diameter-problem-6-abstract-objective-functions/

https://www.cs.umd.edu/users/oleary/a607/607constrbarhand.pdf

.

https://inst.eecs.berkeley.edu/~ee127a/book/login/exa_toy_opt_pb4.html

https://inst.eecs.berkeley.edu/~ee127a/book/login/exa_ols_minvar_port.html

http://www.alglib.net/optimization/quadraticprogramming.php

https://www.mathworks.com/discovery/nonlinear-programming.html

http://www2.imm.dtu.dk/courses/04231/OptCond.pdf

https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf

http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/Duality.pdf

https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec6_constr_opt.pdf

原文发布于微信公众号 - AI2ML人工智能to机器学习(mloptimization)

原文发表时间:2016-12-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

机器学习(五) ——k-近邻算法进一步探究

机器学习(五)——k-近邻算法进一步探究 (原创内容,转载请注明来源,谢谢) 一、概述 现采用k-近邻算法,进行分类应用。数据源采用《机器学习实战》提供的数...

3394
来自专栏人工智能头条

理解 LSTM 网络

1933
来自专栏数据派THU

教你用机器学习匹配导师 !(附代码)

作者:Zipporah Polinsky-Nagel, Gregory Brucchieri, Marissa Joy, William Kye, Nan Li...

1212
来自专栏智能算法

Yoshua Bengio等大神传授:26条深度学习经验

原文地址:http://www.marekrei.com/blog/26-things-i-learned-in-the-deep-learning-summe...

3776
来自专栏磐创AI技术团队的专栏

使用scikit-learn解决文本多分类问题(附python演练)

在我们的商业世界中,存在着许多需要对文本进行分类的情况。例如,新闻报道通常按主题进行组织; 内容或产品通常需要按类别打上标签; 根据用户在线上谈论产品或品牌时的...

2973
来自专栏机器学习算法工程师

机器学习论文笔记—如何利用高效的搜索算法来搜索网络的拓扑结构

分层表示高效的架构搜索(HIERARCHICAL REPRESENTATIONS FOR EFFICIENT ARCHITECTURE SEARCH)这篇文章讲...

1762
来自专栏机器学习原理

我的机器学习微积分篇观点函数从极限到导数导数的应用偏导数从方向导数到梯度

前言: 没想到还能在此生再次用到大学习学习的高数,线性代数和概率论,如果上天给我再来一次的机会,我一定往死了学习这三门课。 观点 与机器学习相关的微积分...

4535
来自专栏人工智能

长时间序贯任务结构的演示学习方法及其在手术机器人中的应用

本文总结了最近三篇论文的结果,这些论文提出了一些可以将更长的任务分解成更短子任务的学习算法。

35810
来自专栏织云平台团队的专栏

【干货分享】AIOps之根因分析

本文将给出基于决策树的智能根因分析方法,针对多维找出导致问题的根因。做数据、搞AI一定要基于具体业务,不可脱离业务谈数据、算法,否则将得不偿失。

2.1K10
来自专栏量子位

以为GAN只能“炮制假图”?它还有这7种另类用途

最近,AI方案设计师Alexandor Honchar在Medium网站上分享一篇文章。他认为生成对抗网络(GAN)目前在生成图像取得了巨大进展,生成的图像几乎...

1282

扫码关注云+社区

领取腾讯云代金券