Convex.jl - Convex Optimization in Julia¶

Variables¶

The simplest kind of expression in Convex.jl is a variable. Variables in Convex.jl are declared using the Variable keyword, along with the dimensions of the variable.

# Scalar variable
x = Variable()

# Column vector variable
x = Variable(5)

# Matrix variable
x = Variable(4, 6)

Variables may also be declared as having special properties, such as being

• (entrywise) positive: x = Variable(4, Positive())
• (entrywise) negative: x = Variable(4, Negative())
• integral: x = Variable(4, :Int)
• binary: x = Variable(4, :Bin)
• (for a matrix) being symmetric, with nonnegative eigenvalues (ie, positive semidefinite): z = Semidefinite(4)

Constants¶

Numbers, vectors, and matrices present in the Julia environment are wrapped automatically into a Constant expression when used in a Convex.jl expression.

Expressions¶

Expressions in Convex.jl are formed by applying any atom (mathematical function defined in Convex.jl) to variables, constants, and other expressions. For a list of these functions, see operations. Atoms are applied to expressions using operator overloading. For example, 2+2 calls Julia’s built-in addition operator, while 2+x calls the Convex.jl addition method and returns a Convex.jl expression. Many of the useful language features in Julia, such as arithmetic, array indexing, and matrix transpose are overloaded in Convex.jl so they may be used with variables and expressions just as they are used with native Julia types.

Expressions that are created must be DCP-compliant. More information on DCP can be found here.

x = Variable(5)
# The following are all expressions
y = sum(x)
z = 4 * x + y
z_1 = z[1]

Convex.jl allows the values of the expressions to be evaluated directly.

x = Variable()
y = Variable()
z = Variable()
expr = x + y + z
problem = minimize(expr, x >= 1, y >= x, 4 * z >= y)
solve!(problem)

# Once the problem is solved, we can call evaluate() on expr:
evaluate(expr)

Constraints¶

Constraints in Convex.jl are declared using the standard comparison operators <=, >=, and ==. They specify relations that must hold between two expressions. Convex.jl does not distinguish between strict and non-strict inequality constraints.

x = Variable(5, 5)
# Equality constraint
constraint = x == 0
# Inequality constraint
constraint = x >= 1

Matrices can also be constrained to be positive semidefinite.

