Introduction to Disciplined Convex Programming with CVXPy - Mines Nancy

What is it?¶

A set of rules, a language that permits to formulate and implement efficiently convex optimization problems.

This is the underlying language of numerical solvers, such as CVXPY (Python) or CVX (Matlab).

In this course we look at CVXPy, a Python-based solver using Discplined Convex Programming (DCP)

see https://www.cvxpy.org/ for tutorial and documentation
see also the lectures slides on Stanford’s convex optimization lecture
you can also check the JMLR paper: CVXPY: A Python-Embedded Modeling Language for Convex Optimization by S. Diamond and S. Boyd

The key idea is that by properly formulating your problem using DCP, CVXPy will ‘pick up’ the appropriate solver to efficiently return a solution.

Example from CVX tutorial¶

We consider solving the following problem

\begin{array}{ll} \minimize& \quad (x-y)^2\\ \st & \quad x+y =1\\ &\quad x-1 \geq 1 \end{array}

(1)

In CVXPy, the code reads:

import cvxpy as cp

# Create two scalar optimization variables.
x = cp.Variable()
y = cp.Variable()

# Create two constraints.
constraints = [x + y == 1,
                x - y >= 1]

# Form objective.
obj = cp.Minimize((x - y)**2)

# Form and solve problem.
prob = cp.Problem(obj, constraints)
prob.solve(verbose=True)  # Returns the optimal value.
print("status:", prob.status)
print("optimal value", prob.value)
print("optimal var", x.value, y.value)

(CVXPY) Dec 11 09:45:39 AM: Your problem has 2 variables, 2 constraints, and 0 parameters.

(CVXPY) Dec 11 09:45:39 AM: It is compliant with the following grammars: DCP, DQCP

(CVXPY) Dec 11 09:45:39 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)

(CVXPY) Dec 11 09:45:39 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.

(CVXPY) Dec 11 09:45:39 AM: Your problem is compiled with the CPP canonicalization backend.

(CVXPY) Dec 11 09:45:39 AM: Compiling problem (target solver=OSQP).

(CVXPY) Dec 11 09:45:39 AM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> OSQP

(CVXPY) Dec 11 09:45:39 AM: Applying reduction CvxAttr2Constr

(CVXPY) Dec 11 09:45:39 AM: Applying reduction Qp2SymbolicQp

(CVXPY) Dec 11 09:45:39 AM: Applying reduction QpMatrixStuffing

(CVXPY) Dec 11 09:45:39 AM: Applying reduction OSQP

(CVXPY) Dec 11 09:45:39 AM: Finished problem compilation (took 7.763e-02 seconds).

(CVXPY) Dec 11 09:45:39 AM: Invoking solver OSQP  to obtain a solution.

(CVXPY) Dec 11 09:45:39 AM: Problem status: optimal

(CVXPY) Dec 11 09:45:39 AM: Optimal value: 1.000e+00

(CVXPY) Dec 11 09:45:39 AM: Compilation took 7.763e-02 seconds

(CVXPY) Dec 11 09:45:39 AM: Solver (including time spent in interface) took 1.863e-03 seconds

===============================================================================
                                     CVXPY                                     
                                     v1.7.5                                    
===============================================================================
-------------------------------------------------------------------------------
                                  Compilation                                  
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
                                Numerical solver                               
-------------------------------------------------------------------------------
-----------------------------------------------------------------
           OSQP v1.0.0  -  Operator Splitting QP Solver
              (c) The OSQP Developer Team
-----------------------------------------------------------------
problem:  variables n = 3, constraints m = 3
          nnz(P) + nnz(A) = 8
settings: algebra = Built-in,
          OSQPInt = 4 bytes, OSQPFloat = 8 bytes,
          linear system solver = QDLDL v0.1.8,
          eps_abs = 1.0e-05, eps_rel = 1.0e-05,
          eps_prim_inf = 1.0e-04, eps_dual_inf = 1.0e-04,
          rho = 1.00e-01 (adaptive: 50 iterations),
          sigma = 1.00e-06, alpha = 1.60, max_iter = 10000
          check_termination: on (interval 25, duality gap: on),
          time_limit: 1.00e+10 sec,
          scaling: on (10 iterations), scaled_termination: off
          warm starting: on, polishing: on, 
iter   objective    prim res   dual res   gap        rel kkt    rho         time
   1   0.0000e+00   1.00e+00   1.00e+02  -1.00e+02   1.00e+02   1.00e-01    5.52e-05s
  50   9.6112e-01   1.96e-02   1.96e-09  -3.85e-02   1.96e-02   3.85e+02*   1.17e-04s
  75   1.0000e+00   3.94e-08   1.07e-10   7.88e-08   7.88e-08   3.85e+02    1.81e-04s
plsh   1.0000e+00   1.57e-22   0.00e+00   0.00e+00   1.57e-22   --------    2.47e-04s

status:               solved
solution polishing:   successful
number of iterations: 75
optimal objective:    1.0000
dual objective:       1.0000
duality gap:          0.0000e+00
primal-dual integral: 1.0038e+02
run time:             2.47e-04s
optimal rho estimate: 8.77e+03

-------------------------------------------------------------------------------
                                    Summary                                    
-------------------------------------------------------------------------------
status: optimal
optimal value 1.0
optimal var 1.0 1.570086213240983e-22

8.4 Introduction to Disciplined Convex Programming with CVXPy

What is it?¶

Example from CVX tutorial¶