Document Actions

9.1 General Solver

cp(F[, G, h[, dims[, A, b[, kktsolver]]]])

Solves a convex optimization problem

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & f_0(x) \\ \mbox{subj... ... k=1,\ldots,m \\ & G x \preceq h \\ & A x = b, \end{array}\end{displaymath}$

(9.1)

The argument F is a function that evaluates the objective and nonlinear constraint functions. It must handle the following calling sequences.

F() returns a tuple (m, x0), where m is the number of nonlinear constraints and x0 is a point in the domain of f. x0 is a dense real matrix of size (n, 1).
F(x), with x a dense real matrix of size (n,1), returns a tuple (f, Df). f is a dense real matrix of size (m+1,1), with f[k] equal to f_k(x). (If m is zero, f can also be returned as a number.) Df is a dense or sparse real matrix of size (m+1, n) with Df[k,:] equal to the transpose of the gradient $\nabla f_k(x)$ . If x is not in the domain of f, F(x) returns None or a tuple (None,None).
F(x,z), with x a dense real matrix of size (n,1) and z a positive dense real matrix of size (m+1,1) returns a tuple (f, Df, H). f and Df are defined as above. H is a square dense or sparse real matrix of size (n, n), whose lower triangular part contains the lower triangular part of

$\begin{displaymath} z_0 \nabla^2f_0(x) + z_1 \nabla^2f_1(x) + \cdots + z_m \nabla^2f_m(x). \end{displaymath}$

If F is called with two arguments, it can be assumed that x is in the domain of f.

The linear inequalities are with respect to a cone C defined as a Cartesian product of a nonnegative orthant, a number of second-order cones, and a number of positive semidefinite cones:

$\begin{displaymath} C = C_0 \times C_1 \times \cdots \times C_M \times C_{M+1} \times \cdots \times C_{M+N} \end{displaymath}$

with

$\begin{displaymath} C_0 = \{ u \in {\mbox{\bf R}}^l \;\vert \; u_k \geq 0, \; ... ... u \in {\mbox{\bf S}}^{t_k}_+ \right\}, \quad k=0,\ldots,N-1. \end{displaymath}$

Here $\mathop{\mathbf{vec}}(u)$ denotes a symmetric matrix u stored as a vector in column major order.

The arguments h and b are real single-column dense matrices. G and A are real dense or sparse matrices. The default values for A and b are sparse matrices with zero rows, meaning that there are no equality constraints. The number of rows of G and h is equal to

$\begin{displaymath} K = l + \sum_{k=0}^{M-1} r_k + \sum_{k=0}^{N-1} t_k^2. \end{displaymath}$

The columns of G and h are vectors in

$\begin{displaymath} {\mbox{\bf R}}^l \times {\mbox{\bf R}}^{r_0} \times \cdots \... ... R}}^{t_0^2} \times \cdots \times {\mbox{\bf R}}^{t_{N-1}^2}, \end{displaymath}$

where the last N components represent symmetric matrices stored in column major order. The strictly upper triangular entries of these matrices are not accessed (i.e., the symmetric matrices are stored in the 'L'-type column major order used in the blas and lapack modules).

The argument dims is a dictionary with the dimensions of the cones. It has three fields.

dims['l']:: l, the dimension of the nonnegative orthant (a nonnegative integer).
dims['q']:: $[r_0, \ldots, r_{M-1}]$ , a list with the dimensions of the second-order cones (positive integers).
dims['s']:: $[t_0, \ldots, t_{N-1}]$ , a list with the dimensions of the positive semidefinite cones (nonnegative integers).

The default value of dims is {'l': h.size[0], 'q': [], 's': []}, i.e., the default assumption is that the linear inequalities are componentwise inequalities.

The role of the optional argument kktsolver is explained in section 9.4.

cp() returns a dictionary with keys 'status', 'x', 'snl', 'sl', 'y', 'znl', 'zl'. The possible values of the 'status' key are:

'optimal'

In this case the 'x' entry of the dictionary is the primal optimal solution, the 'snl' and 'sl' entries are the corresponding slacks in the nonlinear and linear inequality constraints, and the 'znl', 'zl' and 'y' entries are the optimal values of the dual variables associated with the nonlinear inequalities, the linear inequalities, and the linear equality constraints. These vectors approximately satisfy the Karush-Kuhn-Tucker (KKT) conditions

