Python使用CVXOPT求解二次规划详解

CVXOPT安装与环境配置

在Python生态中，处理凸优化（Convex Optimization）任务的常用模块是CVXOPT。安装该库的命令如下：

pip install cvxopt

二次规划数学基础

一、数学基础

二次型

二次型（quadratic form）是指包含n个变量的二次多项式，即多项式中未知数个数任意，但每一项的次数均为2。其基本代数形式如下所示。

该表达式亦可写作矩阵形式，，这被称为二次型的矩阵表示。其中A为对称矩阵。依据如下定义，可直接在基本形式与矩阵表示之间进行相互转换。

2.正定矩阵

若A是n阶实对称矩阵，且对任意非零实向量X，均满足二次型，则称f(X)为正定二次型，此时矩阵A称为正定矩阵（Positive Definite）。

相应地，若对任意非零实向量X，均满足二次型，则称f(X)为半正定二次型，矩阵A为半正定矩阵。

3.二次规划问题

二次规划是指带有二次型目标函数及约束条件的最优化问题。其标准数学形式如下：

即在满足Gx<h和Ax=b约束条件下，最小化目标函数。当矩阵P为正定矩阵时，目标函数存在全局唯一最优解；当P为半正定矩阵时，目标函数为凸函数，存在全局最优解（可能不唯一）；当P为不定矩阵时，目标函数非凸，存在多个局部最小值和稳定点，此类问题属于NP难问题（本文暂不考虑非正定情况）。

Python求解实现步骤

二、Python程序求解

使用的工具包为CVXOPT，即Python凸优化包。

核心函数原型为：Cvxopt.solvers.qp(P,q,G,h,A,b)

参数P,q,G,h,A,b的具体含义可参考上述二次规划问题的标准形式定义。

编程求解的主要思路如下：

1. 对于给定的二次规划问题，首先将其转换为标准形式（具体转换方法参见数学基础中关于二次型矩阵形式的说明）。

2. 对照标准形式，构建出对应的矩阵P, q, G, h, A, b。

3. 调用result=Cvxopt.solvers.qp(P,q,G,h,A,b)执行求解。

4. 通过print（result）查看结果，其中result是一个字典对象，可直接获取其特定属性，例如：print(result['x'])。

接下来通过一个具体实例进行演示。

import pprint
from cvxopt import matrix, solvers
P = matrix([[4.0,1.0],[1.0,2.0]])
q = matrix([1.0,1.0])
G = matrix([[-1.0,0.0],[0.0,-1.0]])
h = matrix([0.0,0.0])
A = matrix([1.0,1.0],(1,2))#原型为cvxopt.matrix(array,dims)，等价于A = matrix([[1.0],[1.0]]）
b = matrix([1.0])
result = solvers.qp(P,q,G,h,A,b)
 
print('x\n',result['x'])

运行结果如下：

注意事项：

cvxopt.matrix与numpy.matrix的数据排列顺序不同：cvxopt.matrix采用列优先存储，而numpy.matrix采用行优先存储。具体差异可见以下实例对比。

import numpy as np
from cvxopt import matrix
a = np.matrix([[1,2],[3,4]])
b = matrix([[1,2],[3,4]])
print('numpy.matrix',a)
print('cvxopt.matrix',b)

运行结果如下：

以上即为使用Python求解二次规划问题的完整介绍，希望能为读者提供参考与支持。