x = Variable(3, 3)
y = Variable(3, 1)
z = Variable()
# constrain [x y; y' z] to be positive semidefinite
constraint = ([x y; y' z] in :SDP)
# or equivalently,
constraint = ([x y; y' z] ⪰ 0)

Objective¶

The objective of the problem is a scalar expression to be maximized or minimized by using maximize or minimize respectively. Feasibility problems can be expressed by either giving a constant as the objective, or using problem = satisfy(constraints).

Problem¶

A problem in Convex.jl consists of a sense (minimize, maximize, or satisfy), an objective (an expression to which the sense verb is to be applied), and zero or more constraints that must be satisfied at the solution. Problems may be constructed as

problem = minimize(objective, constraints)
# or
problem = maximize(objective, constraints)
# or
problem = satisfy(constraints)

Constraints can be added at any time before the problem is solved.

# No constraints given
problem = minimize(objective)
# Add some constraint
problem.constraints += constraint
# Add many more constraints
problem.constraints += [constraint1, constraint2, ...]

A problem can be solved by calling solve!:

solve!(problem)

After the problem is solved, problem.status records the status returned by the optimization solver, and can be :Optimal, :Infeasible, :Unbounded, :Indeterminate or :Error. If the status is :Optimal, problem.optval will record the optimum value of the problem. The optimal value for each variable x participating in the problem can be found in x.value. The optimal value of an expression can be found by calling the evaluate() function on the expression as follows: evaluate(expr).

Linear Program Representable Functions¶

An optimization problem using only these functions can be solved by any LP solver.

Second-Order Cone Representable Functions¶

An optimization problem using these functions can be solved by any SOCP solver (including ECOS, SCS, Mosek, Gurobi, and CPLEX). Of course, if an optimization problem has both LP and SOCP representable functions, then any solver that can solve both LPs and SOCPs can solve the problem.

Exponential Cone Representable Functions¶

An optimization problem using these functions can be solved by any exponential cone solver (SCS).

Semidefinite Program Representable Functions¶

An optimization problem using these functions can be solved by any SDP solver (including SCS and Mosek).

Exponential + SDP representable Functions¶

An optimization problem using these functions can be solved by any solver that supports exponential constraints and semidefinite constraints simultaneously (SCS).

Promotions¶

When an atom or constraint is applied to a scalar and a higher dimensional variable, the scalars are promoted. For example, we can do max(x, 0) gives an expression with the shape of x whose elements are the maximum of the corresponding element of x and 0.

Complex Variables¶

Complex Variables in Convex.jl are declared in the same way as the variables are declared but using the different keyword ComplexVariable.

# Scalar complex variable
z = ComplexVariable()

# Column vector variable
z = ComplexVariable(5)

# Matrix variable
z = ComplexVariable(4, 6)

# Complex Positive Semidefinite variable
z = HermitianSemidefinite(4)

Linear Program Representable Functions¶

All of the linear functions that are listed here operate on complex variables as well. In addition, several specialized functions for complex variables are available:

Second-Order Cone Representable Functions¶

Most of the second order cone function listed here operate on complex variables as well. Notable exceptions include:

• inverse
• square
• quadoverlin
• sqrt
• geomean
• huber

One new function is available:

Semidefinite Program Representable Functions¶

All SDP-representable functions listed here work for complex variables.

Exponential + SDP representable Functions¶

Complex variables also support logdet function.

Where can I get help?¶

For usage questions, please contact us via the JuliaOpt mailing list. If you’re running into bugs or have feature requests, please use the Github Issue Tracker.

How does Convex.jl differ from JuMP?¶

Convex.jl and JuMP are both modelling languages for mathematical programming embedded in Julia, and both interface with solvers via the MathProgBase interface, so many of the same solvers are available in both. Convex.jl converts problems to a standard conic form. This approach requires (and certifies) that the problem is convex and DCP compliant, and guarantees global optimality of the resulting solution. JuMP allows nonlinear programming through an interface that learns about functions via their derivatives. This approach is more flexible (for example, you can optimize non-convex functions), but can’t guarantee global optimality if your function is not convex, or warn you if you’ve entered a non-convex formulation.

For linear programming, the difference is more stylistic. JuMP’s syntax is scalar-based and similar to AMPL and GAMS making it easy and fast to create constraints by indexing and summation (like sum{x[i], i=1:numLocation}). Convex.jl allows (and prioritizes) linear algebraic and functional constructions (like max(x,y) < A*z); indexing and summation are also supported in Convex.jl, but are somewhat slower than in JuMP. JuMP also lets you efficiently solve a sequence of problems when new constraints are added or when coefficients are modified, whereas Convex.jl parses the problem again whenever the solve! method is called.

Where can I learn more about Convex Optimization?¶

See the freely available book Convex Optimization by Boyd and Vandenberghe for general background on convex optimization. For help understanding the rules of Disciplined Convex Programming, we recommend this DCP tutorial website.

Are there similar packages available in other languages?¶

Indeed! You might use CVXPY in Python, or CVX in Matlab.

How does Convex.jl work?¶

For a detailed discussion of how Convex.jl works, see our paper.

How do I cite this package?¶

If you use Convex.jl for published work, we encourage you to cite the software using the following BibTeX citation:

@article{convexjl,
 title = {Convex Optimization in {J}ulia},
 author ={Udell, Madeleine and Mohan, Karanveer and Zeng, David and Hong, Jenny and Diamond, Steven and Boyd, Stephen},
 year = {2014},
 journal = {SC14 Workshop on High Performance Technical Computing in Dynamic Languages},
 archivePrefix = "arXiv",
 eprint = {1410.4821},
 primaryClass = "math-oc",
}

Memory Management¶

Convex uses a module-level dictionary to store the conic forms of every variable and expression created in the same Julia session. These variables and expressions persist even after they are out of scope. If you create large numbers of variables inside a loop, this dictionary can eat a considerable amount of memory.

To flush the memory, you can call

Convex.clearmemory()

This will remove every variable and expression you’ve formed before from the memory cache, so that you’re starting as fresh as if you’d just reimported Convex.

Caching Expressions¶

Better yet, take advantage of this cache of variables and expressions! Create variables and expressions outside the loop, and reuse them inside the loop as you tweak parameters. Doing this will allow Convex to reuse the conic forms it has already calculated for previously used expressions.

For example, the following bad code will create a new instance of a variable and of the expression square(x) for each value of i. Don’t do this:

for i=1:10
        x = Variable()
        p = minimize(square(x), x >= i)
        solve!(p)
end

Contrast this with the following good code, which will reuse the cached conic form for square(x) for each i, reducing the memory footprint and speeding up the computation. Do this instead:

x = Variable()
obj = square(x)
for i=1:10
        p = minimize(obj, x >= i)
        solve!(p)
end

Warmstarts, Parameters, Fixing and Freeing Variables¶

If you’re solving many problems of the same form, or many similar problems, you may also want to use warmstarts, or to dynamically fix and free variables. The former is particularly good for a family of problems related by a parameter; the latter allows for easy implementation of alternating minimization for nonconvex problems. See the Advanced Features section of the documentation for more information.

Dual Variables¶

Convex.jl also returns the optimal dual variables for a problem. These are stored in the dual field associated with each constraint.

using Convex

x = Variable()
constraint = x >= 0
p = minimize(x, constraint)
solve!(p)

# Get the dual value for the constraint
p.constraints[1].dual
# or
constraint.dual

Warmstarting¶

If you’re solving the same problem many times with different values of a parameter, Convex.jl can initialize many solvers with the solution to the previous problem, which sometimes speeds up the solution time. This is called a warm start.

To use this feature, pass the optional argument warmstart=true to the solve! method.

# initialize data
n = 1000
y = rand(n)
x = Variable(n)

# first solve
lambda = 100
problem = minimize(sumsquares(y - x) + lambda * sumsquares(x - 10))
@time solve!(problem)

# now warmstart
# if the solver takes advantage of warmstarts,
# this run will be faster
lambda = 105
@time solve!(problem, warmstart=true)

Fixing and freeing variables¶

Convex.jl allows you to fix a variable x to a value by calling the fix! method. Fixing the variable essentially turns it into a constant. Fixed variables are sometimes also called parameters.

fix(x, v) fixes the variable x to the value v.

fix(x) fixes x to the value x.value, which might be the value obtained by solving another problem involving the variable x.

To allow the variable x to vary again, call free!(x).

Fixing and freeing variables can be particularly useful as a tool for performing alternating minimization on nonconvex problems. For example, we can find an approximate solution to a nonnegative matrix factorization problem with alternating minimization as follows. We use warmstarts to speed up the solution.

# initialize nonconvex problem
n, k = 10, 1
A = rand(n, k) * rand(k, n)
x = Variable(n, k)
y = Variable(k, n)
problem = minimize(sum_squares(A - x*y), x>=0, y>=0)

# initialize value of y
y.value = rand(k, n)
# we'll do 10 iterations of alternating minimization
for i=1:10
        # first solve for x
        # with y fixed, the problem is convex
        fix!(y)
        solve!(problem, warmstart = i > 1 ? true : false)
        free!(y)

        # now solve for y with x fixed at the previous solution
        fix!(x)
        solve!(problem, warmstart = true)
        free!(x)
end

Adding examples¶

• Take a look at our exising usage examples and add another in similar style.
• Submit a PR. (Let us know if it’s a work in progress by putting [WIP] in the name of the PR.)
• We’ll look it over, fix up anything that doesn’t work, and merge it!

Adding atoms¶

Here are the steps to add a new function or operation (atom) to Convex.jl. Let’s say you’re adding the new function \(f\).

• Take a look at the nuclear norm atom for an example of how to construct atoms, and see the norm atom for an example of an atom that depends on a parameter.
• Copy paste (eg) the nuclear norm file, replace anything saying nuclear norm with the name of the atom \(f\), fill in monotonicity, curvature, etc. Save it in the appropriate subfolder of src/atoms/.
• Add as a comment a description of what the atom does and its parameters.
• The most mathematically interesting part is the conic_form! function. Following the example in the nuclear norm atom, you’ll see that you can just construct the problem whose optimal value is \(f(x)\), introducing any auxiliary variables you need, exactly as you would normally in Convex.jl, and then call cache_conic_form! on that problem.
• Add a test for the atom so we can verify it works in test/test_<cone>, where <cone> matches the subfolder of src/atoms.
• Submit a PR, including a description of what the atom does and its parameters. (Let us know if it’s a work in progress by putting [WIP] in the name of the PR.)
• We’ll look it over, fix up anything that doesn’t work, and merge it!

Fixing the guts¶

If you want to do a more major bug fix, you may need to understand how Convex.jl thinks about conic form. To do this, start by reading the Convex.jl paper. Then read the conic form code:

• We define data structures for conic objectives and conic constraints, and simple ways of combining them, in conic_form.jl
• We convert the internal conic form representation into the standard form for conic solvers in the function conic_problem.
• We solve problems (that is, pass the standard form of the problem to a solver, and put the solution back into the values of the appropriate variables) in solution.jl.

You’re now armed and dangerous. Go ahead and open an issue (or comment on a previous one) if you can’t figure something out, or submit a PR if you can figure it out. (Let us know if it’s a work in progress by putting [WIP] in the name of the PR.)

PRs that comment the code more thoroughly will also be welcomed.