使用python求解二次规划的问题

Python中支持Convex Optimization（凸规划）的模块为CVXOPT,其安装方式为：

pip install cvxopt

一、数学基础

二次型

二次型（quadratic form）：n个变量的二次多项式称为二次型，即在一个多项式中，未知数的个数为任意多个，但每一项的次数都为2的多项式。其基本形式如下

亦可写作， ，称作二次型的矩阵表示，其中A是对称矩阵。仿照如下的定义，我们可以直接在其基本形式和矩阵表示之间相互转化。

2.正定矩阵

设A是n阶实对称矩阵， 如果对任意一非零实向量X，都使二次型 成立，则称f(X)为正定二次型，矩阵A称为正定矩阵(Positive Definite)，A为正定矩阵。

相应的，如果对任意一非零实向量X，都使二次型成立，则称f(X)为半正定二次型，A为半正定矩阵。

3.二次规划问题

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

即在Gx<h 和Ax=b的约束下，最小化目标函数。其中，当P是正定矩阵时，目标函数存在全局唯一最优解；P是半正定矩阵时，目标函数是凸函数，存在全局最优解（不唯一）;P是不定矩阵时，目标函数非凸，存在多个局部最小值和稳定点，为np难问题。（本篇博客中我们不考虑非正定情况）。

二、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是一个字典，我们可直接获得其某个属性，e.g. 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求解二次规划的问题就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python二次规划和线性规划使用实例

    这篇文章主要介绍了Python二次规划和线性规划使用实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 对于二次规划(quadratic programming)和线性规划(Linear Programming)问题 MATLAB里是有quadprog函数可以直接用来解决二次规划问题的,linprog函数来解决线性规划问题.Python中也有很多库用来解决,对于二次规划有CVXOPT, CVXPY, Gurobi, MOSEK, qpOASES

  • 使用python求解二次规划的问题

    Python中支持Convex Optimization(凸规划)的模块为CVXOPT,其安装方式为: pip install cvxopt 一.数学基础 二次型 二次型(quadratic form):n个变量的二次多项式称为二次型,即在一个多项式中,未知数的个数为任意多个,但每一项的次数都为2的多项式.其基本形式如下 亦可写作, ,称作二次型的矩阵表示,其中A是对称矩阵.仿照如下的定义,我们可以直接在其基本形式和矩阵表示之间相互转化. 2.正定矩阵 设A是n阶实对称矩阵, 如果对任意一非零实

  • 利用python求解物理学中的双弹簧质能系统详解

    利用python求解物理学中的双弹簧质能系统详解

    前言 本文主要给大家介绍了关于利用python求解物理学中双弹簧质能系统的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定.假定没有外力时,两个弹簧的长度为L1和L2. 由于两物体有重力,那么在平面上形成摩擦力,那么摩擦系数分别为b1和b2.所以可以把微分方程写成这样: 这是一个二阶的微分方程,为了使用python来求解,需要把它转换为一阶微分方程

  • python求解水仙花数的方法

    本文实例讲述了python求解水仙花数的方法.分享给大家供大家参考.具体如下: 一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数. #!/usr/bin/python def get_flower(n, ofile): D_pow=[pow(i,n) for i in range(0,10)] V_min=1*pow(10,n-1) V_max=sum((9*pow(10,x) for x in range(0,n))) T_count=0 print D

  • Python求解平方根的方法

    本文实例讲述了Python求解平方根的方法.分享给大家供大家参考.具体如下: 主要通过SICP的内容改写而来.基于newton method求解平方根.代码如下: #!/usr/bin/python def sqrt_iter(guess,x): if(good_enough(guess, x)): print guess else: sqrt_iter(improve(guess, x),x) def improve(guess, x): return average(guess, x/gue

  • Python求解正态分布置信区间教程

    正态分布和置信区间 正态分布(Normal Distribution)又叫高斯分布,是一种非常重要的概率分布.其概率密度函数的数学表达如下: 置信区间是对该区间能包含未知参数的可置信的程度的描述. 使用SciPy求解置信区间 import numpy as np import matplotlib.pyplot as plt from scipy import stats N = 10000 x = np.random.normal(0, 1, N) # ddof取值为1是因为在统计学中样本的标

  • 使用Python求解带约束的最优化问题详解

    题目: 1. 利用拉格朗日乘子法 #导入sympy包,用于求导,方程组求解等等 from sympy import * #设置变量 x1 = symbols("x1") x2 = symbols("x2") alpha = symbols("alpha") beta = symbols("beta") #构造拉格朗日等式 L = 10 - x1*x1 - x2*x2 + alpha * (x1*x1 - x2) + beta

  • Python求解排列中的逆序数个数实例

    在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序. 一个排列中逆序的总数就称为这个排列的逆序数. 一个排列中所有逆序总数叫做这个排列的逆序数. 也就是说,对于n个不同的元素,先规定各元素之间有一个标准次序(例如n个 不同的自然数,可规定从小到大为标准次序),于是在这n个元素的任一排列中,当某两个元素的先后次序与标准次序不同时,就说有1个逆序. 一个排列中所有逆序总数叫做这个排列的逆序数. Python代码: def inverse_number(s

  • python求解汉诺塔游戏

    本文实例为大家分享了python求解汉诺塔游戏的具体代码,供大家参考,具体内容如下 一.问题定义 百度百科定义:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.据说大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照从小到大顺序摞着64片黄金圆盘.大梵天命令婆罗门借助其中一根柱子,把64片黄金圆盘重新摆放到第三个根柱子上.并且规定,在小黄金圆盘上不能放大的黄金圆盘,在三根柱子之间一次只能移动一个圆盘. 例如,如果黄金圆盘只有3片,则为了满足游戏规则,那么必须按照如下图所示的

  • 使用python求解迷宫问题的三种实现方法

    使用python求解迷宫问题的三种实现方法

    目录 前言 递归求解 回溯求解 队列求解 总结 前言 在迷宫问题中,给定入口和出口,要求找到路径.本文将讨论三种求解方法,递归求解.回溯求解和队列求解. 在介绍具体算法之前,先考虑将迷宫数字化.这里将迷宫用一个二维的list存储(即list嵌套在list里),将不可到达的位置用1表示,可到达的位置用0表示,并将已经到过的位置用2表示. 递归求解 递归求解的基本思路是: 每个时刻总有一个当前位置,开始时这个位置是迷宫人口. 如果当前位置就是出口,问题已解决. 否则,如果从当前位置己无路可走,当前的

  • 使用Python求解最大公约数的实现方法

    1. 欧几里德算法 欧几里德算法又称辗转相除法, 用于计算两个整数a, b的最大公约数.其计算原理依赖于下面的定理: 定理: gcd(a, b) = gcd(b, a mod b) 证明:   a可以表示成a = kb + r, 则r = a mod b   假设d是a, b的一个公约数, 则有  d|a, d|b, 而r = a - kb, 因此d|r.   因此,d是(b, a mod b)的公约数.   加上d是(b,a mod b)的公约数,则d|b, d|r, 但是a = kb + r

随机推荐