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 21 10:01:36 PM: Your problem has 2 variables, 2 constraints, and 0 parameters.

(CVXPY) Dec 21 10:01:36 PM: It is compliant with the following grammars: DCP, DQCP

(CVXPY) Dec 21 10:01:36 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)

(CVXPY) Dec 21 10:01:36 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.

(CVXPY) Dec 21 10:01:36 PM: Your problem is compiled with the CPP canonicalization backend.

(CVXPY) Dec 21 10:01:36 PM: Compiling problem (target solver=OSQP).

(CVXPY) Dec 21 10:01:36 PM: Reduction chain: CvxAttr2Constr -> Qp2SymbolicQp -> QpMatrixStuffing -> OSQP

(CVXPY) Dec 21 10:01:36 PM: Applying reduction CvxAttr2Constr

(CVXPY) Dec 21 10:01:36 PM: Applying reduction Qp2SymbolicQp

(CVXPY) Dec 21 10:01:36 PM: Applying reduction QpMatrixStuffing

(CVXPY) Dec 21 10:01:36 PM: Applying reduction OSQP

(CVXPY) Dec 21 10:01:36 PM: Finished problem compilation (took 9.781e-02 seconds).

(CVXPY) Dec 21 10:01:36 PM: Invoking solver OSQP  to obtain a solution.

(CVXPY) Dec 21 10:01:36 PM: Problem status: optimal

(CVXPY) Dec 21 10:01:36 PM: Optimal value: 1.000e+00

(CVXPY) Dec 21 10:01:36 PM: Compilation took 9.781e-02 seconds

(CVXPY) Dec 21 10:01:36 PM: Solver (including time spent in interface) took 2.064e-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.00e-05s
  50   9.6112e-01   1.96e-02   1.96e-09  -3.85e-02   1.96e-02   3.85e+02*   1.31e-04s
  75   1.0000e+00   3.94e-08   1.07e-10   7.88e-08   7.88e-08   3.85e+02    1.97e-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¶