Programación lineal y cuadrática con CVXOPT

CVXOPT es una librería en Python para optimización convexa que hace interface a librerías ya establecidas (como LAPACK, FFTW, GLPK, MOSEK, etc) para resolver los problemas de manera eficiente.



In [1]:

    
from cvxopt import matrix, solvers

Problema de Programación Lineal

Consideramos el siguiente problema:



In [2]:

    
%%latex
    $$
    \begin{array}{rr}
      \text{minimizar} & 2x_1 + x_2 \quad
      \\ \text{sujeto a} & -x_1 + x_2 \le 1
      \\   & x_1 + x_2 \ge 2
      \\   & x_2 \ge 0
      \\   & x_1 - 2 x_2 \le 4
    \end{array}
    $$









    





    $$
    \begin{array}{rr}
      \text{minimizar} & 2x_1 + x_2 \quad
      \\ \text{sujeto a} & -x_1 + x_2 \le 1
      \\   & x_1 + x_2 \ge 2
      \\   & x_2 \ge 0
      \\   & x_1 - 2 x_2 \le 4
    \end{array}
    $$

De acuerdo a la documentación de cvxopt.solvers.lp, tenemos que expresar el problema como:



In [3]:

    
%%latex
    $$
    \begin{array}{rr}
      \text{minimizar} & c^t x \qquad
      \\ \text{sujeto a} & G x + s = h
      \\   & A x = b
      \\   & s \succeq 0
    \end{array}
    $$









    





    $$
    \begin{array}{rr}
      \text{minimizar} & c^t x \qquad
      \\ \text{sujeto a} & G x + s = h
      \\   & A x = b
      \\   & s \succeq 0
    \end{array}
    $$

Entonces:



In [4]:

    
%%latex
    $$
    \begin{array}{rr}
      \text{minimizar} & \begin{pmatrix}2 & 1 \end{pmatrix} \begin{pmatrix}x_1 \\ x_2\end{pmatrix} \qquad\qquad\qquad
      \\ \text{sujeto a} & \begin{pmatrix} -1 & 2 \\ -1 & -2 \\ 0 & -1 \\ 1 & -2\end{pmatrix}
        \begin{pmatrix}x_1 \\ x_2\end{pmatrix} + \begin{pmatrix}s_1 \\ s_2\end{pmatrix}
        = \begin{pmatrix}1 \\ -2 \\ 0 \\ 4 \end{pmatrix}
      \\   & \text{ con } s_1,s_2 \gt 0
    \end{array}
    $$









    





    $$
    \begin{array}{rr}
      \text{minimizar} & \begin{pmatrix}2 & 1 \end{pmatrix} \begin{pmatrix}x_1 \\ x_2\end{pmatrix} \qquad\qquad\qquad
      \\ \text{sujeto a} & \begin{pmatrix} -1 & 2 \\ -1 & -2 \\ 0 & -1 \\ 1 & -2\end{pmatrix}
        \begin{pmatrix}x_1 \\ x_2\end{pmatrix} + \begin{pmatrix}s_1 \\ s_2\end{pmatrix}
        = \begin{pmatrix}1 \\ -2 \\ 0 \\ 4 \end{pmatrix}
      \\   & \text{ con } s_1,s_2 \gt 0
    \end{array}
    $$

Por lo tanto los argumentos estan dado de la siguiente manera:



In [5]:

    
# Notese que el objeto matrix() se declara por-columna en lugar del usual por-fila.
A = matrix([[-1., -1., 0., 1.], [1., -1., -1., -2.]])
b = matrix([1., -2., 0., 4.])
c = matrix([2., 1.])

print A
print b
print c









    



[-1.00e+00  1.00e+00]
[-1.00e+00 -1.00e+00]
[ 0.00e+00 -1.00e+00]
[ 1.00e+00 -2.00e+00]

[ 1.00e+00]
[-2.00e+00]
[ 0.00e+00]
[ 4.00e+00]

