通过 python 求解 QP 问题

From 李航《统计学习方法》Ver.2 例7.1

1：二次规划问题的标准形式

2：问题描述

3：按照线性可分支持向量机算法分析问题

3.1：SMO算法

3.2：根据三个实例构造约束最优化问题

$$\begin{gathered} \underset{w,b}{\min }1/2(w_1^2+w_2^2) \\ s.t.3w_1+3w_2+b\ge 1 \\ 4w_1+3w_2+b\ge 1 \\ -1w_1-1w_2-b\ge 1 \end{gathered}$$

3.:3：写成矩阵乘法的形式有

$$\underset{w,b}{\min }\frac{1}{2}{\left(\begin{array}{c}{w}_1\\ w_2\\ b\end{array}\right)}^T\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}\right)\left(\begin{array}{c}{w}_1\\ w_2\\ b\end{array}\right)$$
$$s.t.\left(\begin{array}{ccc}-3& -3& -1\\ -4& -3& -1\\ 1& 1& 1\end{array}\right)\left(\begin{array}{c}{w}_1\\ w_2\\ b\end{array}\right)\le \left(\begin{array}{c}-1\\ -1\\ -1\end{array}\right)$$

4：代码分析

'''
    Objects  :  对SVM支持向量机基本型的算法，用现成的优化计算包求解二次规则(Convex Quadratic Programming)问题 
                举例，将形式转换为二次规划的标准形式
                调用优化函数：solvers.qp(P,q,G,h,A,b)  
    Version  :  V1.0
    Name     :  7.1.py
    Author   :  Haoger
    Date     :  2020/12/12
    Location :  Long Room
'''
from cvxopt import solvers, matrix

# matrix里区分int和double，所以数字后面都需要加小数点
# 注意录入数据时，以列向量的形式录入
P = matrix([[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 0.0]])
q = matrix([0.0, 0.0, 0.0])
G = matrix([[-3.0, -4.0, 1.0], [-3.0, -3.0, 1.0], [-1.0, -1.0, 1.0]])
h = matrix([-1.0, -1.0, -1.0])
sol = solvers.qp(P,q,G,h)

print(sol['x'])

5：结果分析

     pcost       dcost       gap    pres   dres
 0:  1.4507e-01  7.1106e-01  4e+00  1e+00  8e+00
 1:  5.9278e-01  1.4232e-01  5e-01  3e-16  2e-15
 2:  2.7513e-01  2.3773e-01  4e-02  0e+00  4e-16
 3:  2.5037e-01  2.4959e-01  8e-04  4e-16  4e-16
 4:  2.5000e-01  2.5000e-01  8e-06  4e-16  4e-16
 5:  2.5000e-01  2.5000e-01  8e-08  0e+00  2e-15
Optimal solution found.
[ 5.00e-01]
[ 5.00e-01]
[-2.00e+00]

即所求方程为：$1/2x_1+1/2x_2-2=0$

本文地址：https://blog.csdn.net/whaoger/article/details/111084045