• A solver (Gurobi, MOSEK) is software for implementing optimization algorithms
  • Problems must be expressed as a standard form
• CVX is a modeling tool for convex optimization in MATLAB
  • Syntax is more straightforward and often close to the written mathematical formulation
  • Interacts with several different solvers
    • Automates putting a problem into standard form
    • Saves learning each solver's syntax
  • Can handle LP, QP, SOCP, SDP, GP
  • Convex.jl and CVXPY are spinoffs for Julia and Python

• Pros
  • Much easier to use, one stop shop for multiple solvers
  • Ability to quickly prototype
    • Validate method before spending time on algorithm development
    • Provides benchmark to faster algorithms
  • Well-documented with lots of examples
• Cons
  • Does not scale as well as the fast solvers (MOSEK and Gurobi)
  • Can't handle everything – some functions aren't supported

I'm not aware of an equivalent for R

• Gurobi and Mosek are available for R
  • R is great but it is not the ideal place for serious computing

MATLAB is very similar to R

• R users should be able to pick it up quickly
• MATLAB's documentation is great
• Useful MATLAB and R reference (thanks Isaac)

I hope to convince you that learning MATLAB for the sake of CVX is worth it!

• Here are some examples to see how much easier CVX is compared to Gurobi or the solvers in MATLAB's Optimization Toolbox

  • Linear programming: \(\ell_1\) regression
  • Quadratic Programming: Lasso regression

The source code and data are also available if you would like to play around with them on your own.

CVX technically solves disciplined convex programming (DCP) problems, which is a subset of convex optimization

• DCP consists of:
  • Atoms: basic functions/sets with known convexity
  • Rules: rules, based on convex analysis, for combining convex functions while preserving convexity

This allows CVX to verify convexity and quickly transform the problem into a solvable form

• So some convex expression may be rejected
  • Ex: norm(x, 2)^2 fails, use square_pos(norm(x, 2))
  • However, most convex functions are in fact DCP convex
  • If not, scan the CVX documentation

Optimization problem in standard form: \[\text{minimize } f_0(x) \] \[\text{subject to } f_i(x) \le 0, i = 1, ..., m\] \[\text{subject to } h_i(x) = 0, i = 1, ..., p\]

Corresponding CVX code:

cvx_begin
  variable x(n);
  minimize ( f0(x) );
  subject to
    f(x) <= 0;
    h(x) == 0;
cvx_end

cvx_begin & cvx_end

• Everything else (variables, objective functions, constraints, etc.) goes in bewteen
• cvx_begin can include a few keywords:
  • quiet: suppress screen output
    • Ex: cvx_begin quiet
  • sdp: semidefinite programming mode
  • gp: geometric programing mode
    • These allow for more natural syntax for SDP and GP problems

variable varname(dimensions) structure;

• Must do before a variable can be used in an objective function or constraint
• Variables can be scalars, vectors, matrices, or arrays
• Use variables to declare multiple varabies in the same statement
• structure is an optional keyword to specify that the variable has a special type of structure, such as symmetric, diagonal, etc.
  • See the CVX User Guide for the possible structures

For constrained problems, CVX also solves the dual problem

• There is one dual variable per constraint

To access the dual variables:

• Declare the dual variable after the variable statement:
  • dual variable y
• Associate it with the constraint:
  • y : A*x <= b;

Types of objective functions

• minimize( convex expression )
• maximize( concave expression )
• ommitted \(\Rightarrow\) feasibility problem

Notes

• Only one objective function can be specified at a time
• Must have a scalar value

CVX base fuction library includes a variaty of convex, concave, and affine functions

• Includes many common MATLAB functions
• Also new functions specifically for CVX
• A complete list is available and is a useful reference

New functions can be added if they satisfy the DCP rulset

• Ex: hinge loss for SVM
  • hingeLoss = @(x) sum(max(0, 1 - x));

Types of constraints

• convex expression <= concave expression
• concave expression >= convex expression
• affine expression == affine expression
  • Note == and not =
• Chained inequalities are allowed: l <= x <= u;

Other notes

• subject to: does nothing but helps readibility
• Constraints are applied element-wise
• Strict inequalities are the same as non-strict and are discouraged the CVX developers
• ~= is never valid

Set membership can also be used to define constraints

If our variable X is a symmetric psd matrix

• \(\mathbf{X} \in \mathbf{S}_+^n\)
• variable X(n,n) symmetric;
• X <In> semidefinite(n);

Estimating probabilities on the simplex

• \(x \in \{ \mathbf{x} \in \mathbb{R}^n | \sum_i x_i = 1, x_i \ge 0\) \(\forall\) \(i\}\)
• x <In> simplex(n)

See the CVX Users' Guide for a complete list of sets

After cvx_end, the model is solved:

• Optimization variables are replaced by their optimal values

CVX also creates some new variables related to the solution, including:

• cvx_optval: objective function's optimal value
• cvx_status: describes the status of the calculation, such as Solved, Infeasible, Failed, etc.
  • See the the users' guide for interpreting the results

Here is another example using only CVX to see how straightforward the implementation is

• 1-nom SVM

The CVX example library has a ton of examples!

The CVX Users' Guide also covers some advanced topics after you're familiar with the basics

MATLAB's attempt at generating reports that contain code, output, and figures with supporting text

• Output to HTML (default), XML, LaTeX, or PDF
• Different from "Matlab Report Generator", which isn't free

Warning: If you use R Markdown, prepare to be disappointed

• Publish is not as flexible or nice looking, but often gets the job done
• Given how long it has been around, and compared to other software, it's not too bad
  • Supposedly, it's getting a makeover in the next version
• Publishing code can take a little while (code is reevaluated)
  • I often use a separate, small working file to finalize the code and text for each section

1. MATLAB Editor: "Publish" tab \(\Rightarrow\) "Publish" button
   • May need to add the script's directory to MATLAB's path
   • Green triangle part of the Publish button publishes the document
   • Small black triangle opens a small menu
     • One option is to "Edit Publishing Options…"
       • Output format, destination folder, image format, whether code is included or evaluted
   • "Publish" menu has a lot of useful shortcuts
2. Use the publish function (publish('filename.m'))

• HTML is the default and is what I typically use
  • It's not very mobile as a stand alone file because it needs local copies of the supporting images
    • I create a PDF using the HTML file for mobility
  • The math images it creates are poor quality (workaround)
• PDF is mobile but sometimes the page breaks can make the formatting look weird
  • The math images are also poor quality
• TeX requires the .tex file to be compiled separately to PDF
  • It DOES have nice-looking math, but no syntax highlighting for code chunks
    • This may be possible with an additional tex package

% is the symbol for commenting on MATLAB code, and plays an important role

To start a new "cell" of markup in a new section (in both document and code)

%% Section Title (optional, will appear in Table of Contents)
% Document text starts here

If we want a new section in the document that is in the same section in the code, triple "%" is used

%%% Section Title (optional, will appear in Table of Contents)
% Document text starts here

I put together a short demo, as that's probably the easiest way to learn how to use Publish

• Source code, html output, PDF output, PDF from HTML, PDF from LateX

The MATLAB page on using Publish is also very useful