Python中支持Convex Optimization（凸規(guī)劃）的模塊為CVXOPT,其安裝方式為：

pip install cvxopt

一、數(shù)學(xué)基礎(chǔ)

二次型

二次型（quadratic form）：n個(gè)變量的二次多項(xiàng)式稱為二次型，即在一個(gè)多項(xiàng)式中，未知數(shù)的個(gè)數(shù)為任意多個(gè)，但每一項(xiàng)的次數(shù)都為2的多項(xiàng)式。其基本形式如下

亦可寫作， ，稱作二次型的矩陣表示，其中A是對(duì)稱矩陣。仿照如下的定義，我們可以直接在其基本形式和矩陣表示之間相互轉(zhuǎn)化。

2.正定矩陣

設(shè)A是n階實(shí)對(duì)稱矩陣， 如果對(duì)任意一非零實(shí)向量X，都使二次型 成立，則稱f(X)為正定二次型，矩陣A稱為正定矩陣(Positive Definite)，A為正定矩陣。

相應(yīng)的，如果對(duì)任意一非零實(shí)向量X，都使二次型成立，則稱f(X)為半正定二次型，A為半正定矩陣。

3.二次規(guī)劃問題

二次規(guī)劃是指，帶有二次型目標(biāo)函數(shù)和約束條件的最優(yōu)化問題。其標(biāo)準(zhǔn)形式如下：

即在Gx<h 和Ax=b的約束下，最小化目標(biāo)函數(shù)。其中，當(dāng)P是正定矩陣時(shí)，目標(biāo)函數(shù)存在全局唯一最優(yōu)解；P是半正定矩陣時(shí)，目標(biāo)函數(shù)是凸函數(shù)，存在全局最優(yōu)解（不唯一）;P是不定矩陣時(shí)，目標(biāo)函數(shù)非凸，存在多個(gè)局部最小值和穩(wěn)定點(diǎn)，為np難問題。（本篇博客中我們不考慮非正定情況）。

二、python程序求解

工具包：Cvxopt python 凸優(yōu)化包

函數(shù)原型：Cvxopt.solvers.qp(P,q,G,h,A,b)

P,q,G,h,A,b的含義參見上面的二次規(guī)劃問題標(biāo)準(zhǔn)形式。

編程求解思路：

1.對(duì)于一個(gè)給定的二次規(guī)劃問題，先轉(zhuǎn)換為標(biāo)準(zhǔn)形式（參見數(shù)學(xué)基礎(chǔ)中所講的二次型二中形式轉(zhuǎn)換）

2.對(duì)照標(biāo)準(zhǔn)形勢(shì)，構(gòu)建出矩陣P,q,G,h,A,b

3.調(diào)用result=Cvxopt.solvers.qp(P,q,G,h,A,b)求解

4.print（result）查看結(jié)果，其中result是一個(gè)字典，我們可直接獲得其某個(gè)屬性，e.g. print(result['x'])

下面我們來看一個(gè)例子

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)，等價(jià)于A = matrix([[1.0],[1.0]]）
b = matrix([1.0])
result = solvers.qp(P,q,G,h,A,b)
 
print('x\n',result['x'])

運(yùn)行結(jié)果：

注意事項(xiàng)：

cvxopt.matrix與numpy.matrix的排列順序不同，其中cvxopt.matrix是列優(yōu)先，numpy.matrix是行優(yōu)先。具體可見下面實(shí)例

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)

運(yùn)行結(jié)果：

以上這篇使用python求解二次規(guī)劃的問題就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論