Convex Optimization in Python with CVXPY

Steven Diamond Stephen Boyd

Stanford University

TCMM 2014, September 2014

1
Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

Convex optimization 2
Convex optimization problem

minimize f0 (x)
subject to fi (x) ≤ 0, i = 1, . . . , m
Ax = b,
with variable x ∈ Rn

I objective and inequality constraints f0 , . . . , fm are convex

for all x, y , θ ∈ [0, 1],

fi (θx + (1 − θ)y ) ≤ θfi (x) + (1 − θ)fi (y )

i.e., graphs of fi curve upward

I equality constraints are linear

Convex optimization 3
Why convex optimization?

I beautiful, fairly complete, and useful theory

I solution algorithms that work well in theory and practice
I many applications in
I machine learning, statistics
I control
I signal, image processing
I networking
I engineering design
I finance
. . . and many more

Convex optimization 4
How do you solve a convex problem?

I use someone else’s (‘standard’) solver (LP, QP, SOCP, . . . )

I easy, but your problem must be in a standard form
I cost of solver development amortized across many users

I write your own (custom) solver

I lots of work, but can take advantage of special structure

I use a convex modeling language

I transforms user-friendly format into solver-friendly standard form
I extends reach of problems solvable by standard solvers

Convex optimization 5
Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

Convex modeling languages 6

Convex modeling languages

I long tradition of modeling languages for optimization

I cf. AMPL, GAMS
I modeling languages for convex optimization
I e.g., CVX, YALMIP, CVXGEN, QCML
I function of a convex modeling language:
I check/verify problem convexity
I convert to standard form

Convex modeling languages 7

Disciplined convex programming (DCP)

I system for constructing expressions with known curvature

I constant, affine, nonnegative (convex), nonpositive (concave)
I expressions formed from
I variables (curvature: affine, unknown sign)
I constants (curvature: constant, known sign)
I library of atoms with known curvature and sign (as function of
their arguments)
I more at dcp.stanford.edu

Convex modeling languages 8

Standard (conic) form

minimize c T x
subject to Ax = b
x ∈K
with variable x ∈ Rn
I K is convex cone
I x ∈ K is a generalized nonnegativity constraint
I linear objective, equality constraints
I special cases:
I K = Rn+ : linear program (LP)
I K = Sn+ : semidefinite program (SDP)
I general interface for solvers
Convex modeling languages 9
Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

CVXPY 10
CVXPY

a modeling language in Python for convex optimization

I translates from math to standard form used by solvers

I uses DCP to verify convexity
I open source all the way from the solvers
I supports parameterized problems
I mixes easily with general Python code, other libraries
I already used in many research projects and two classes
I over 7000 downloads on PyPi

CVXPY 11
CVXPY solvers
I all open source
I CVXOPT (Vandenberghe, Dahl, Andersen)
I interior-point method
I in Python
I ECOS (Domahidi)
I interior-point method
I compact, library-free C code
I SCS (O’Donoghue)
I first-order method
I native support of exponential cone
I parallelism with OpenMP

CVXPY 12
CVXPY example
(constrained LASSO)

minimize kAx − bk22 + γkxk1

subject to 1T x = 0, kxk∞ ≤ 1

with variable x ∈ Rn

from cvxpy import *

x = Variable(n)
cost = sum_squares(A*x-b) + gamma*norm(x,1)
obj = Minimize(cost)
constr = [sum_entries(x) == 0, norm(x,"inf") <= 1]
prob = Problem(obj, constr)
opt_val = prob.solve()
solution = x.value

CVXPY 13
Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

Image in-painting 14
Image in-painting

I guess pixel values in obscured/corrupted parts of image

I total variation in-painting: choose pixel values xij ∈ R3 to
minimize
X  xi+1,j − xij 
TV(x) =
xi,j+1 − xij 2
ij

I a convex problem

Image in-painting 15
Example

I 512 × 512 color image

I denote corrupted pixels with K ∈ {0, 1}512×512
I Kij = 1 if pixel value is known
I Kij = 0 if unknown
I Xcorr ∈ R512×512×3 is corrupted image

Image in-painting 16
Image in-painting CVXPY code

from cvxpy import *

variables = []
constr = []
for i in range(3):
X = Variable(512, 512)
variables += [X]
constr += [mul_elemwise(K, X - X_corr[:,:,i]) == 0]

prob = Problem(Minimize(tv(*variables)), constr)

prob.solve(solver=SCS)

Image in-painting 17
Example

Original Corrupted

Image in-painting 18
Example

Original Recovered

Image in-painting 19
Example (80% of pixels removed)

Original Corrupted

Image in-painting 20
Example (80% of pixels removed)

Original Recovered

Image in-painting 21
Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

Trade-off curve, in parallel 22

