How to interpret the result of cvxopt.solvers.qp?

3.5k views Asked by At

There is no enough documentation and my math knowledge is limited.

The model

sol = solvers.qp(P=P, q=q,G=G,h=h, A=L, b=t)

    pcost       dcost       gap    pres   dres
0:  6.3316e+08  6.3316e+08  7e+00  3e+00  7e-10
1:  6.3316e+08  6.3316e+08  2e+00  1e+00  3e-10
2:  6.3316e+08  6.3316e+08  2e+00  1e+00  3e-10
3:  1.3393e+10 -3.5020e+09  2e+10  9e-01  2e-10
4:  7.6898e+08 -1.7925e+10  4e+10  8e-01  2e-10
5:  2.1728e+09 -3.8363e+09  6e+09  6e-16  2e-14
6:  2.1234e+09  2.0310e+09  9e+07  2e-16  3e-16
7:  2.0908e+09  2.0899e+09  1e+06  1e-18  2e-16
8:  2.0905e+09  2.0905e+09  1e+04  7e-21  9e-17
9:  2.0905e+09  2.0905e+09  1e+02  2e-16  3e-16
Optimal solution found.

The result

{'dual infeasibility': 2.538901219845834e-16,
 'dual objective': 2090476416.743256,
 'dual slack': 59.256743485146764,
 'gap': 95.35084344459145,
 'iterations': 9,
 'primal infeasibility': 2.220446049250331e-16,
 'primal objective': 2090476512.0941,
 'primal slack': 1.0136346108956689e-08,
 'relative gap': 4.561201584523881e-08,
 's': <2x1 matrix, tc='d'>,
 'status': 'optimal',
 'x': <2x1 matrix, tc='d'>,
 'y': <1x1 matrix, tc='d'>,
 'z': <2x1 matrix, tc='d'>}

How can I inteprert s,x,z which one is the result of my variable ?

If I print s and x, I always get something near to 1 and another near to 0, which seems to be infinitely incorrect.

>>> np.array(sol['x'])
>>> array([[  9.99999990e-01],[  1.01363461e-08]])
2

There are 2 answers

0
YU Chen  Shih On

#full explain here
https://blog.dominodatalab.com/fitting-support-vector-machines-quadratic-programming

#full example here
import numpy as np
import pandas as pd
import cvxopt
import matplotlib
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris

cvxopt.solvers.options['show_progress'] = True

if __name__ == '__main__':
    x_min     = 0
    x_max     = 5.5
    y_min     = 0
    y_max     = 2

    iris    = load_iris()
    iris_df = pd.DataFrame(data=np.c_[iris['data'], iris['target']], columns=iris['feature_names'] + ['target'])
    #Retain only 2 linearly separable classes
    iris_df = iris_df[iris_df["target"].isin([0,1])]
    iris_df["target"] = iris_df[["target"]].replace(0,-1)
    #Select only 2 attributes
    iris_df = iris_df[["petal length (cm)", "petal width (cm)", "target"]]
    print(iris_df.head())
    print()

    X = iris_df[["petal length (cm)", "petal width (cm)"]].to_numpy()
    y = iris_df[["target"]].to_numpy()
    n = X.shape[0]
    H = np.dot(y * X, (y * X).T)
    q = np.repeat([-1.0], n)[..., None]
    A = y.reshape(1, -1)
    b = 0.0
    G = np.negative(np.eye(n))
    h = np.zeros(n)

    P       = cvxopt.matrix(H)
    q       = cvxopt.matrix(q)
    G       = cvxopt.matrix(G)
    h       = cvxopt.matrix(h)
    A       = cvxopt.matrix(A)
    b       = cvxopt.matrix(b)
    solved  = cvxopt.solvers.qp(P, q, G, h, A, b)
    print()

    alphas  = np.array(solved["x"])
    w       = np.dot((y * alphas).T, X)[0]
    S       = (alphas > 1e-5).flatten()
    b       = np.mean(y[S] - np.dot(X[S], w.reshape(-1, 1)))
    print("W:", w)
    print("b:", b)

    xx      = np.linspace(x_min, x_max)
    a       = -w[0] / w[1]
    yy      = a * xx - (b) / w[1]
    margin  = 1 / np.sqrt(np.sum(w ** 2))
    yy_neg  = yy - np.sqrt(1 + a ** 2) * margin
    yy_pos  = yy + np.sqrt(1 + a ** 2) * margin
    plt.figure(figsize=(8, 8))
    plt.plot(xx, yy, "b-")
    plt.plot(xx, yy_neg, "m--")
    plt.plot(xx, yy_pos, "m--")
    colors = ["steelblue", "orange"]
    plt.scatter(X[:, 0],
                X[:, 1],
                c=y.ravel(),
                alpha=0.5,
                cmap=matplotlib.colors.ListedColormap(colors),
                edgecolors="black")
    plt.xlim(x_min, x_max)
    plt.ylim(y_min, y_max)
    plt.title('svm line')
    plt.show()
0
Wu Michael On

I think this short text from Stanford might be helpful for you. Highlighting the quoted section about the result:

Many properties about the solution can be extracted from the sol variable > (dictionary). In particular, the ‘status’, ‘x’, and ‘primal objective’ are probably the most >important. If status is optimal, then the latter two give the optimal solution and >its objective value. You can access these fields as you would with a regular Python dictionary:

Also, this documentation provides a in-depth explanation. For understanding the result, please go to page 69