# 《Python进阶系列》二十三：解决线性规划和二次型规划问题的CVXOPT模块

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]


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 ​

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模块

(0)

### 大家都在看

• #### Android自定义View之点赞撒花（三阶贝塞尔曲线应用）

前言 本文参考辉哥的贝塞尔曲线 – 花束直播点赞效果，是对 &#x4E09;&#x9636;&#x8D1D;&#x585E;&#…

人工智能 2022年11月26日
065
• #### 初步认识系统调用

目录 * – 前言 – 一、什么是进程？ – + * 1、进程与程序的区别？ * 2、什么是进程的控制块 – 二、什么是系统调用？ …

人工智能 2022年11月25日
056
• #### sklearn实战之聚类算法

sklearn实战系列：(1) sklearn实战之决策树(2) sklearn实战之随机森林(3) sklearn实战之数据预处理与特征工程(4) sklearn实战之降维算法P…

人工智能 2022年11月9日
085
• #### python中stack函数_python pandas stack和unstack函数

在用pandas进行数据重排时，经常用到stack和unstack两个函数。stack的意思是堆叠，堆积，unstack即”不要堆叠”，我对两个函数是这样理…

人工智能 2022年12月4日
054
• #### 最新版GNS3安装详解，小白也可以独立完成哦！！

一、准备工作 请各位提前安装好CRT和Wireshark软件以及GNS3所要使用到的镜像文件，GNS3支持虚拟机模式，所以在安装GNS3前，请确保你的电脑上安装了虚拟机软件VMwa…

人工智能 2022年11月26日
073
• #### 聚类系列算法进阶（一）18

聚类算法 1、聚类介绍 1.1、聚类作用 知识发现 发现事物之间的潜在关系 异常值检测 特征提取 数据压缩的例子 1.2、有监督与无监督学习 有监督： 给定训练集 X 和 标签Y …

人工智能 2022年9月29日
0114
• #### velo2cam_calibration——最新最准确的激光雷达Lidar和相机Camera外参标定算法实现

因为实验需求，要实现相机和雷达之间的融合，因此需要完成相机内参标定和雷达与相机外参标定。 [En] Because of the experimental requirements…

人工智能 2022年9月18日
0124
• #### 自动驾驶笔记-轨迹跟踪之①纯跟踪算法（Pure Pursuit）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言 一、阿克曼转向模型 * 1.1 模型理解 1.2 模型表达 二、纯跟踪算法（Pure Pursui…

人工智能 2022年10月3日
0262
• #### Tensorflow 2.x(keras)源码详解之第五章：数据预处理

抵扣说明： 1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。 Original: https:…

人工智能 2022年9月5日
0105
• #### 对于神经网络参数初始化的一些理解

参数初始化 * – 动机 – 1. 预训练初始化 – 2. 随机初始化 – + 2.1 高斯（Gaussian）分布初始化 + 2….

人工智能 2022年12月8日
029
• #### 卡方检验有哪些指标？卡方值怎么计算？

一、研究场景 卡方检验是一种假设检验的方法，它属于非参数检验的范畴，主要是用于分析定类数据与定类数据之间的关系情况。例如：分析性别与患病之间是否存在差异、性别与是吸烟之间是否存在差…

人工智能 2022年12月9日
097
• #### Keras深度学习实战——车辆转弯角度预测

Keras深度学习实战——车辆转弯角度预测 * – 0. 前言 – 1. 数据集与模型分析 – + 1.1 模型分析 + 1.2 数据集分析 &…

人工智能 2022年9月18日
0129
• #### 如何在感知机中使用多任务学习算法

你好，这篇文章咱们讨论一下关于「如何在感知机中使用多任务学习算法」的事情… 如何在感知机中使用多任务学习算法 随着深度学习技术的发展，多任务学习成为了一种非常重要的机器…

人工智能 2023年3月14日
09
• #### 【超分辨率】【深度学习】SRCNN pytorch代码（附详细注释和数据集）

主要改进： 断点恢复，可以恢复训练。 注释掉原test.py的38行才是真正的超分辨率。 即image = image.resize((image.width // args.sc…

人工智能 2022年12月13日
046
• #### 机器学习之分类回归树

一. 随机森林RF RF是分类树，是由很多决策树构成的，不同决策树之间没有关联 二. GBDT GBDT是回归树，当前的树的输入为上一棵树的残差结果 入门例子的话，可以看这个视频讲…

人工智能 2022年11月19日
062
• #### Faster-RCNN详解（个人理解）

1. Faster-RCNN的四个主要内容 图1 Faster-RCNN基本结构 如上图所示，整个Faster-RCNN模型可以分为四个模块： 1） Conv layers ，特征…

人工智能 2022年11月24日
045