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) Oct 13 09:02:22 AM: Your problem has 2 variables, 2 constraints, and 0 parameters.

(CVXPY) Oct 13 09:02:22 AM: It is compliant with the following grammars: DCP, DQCP

(CVXPY) Oct 13 09:02:22 AM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)

(CVXPY) Oct 13 09:02:22 AM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.

(CVXPY) Oct 13 09:02:22 AM: Your problem is compiled with the CPP canonicalization backend.

(CVXPY) Oct 13 09:02:22 AM: Compiling problem (target solver=OSQP).

(CVXPY) Oct 13 09:02:22 AM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> OSQP

(CVXPY) Oct 13 09:02:22 AM: Applying reduction CvxAttr2Constr

(CVXPY) Oct 13 09:02:22 AM: Applying reduction Qp2SymbolicQp

(CVXPY) Oct 13 09:02:22 AM: Applying reduction QpMatrixStuffing

(CVXPY) Oct 13 09:02:22 AM: Applying reduction OSQP

(CVXPY) Oct 13 09:02:22 AM: Finished problem compilation (took 1.041e-01 seconds).

(CVXPY) Oct 13 09:02:22 AM: Invoking solver OSQP  to obtain a solution.

(CVXPY) Oct 13 09:02:22 AM: Problem status: optimal

(CVXPY) Oct 13 09:02:22 AM: Optimal value: 1.000e+00

(CVXPY) Oct 13 09:02:22 AM: Compilation took 1.041e-01 seconds

(CVXPY) Oct 13 09:02:22 AM: Solver (including time spent in interface) took 1.331e-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.02e-05s
  50   9.6112e-01   1.96e-02   1.96e-09  -3.85e-02   1.96e-02   3.85e+02*   9.66e-05s
  75   1.0000e+00   3.94e-08   1.07e-10   7.88e-08   7.88e-08   3.85e+02    1.39e-04s
plsh   1.0000e+00   1.57e-22   0.00e+00   0.00e+00   1.57e-22   --------    1.84e-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:             1.84e-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¶