Optimization in MATLAB: Video Tutorial

This video tutorial reviews optimization and shows how to implement it in MATLAB. It is part of the Numerical Computations course.

Optimization problems in MATLAB

An optimization problem asks for values of the decision variables $x$ that improve an objective function $f(x)$, subject to constraints. The solvers used in this tutorial minimize. To maximize a function with these solvers, minimize its negative and change the sign of the returned objective value.

The three videos follow the type of the objective and the constraints:

• Linear programming (LP): a linear objective with linear constraints, solved with linprog. If some variables must be integers, the problem is a mixed integer linear program (MILP), solved with intlinprog.
• Quadratic programming (QP): a quadratic objective with linear constraints, solved with quadprog.
• Nonlinear optimization: a general objective, with or without constraints, solved with fminbnd, fminsearch, fminunc or fmincon.

linprog, intlinprog, quadprog, fminunc and fmincon are part of Optimization Toolbox. fminbnd and fminsearch are in core MATLAB.

Watch online

The three sections of this tutorial are on YouTube and are embedded here as a playlist.

Play playlistLoads from YouTube

What each video covers

Section 1: Linear programming and mixed integer LP

Linear Programming and Mixed-Integer LP (YouTube (opens in a new tab)). MATLAB writes a linear program in this standard form:

So a model is defined by seven matrices and vectors: f, A, b, Aeq, beq, lb and ub. Missing parts are passed as empty matrices [].

The video solves three examples:

1. Minimize $2x_1 - 5x_2$ with $100 \le x_1 \le 200$, $50 \le x_2 \le 150$ and $x_1 + x_2 \le 210$. The bounds go into lb and ub, and linprog returns an objective value of $-350$.
2. Maximize $x_1 + x_2/3$ subject to six linear inequalities. The objective is negated, and each “greater than or equal” constraint is multiplied by $-1$ to fit the form $Ax \le b$. The solution is $x = (2/3, 4/3)$ with a maximum of about $1.111$. The video then adds integer constraints with intlinprog, whose second input intcon lists the integer variables. With $x_1$ an integer the solution is $(1, 0)$, and with $x_2$ an integer it is $(0.75, 1)$.
3. Minimize $5x_1 - 2x_2$ subject to $x_1 - 3x_2 \ge -14$, $4x_1 - x_2 \ge 33$, $x_1 - 2x_2 \le 25$ and $x \ge 0$. The LP solution is about $(10.27, 8.09)$. With $x_2$ an integer, intlinprog returns $(10.25, 8)$.

f = [5; -2];
A = [-1 3; -4 1; 1 -2];
b = [14; -33; 25];
lb = [0; 0];
x = intlinprog(f, 2, A, b, [], [], lb)

For a longer treatment of linprog, with the transportation problem as the example, see the Linear Programming in MATLAB video tutorial.

Section 2: Quadratic programming

Quadratic Programming (YouTube (opens in a new tab)). A quadratic program adds a quadratic term to the LP form:

The video notes that training a support vector machine leads to a QP. Its example is

The main step is to find $H$. The objective is written as $\tfrac{1}{2}(x_1^2 + 2x_2^2 - 2x_1x_2)$, and the cross term is split equally between the two off-diagonal elements, because a symmetric $H$ is preferred:

H = [1 -1; -1 2];
f = [-2; -6];
A = [1 1; 2 1];
b = [2; 5];
[x, fval] = quadprog(H, f, A, b)

The solution is $x = (0.4, 1.6)$ with an objective value of $-8.4$.

Section 3: Constrained and unconstrained nonlinear optimization

Constrained and Unconstrained Nonlinear Optimization (YouTube (opens in a new tab)). The video compares four functions:

• fminbnd: one variable, searched within an interval.
• fminsearch: several variables, no constraints. It searches without requiring derivatives, and the video uses it for a small problem. This does not guarantee reliable behavior for discontinuous functions or large problems.
• fminunc: several variables, no constraints. The video uses it for smooth objectives, for which derivative information is useful.
• fmincon: several variables with constraints.

The first example is $f(x) = x^3 - 5x + 1$. fminbnd on $[-1, 5]$ finds the local minimum at about $1.29$, and fminsearch and fminunc started from 2 find the same point. The video also turns root finding into optimization: minimizing $|f(x)|$ with fminbnd on different intervals finds each of the three roots, which roots([1 0 -5 1]) confirms.

The second example is the Rosenbrock function

whose minimum is at $(1, 1)$. Both fminsearch and fminunc, started from $(0, 0)$, find it.

The last example is a constrained design problem: a box with sides $x_1$, $x_2$ and $x_3$ should have the largest volume, while its surface area is at most 150:

The nonlinear constraint goes into a function that returns c (inequalities, $c(x) \le 0$) and ceq (equalities, empty here). Since fmincon minimizes, the objective is the negative volume. Started from $(1, 1, 1)$, the solution is a cube with all sides equal. Adding the constraint $2x_2 \le x_3$ gives a box that is no longer a cube, and the volume drops to about 117. The video adds this constraint to c, and notes that a linear constraint can also go into A and b.

Applications

• Planning and allocation problems with linear models, such as production planning and transportation.
• Problems with yes or no decisions or whole units, modeled with integer variables.
• Machine learning models such as support vector machines (quadratic programming).
• Engineering design, such as the box example, where the objective and constraints are nonlinear.

Check feasibility and optimality

Substitute the result into every constraint and evaluate the original objective, especially after negating a maximization problem. Inspect the solver’s termination information before accepting a result. A local solution of a nonlinear problem need not be the global best, so compare starting points when the model has several basins. Keep integer decisions in an integer model rather than rounding a continuous solution, which can break the constraints.