[ 2.00e+00]
[ 1.00e+00]

Finalmente encontramos la solución:



In [6]:

    
sol = solvers.lp(c, A, b)
print sol['x']









    



     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
Optimal solution found.
[ 5.00e-01]
[ 1.50e+00]

Problema de Programación Cuadrática

Consideremos el siguiente problema:



In [7]:

    
%%latex
    $$
    \begin{array}{rr}
      \text{minimizar} & 2x_1^2 + x_2^2 + x_1 x_2 + x_1 + x_2
      \\ \text{sujeto a} & -x_1 \ge 0 \qquad
      \\   & x_2 \ge 0 \qquad
      \\   & x_1 + x_2 = 1 \qquad
    \end{array}
    $$









    





    $$
    \begin{array}{rr}
      \text{minimizar} & 2x_1^2 + x_2^2 + x_1 x_2 + x_1 + x_2
      \\ \text{sujeto a} & -x_1 \ge 0 \qquad
      \\   & x_2 \ge 0 \qquad
      \\   & x_1 + x_2 = 1 \qquad
    \end{array}
    $$

De acuerdo a la documentación de cvxopt.solvers.qp, tenemos que expresar el problema como:



In [8]:

    
%%latex
    $$
    \begin{array}{rr}
      \text{minimizar} & \frac{1}{2} x^t P x + q^t
      \\ \text{sujeto a} & G x \preceq h
      \\   & A x = b
    \end{array}
    $$









    





    $$
    \begin{array}{rr}
      \text{minimizar} & \frac{1}{2} x^t P x + q^t
      \\ \text{sujeto a} & G x \preceq h
      \\   & A x = b
    \end{array}
    $$

Entonces:



In [9]:

    
%%latex
    $$
    \begin{array}{rr}
      \text{minimizar} & \frac{1}{2} \begin{pmatrix}x_1 & x_2 \end{pmatrix}
        \begin{pmatrix} 4 & 1 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}
        + \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}
      \\ \text{sujeto a} & \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}
        \begin{pmatrix}x_1 \\ x_2\end{pmatrix} \preceq \begin{pmatrix} 0 \\ 0 \end{pmatrix} \qquad\qquad
      \\   & \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}
        = \begin{pmatrix} 1 \end{pmatrix} \qquad\qquad
    \end{array}
    $$









    





    $$
    \begin{array}{rr}
      \text{minimizar} & \frac{1}{2} \begin{pmatrix}x_1 & x_2 \end{pmatrix}
        \begin{pmatrix} 4 & 1 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}
        + \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}
      \\ \text{sujeto a} & \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}
        \begin{pmatrix}x_1 \\ x_2\end{pmatrix} \preceq \begin{pmatrix} 0 \\ 0 \end{pmatrix} \qquad\qquad
      \\   & \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}
        = \begin{pmatrix} 1 \end{pmatrix} \qquad\qquad
    \end{array}
    $$

Por lo tanto, resolvemos el problema de la siguiente manera:



In [10]:

    
P = matrix([[4., 1.], [1., 2.]])
q = matrix([1., 1.])
G = matrix([[-1., 0.], [0., -1.]])
h = matrix([0., 0.])
A = matrix([[1.], [1.]])
b = matrix([1.])

sol = solvers.qp(P, q, G, h, A, b)
print sol['x']









    



     pcost       dcost       gap    pres   dres
 0:  1.8889e+00  7.7778e-01  1e+00  3e-16  2e+00
 1:  1.8769e+00  1.8320e+00  4e-02  1e-16  6e-02
 2:  1.8750e+00  1.8739e+00  1e-03  2e-16  5e-04
 3:  1.8750e+00  1.8750e+00  1e-05  2e-16  5e-06
 4:  1.8750e+00  1.8750e+00  1e-07  1e-16  5e-08
Optimal solution found.
[ 2.50e-01]
[ 7.50e-01]

Referencias:

CVXOPT: http://cvxopt.org/