$\begin{displaymath} \nabla f_0(x) + D\tilde f(x)^T z_\mathrm{nl} + G^T z_\mat... ... k=1,\ldots,m, \qquad Gx + s_\mathrm{l} = h, \qquad Ax = b, \end{displaymath}$

where $\tilde f = (f_1,\ldots, f_m)$ ,

$\begin{displaymath} s_\mathrm{nl}\succeq 0, \qquad s_\mathrm{l}\succeq 0, \qquad... ...\mathrm{nl}^T z_\mathrm{nl} + s_\mathrm{l}^T z_\mathrm{l} = 0. \end{displaymath}$

'unknown'

This indicates that the algorithm reached the maximum number of iterations before a solution was found. The 'x', 'snl', 'sl', 'y', 'znl' and 'zl' entries are None.

cp() requires that the problem is solvable and that

$\begin{displaymath} \Rank(A) = p, \qquad \Rank\left(\left[\begin{array}{cccccc}... ...x) & \cdots \nabla f_m(x) & G^T \end{array}\right]\right) = n, \end{displaymath}$

for all x and all positive z.

Example: equality constrained analytic centering

The equality constrained analytic centering problem is defined as

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & -\sum_{i=1}^m \log x_i \\ \mbox{subject to} & Ax = b. \end{array}\end{displaymath}$

The function acent() defined below solves the problem, assumping it is solvable.

from cvxopt import solvers 
from cvxopt.base import matrix, spdiag, log

def acent(A, b):
    m, n = A.size
    def F(x=None, z=None):
        if x is None: return 0, matrix(1.0, (n,1))
        if min(x) <= 0.0: return None
        f = -sum(log(x))
        Df = -(x**-1).T 
        if z is None: return f, Df
        H = spdiag(z[0] * x**-2)
        return f, Df, H
    return solvers.cp(F, A=A, b=b)['x']

Example: robust least-squares

The function robls() defined below solves the unconstrained problem

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & \sum_{k=1}^m \phi((Ax-b)... ...{\mbox{\bf R}}^{m\times n}, \quad \phi(u) = \sqrt{\rho + u^2}. \end{displaymath}$

from cvxopt import solvers 
from cvxopt.base import matrix, spdiag, sqrt, div

def robls(A, b, rho): 
    m, n = A.size
    def F(x=None, z=None):
        if x is None: return 0, matrix(0.0, (n,1))
        y = A*x-b
        w = sqrt(rho + y**2)
        f = sum(w)
        Df = div(y, w).T * A 
        if z is None: return f, Df 
        H = A.T * spdiag(z[0]*rho*(w**-3)) * A
        return f, Df, H
    return solvers.cp(F)['x']

Example: analytic centering with cone constraints

$\begin{displaymath} \begin{array}{ll} \mbox{minimize} & - \log(1-x_1^2) - \log... ...\ 10 & 80 & 10 \\ 40 & 10 & 15 \end{array}\right]. \end{array}\end{displaymath}$

from cvxopt.base import matrix, log, div, spdiag
from cvxopt import solvers

def F(x = None, z = None):
     if x is None:  return 0, matrix(0.0, (3,1)) 
     if max(abs(x)) >= 1.0:  return None
     u = 1 - x**2
     val = -sum(log(u))
     Df = div(2*x, u).T
     if z is None:  return val, Df
     H = spdiag(2 * z[0] * div(1 + u**2, u**2))
     return val, Df, H

G = matrix([ [0., -1.,  0.,  0., -21., -11.,   0., -11.,  10.,   8.,   0.,   8., 5.], 
             [0.,  0., -1.,  0.,   0.,  10.,  16.,  10., -10., -10.,  16., -10., 3.], 
             [0.,  0.,  0., -1.,  -5.,   2., -17.,   2.,  -6.,   8., -17.,  -7., 6.] ])  
h = matrix([1.0, 0.0, 0.0, 0.0, 20., 10., 40., 10., 80., 10., 40., 10., 15.])
dims = {'l': 0, 'q': [4], 's':  [3]}
sol = solvers.cp(F, G, h, dims)
print sol['x']
[ 4.11e-01]
[ 5.59e-01]
[-7.20e-01]

CVXOPT

Sections

Personal tools

Document Actions

9.1 General Solver