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) Jan 06 02:13:13 PM: Your problem has 2 variables, 2 constraints, and 0 parameters.

(CVXPY) Jan 06 02:13:13 PM: It is compliant with the following grammars: DCP, DQCP

(CVXPY) Jan 06 02:13:13 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)

(CVXPY) Jan 06 02:13:13 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.

(CVXPY) Jan 06 02:13:13 PM: Your problem is compiled with the CPP canonicalization backend.

(CVXPY) Jan 06 02:13:13 PM: Compiling problem (target solver=OSQP).

(CVXPY) Jan 06 02:13:13 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> OSQP

(CVXPY) Jan 06 02:13:13 PM: Applying reduction CvxAttr2Constr

(CVXPY) Jan 06 02:13:13 PM: Applying reduction Qp2SymbolicQp

(CVXPY) Jan 06 02:13:13 PM: Applying reduction QpMatrixStuffing

(CVXPY) Jan 06 02:13:13 PM: Applying reduction OSQP

(CVXPY) Jan 06 02:13:13 PM: Finished problem compilation (took 5.468e-02 seconds).

(CVXPY) Jan 06 02:13:13 PM: Invoking solver OSQP  to obtain a solution.

(CVXPY) Jan 06 02:13:13 PM: Problem status: optimal

(CVXPY) Jan 06 02:13:13 PM: Optimal value: 1.000e+00

(CVXPY) Jan 06 02:13:13 PM: Compilation took 5.468e-02 seconds

(CVXPY) Jan 06 02:13:13 PM: Solver (including time spent in interface) took 2.088e-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    6.07e-05s
  50   9.6112e-01   1.96e-02   1.96e-09  -3.85e-02   1.96e-02   3.85e+02*   1.28e-04s
  75   1.0000e+00   3.94e-08   1.07e-10   7.88e-08   7.88e-08   3.85e+02    1.98e-04s
plsh   1.0000e+00   1.57e-22   0.00e+00   0.00e+00   1.57e-22   --------    2.65e-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.65e-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¶