Python中支持Convex Optimization（凸规划）的模块为CVXOPT，能够解决线性规划和二次型规划问题，其应用场景如SVM中的Hard Margin SVM。
Creating matrices
CVXOPT has separate dense and sparse matrix objects.
A dense matrix is created using the matrix() function; it can be created from a list (or iterator):
>>>from cvxopt import matrix
>>>A = matrix([1.0, 2.0, 3.0, 4.0, 5.0, 6.0], (2,3))
>>>print(A)
[ 1.00e+00 3.00e+00 5.00e+00]
[ 2.00e+00 4.00e+00 6.00e+00]
>>>A.size
(2, 3)
or from a list of lists, where each inner list represents a column of the matrix:
>>>B = matrix([ [1.0, 2.0], [3.0, 4.0] ])
>>>print(B)
[ 1.00e+00 3.00e+00]
[ 2.00e+00 4.00e+00]
More generally, the inner lists can represent block-columns.
>>>print(matrix([ [A] ,[B] ]))
[ 1.00e+00 3.00e+00 5.00e+00 1.00e+00 3.00e+00]
[ 2.00e+00 4.00e+00 6.00e+00 2.00e+00 4.00e+00]
The spmatrix() function creates a sparse matrix from a (value, row, column) triplet description.
>>>from cvxopt import sparse
>>>E = sparse([ [B, B], [D] ])
>>>print(E)
[ 1.00e+00 3.00e+00 1.00e+00 0 ]
[ 2.00e+00 4.00e+00 0 2.00e+00]
[ 1.00e+00 3.00e+00 0 0 ]
[ 2.00e+00 4.00e+00 0 0 ]
Sparse block-diagonal matrices can be constructed using the spdiag() function.
>>>from cvxopt import spdiag
>>>print(spdiag([B, -B, 1, 2]))
[ 1.00e+00 3.00e+00 0 0 0 0 ]
[ 2.00e+00 4.00e+00 0 0 0 0 ]
[ 0 0 -1.00e+00 -3.00e+00 0 0 ]
[ 0 0 -2.00e+00 -4.00e+00 0 0 ]
[ 0 0 0 0 1.00e+00 0 ]
[ 0 0 0 0 0 2.00e+00]
Solving a linear program
Linear programs can be specified via the solvers.lp() function. As an example, we can solve the problem
minimize 2 x 1 + x 2 subject to − x 1 + x 2 ≤ 1 x 1 + x 2 ≥ 2 x 2 ≥ 0 x 1 − 2 x 2 ≤ 4 \begin{array}{ll} \operatorname{minimize} & 2 x_{1}+x_{2} \ \text { subject to } & -x_{1}+x_{2} \leq 1 \ & x_{1}+x_{2} \geq 2 \ & x_{2} \geq 0 \ & x_{1}-2 x_{2} \leq 4 \end{array}minimize subject to 2 x 1 +x 2 −x 1 +x 2 ≤1 x 1 +x 2 ≥2 x 2 ≥0 x 1 −2 x 2 ≤4
>>>from cvxopt import matrix, solvers
>>>A = matrix([ [-1.0, -1.0, 0.0, 1.0], [1.0, -1.0, -1.0, -2.0] ])
>>>b = matrix([ 1.0, -2.0, 0.0, 4.0 ])
>>>c = matrix([ 2.0, 1.0 ])
>>>sol=solvers.lp(c,A,b)
pcost dcost gap pres dres k/t
0: 2.6471e+00 -7.0588e-01 2e+01 8e-01 2e+00 1e+00
1: 3.0726e+00 2.8437e+00 1e+00 1e-01 2e-01 3e-01
2: 2.4891e+00 2.4808e+00 1e-01 1e-02 2e-02 5e-02
3: 2.4999e+00 2.4998e+00 1e-03 1e-04 2e-04 5e-04
4: 2.5000e+00 2.5000e+00 1e-05 1e-06 2e-06 5e-06
5: 2.5000e+00 2.5000e+00 1e-07 1e-08 2e-08 5e-08
>>>print(sol['x'])
[ 5.00e-01]
[ 1.50e+00]
Solving a quadratic program
二次型规划问题
min x 1 2 x ⊤ P x + q ⊤ x subject to G x ⪯ h A x = b \begin{aligned} \min _{x} & \frac{1}{2} x^{\top} P x +q^{\top} x \ \text { subject to } & G x \preceq h \ & A x=b \end{aligned}x min subject to 2 1 x ⊤P x +q ⊤x G x ⪯h A x =b
其中P , q , G , h , A , b P,q,G,h,A,b P ,q ,G ,h ,A ,b为输入矩阵，该问题求解采用QP算法。
Quadratic programs can be solved via the solvers.qp() function. As an example, we can solve the QP
minimize 2 x 1 2 + x 2 2 + x 1 x 2 + x 1 + x 2 subject to x 1 ≥ 0 x 2 ≥ 0 x 1 + x 2 = 1 \begin{array}{ll} \operatorname{minimize} & 2 x_{1}^{2}+x_{2}^{2}+x_{1} x_{2}+x_{1}+x_{2} \ \text { subject to } & x_{1} \geq 0 \ & x_{2} \geq 0 \ & x_{1}+x_{2}=1 \end{array}minimize subject to 2 x 1 2 +x 2 2 +x 1 x 2 +x 1 +x 2 x 1 ≥0 x 2 ≥0 x 1 +x 2 =1
>>>from cvxopt import matrix, solvers
>>>Q = 2*matrix([ [2, .5], [.5, 1] ])
>>>p = 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))
>>>b = matrix(1.0)
>>>sol=solvers.qp(Q, p, G, h, A, b)
pcost dcost gap pres dres
0: 0.0000e+00 0.0000e+00 3e+00 1e+00 0e+00
1: 9.9743e-01 1.4372e+00 5e-01 4e-01 3e-16
2: 1.8062e+00 1.8319e+00 5e-02 4e-02 5e-16
3: 1.8704e+00 1.8693e+00 6e-03 2e-03 1e-15
4: 1.8749e+00 1.8748e+00 2e-04 6e-05 6e-16
5: 1.8750e+00 1.8750e+00 2e-06 6e-07 7e-16
6: 1.8750e+00 1.8750e+00 2e-08 6e-09 1e-15
>>>print(sol['x'])
[ 2.50e-01]
[ 7.50e-01]
Original: https://blog.csdn.net/qq_37085158/article/details/122535368
Author: 奋斗的西瓜瓜
Title: 《Python进阶系列》二十三：解决线性规划和二次型规划问题的CVXOPT模块
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/170587/
转载文章受原作者版权保护。转载请注明原作者出处！
