登录
首页精彩阅读[译]在R中使用quadprog包求解二次规划
[译]在R中使用quadprog包求解二次规划
2016-03-01
收藏

概述

本文将探究一个被称为二次规划的优化问题,这是一种特殊形式的非线性约束优化问题。二次规划在许多领域都有运用,比如投资组合优化、求解支持向量机(SVM)分类问题等。在R中求解二次规划有许多包,这次,我们将讨论一下quadprog包。在我们开始讲解案例之前,我们将先简短地介绍一下二次规划的机理。

什么是二次规划

对于一个二次规划问题,首先要考虑的就是一个二次目标函数:

Q(x)=12xTDx−dTx+c.

这里 x  ℝn 中是一个向量, D 是一个n×的对称正定矩阵,在 ℝn 中 d 是常数项约束,是一个标量常数。Q(x)函数通常以二次函数的形式出现,并且它高维的通项表达式是:

q(x)=ax2+bx+c

Q(x)的关键特性在于这是一个凸函数。

我们也对向量x构造一个线性约束集合,即∈ℝn。
我们把这些约束写成:

Ax=fBx≥g

这里,是一个 m1×的矩阵且约束为 m1nBB 是一个 m2×的矩阵.向量 f 和向量 g的长度分别是m1m2.

这是一种让我们可以充分考虑实际条件的标准型。比如我们让 x 强制满足

i=1nxi=1

的求和条件,或者满足aixibi的区间约束。接下来,我们将介绍如何将这些约束转化为矩阵表达。

用这个符号系统,我们可以简洁表示二次规划 (QP):

{minimizex∈ℝn:Q(x)=12xTDx−dTx+csubjectto:Ax=fBxg

示例

目标函数

考虑目标函数:

Q(x,y)==12[xy][2−112][xy][32][xy]+4x2+y2xy+3x2y+4.

约束条件

我们这个约束条件下的可行域内寻求最小化:

yyy≥≥≤2x2+x3.

我们可以找到这个可行域的顶点并在R画出整个可行域:

plot(0, 0, xlim = c(-2,5.5), ylim = c(-1,3.5), type = "n",       xlab = "x", ylab = "y", main="Feasible Region") polygon(c(2,5,-1), c(0,3,3), border=TRUE, lwd=4, col="blue")

 SHAPE  \* MERGEFORMAT

化为标准型

想要用quadprog包求解二次规划,我们需要同时转化我们的目标函数和约束条件为矩阵形式。这里是官方文档的说明:

This routine implements the dual method of Goldfarb and Idnani (19821983for solving quadratic programming problems of the form min(-d^T b + 1/2 b^T D b) with the constraints A^T b >= b_0.

可惜官方文档多可读性不高,我们很难得知如何准确地转化二次型Q(x,y)为一个矩阵形式。首先,我们观察到,对于任意常数 c, 都存在MinQ(x,y)+c  Q(x,y)的解相等。因此,我们可以忽略二次规划中的常数项:

D=[2−112]d=[32].

我们可以写出约束方程的矩阵形式:

⎡⎣⎢⎢1−10111⎤⎦⎥⎥[xy]≥⎡⎣⎢⎢2−23⎤⎦⎥⎥

因此:

A=⎡⎣⎢⎢1−10111⎤⎦⎥⎥Tb0=⎡⎣⎢⎢2−23⎤⎦⎥⎥



具体实现

quadprog包默认是求解最小化问题,目标函数二次,约束一次。所以,我们的约束条件默认的形式也就是AX>=bvec。通常我们需要把一些原来是求极大值的问题或者<=约束通过乘以负号来转化。

这是R的完整实现:



·       参数Dmat表示海赛矩阵

·       参数dvet表示一阶向量,和Dmat的维数要相对应。

·       参数Amat表示约束矩阵,默认的约束都是是>=。

·       参数bvet表示右边值,由向量,和Amat的维数要相对应。

·       参数 meq 表示从哪一行开始Amat矩阵中的约束是需要被当作等式约束的。


结论

让我们检查一下 quadprog 求解器求解的结果吧:


(1/6,11/6) 点是唯一满足约束条件和 Q(x,y)的最小化目标,但 (−4/3,1/3)点才是 Q(x,y) 的最小值点。iterations,Lagrangian 和 iact 都是用来描述quadprog算法性能的。对于这些值之后我们将进一步讨论。现在,让我们先可视化二次规划的解。为此,我们在Q(x,y)的可行域边界添加一个外侧的等高线图。

在图中,深绿色区域表示Q(x,y) 表面目标函数值较小的解,而亮色表示目标函数值较大的解。红点是Q(x,y)的全局最小值点,而黄点表示二次规划的解。


英文原文


数据分析咨询请扫描二维码

客服在线
立即咨询