Parameters

I symbolic representations of constants

I fixed sign and dimensions
I change value of constant without rebuilding problem

Trade-off curve, in parallel 23

Parameter syntax

# Positive scalar parameter.

gamma = Parameter(sign="positive")

# Column vector parameter with unknown sign (by default).

c = Parameter(5)

# Matrix parameter with negative entries.

G = Parameter(4, 7, sign="negative")

# Assigns a constant value to G.

G.value = -numpy.ones((4, 7))

Trade-off curve, in parallel 24

LASSO in CVXPY

(LASSO)
minimize kAx − bk22 + γkxk1
with variable x ∈ Rn

x = Variable(n)
gamma = Parameter(sign="positive")
error = sum_squares(A*x-b)
regularization = gamma*norm(x,1)
prob = Problem(Minimize(error + regularization))

Trade-off curve, in parallel 25

For loop style trade-off curve

compute a trade-off curve by updating parameter gamma

x_values = []
for val in numpy.logspace(-4, 2):
gamma.value = val
prob.solve()
x_values.append(x.value)

Trade-off curve, in parallel 26

Trade-off curve for LASSO

Trade-off curve, in parallel 27

Entries of x versus γ: (regularization path)

Trade-off curve, in parallel 28

Parallel style trade-off curve

# Use tools for parallelism in standard library.

from multiprocessing import Pool

# Assign a value to gamma and find the optimal x.

def get_x(gamma_value):
gamma.value = gamma_value
result = prob.solve()
return x.value

# Parallel computation with N processes.

pool = Pool(processes = N)
x_values = pool.map(get_x, numpy.logspace(-4, 2))

Trade-off curve, in parallel 29

Performance

I Lasso with A ∈ R1000×500 , 100 values of γ

I single thread time for one LASSO: 4 seconds
I performance using solver SCS:
For loop 4 processes 32 processes
4 core MacBook Pro 403 sec 147 sec 136 sec
32 cores, Intel Xeon 619 sec 175 sec 56 sec

Trade-off curve, in parallel 30

Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

Single commodity flow 31

Single commodity flow
I directed graph with p nodes, n edges
I flow fi on edge i
I external source/sink flow sj at node j
I single commodity flow problem:
Pn Pp
minimize i=1 φi (fi ) + j=1 ψj (sj ),
subject to zero net flow at each node

I variables are fi , sj
I φi convex flow cost functions
I ψj convex source cost functions
I can include constraints in φi , ψj
Single commodity flow 32
Matrix representation

I node incidence matrix A ∈ Rp×n


+1 edge i leaves node j

Aij = −1 edge i enters node j

0 otherwise.


I zero net flow at each node: Af = s

I final problem:
Pn Pp
minimize i=1 φi (fi ) + j=1 ψj (sj ),
subject to Af = s

Single commodity flow 33

Object-oriented representation

I node object includes source, cost, source/net flow constraints

I edge object includes flow, cost, flow constraints
I solve the problem:
cost = sum([object.cost for object in nodes + edges])
obj = Minimize(cost)
constraints = []
for object in nodes + edges:
constraints += object.constraints()
Problem(obj, constraints).solve()

Single commodity flow 34

Node object

class Node(object):
def __init__(self, cost):
self.source = Variable()
self.cost = cost(self.source)
self.edge_flows = []

def constraints(self):
"""The constraint net flow == 0."""
net_flow = sum(self.edge_flows) + self.source
return [net_flow == 0]

Single commodity flow 35

Edge object

class Edge(object):
def __init__(self, cost):
self.flow = Variable()
self.cost = cost(self.flow)

def connect(self, in_node, out_node):

"""Connects two nodes via the edge."""
in_node.edge_flows.append(-self.flow)
out_node.edge_flows.append(self.flow)

Single commodity flow 36

Example

I 7-by-7 grid of nodes

I 1 unit of flow sent from source s1 to sink sn :
I s1 = +1
I sn = −1
I si = 0 for i = 2, . . . , n − 1
flow cost φi (fi ) = wi |fi | + λfi 2


I

I weights wi > 0 randomly chosen

Single commodity flow 37

Shortest path (λ = 0)

Single commodity flow 38

Diffusion (λ = +∞)

Single commodity flow 39

Diffusion with sparsity (λ = 1)

Single commodity flow 40

Outline

Convex optimization

Convex modeling languages

CVXPY

Image in-painting

Trade-off curve, in parallel

Single commodity flow

Summary

Summary 41
Summary

I convex optimization is easy with CVXPY

I mixes well with high level Python
I parallelism
I object oriented design
I building block for
I distributed optimization
I nonconvex optimization

Summary 42
Future work

I not just for prototyping

I speed and scalability
I abstract linear operators

Summary 43