Optimization Toolbox 4.3

Quadratic, Binary Integer, and Linear Programming

Quadratic Programming

Quadratic programming problems involve minimizing a multivariate quadratic function subject to linear equality and inequality constraints. The toolbox implements three methods for solving these problems: trust-region, preconditioned conjugate gradient, and active set.

Trust-region is used for bound constrained problems.

Preconditioned conjugate gradient is used for problems subject to equality constraints.

Active set minimizes the objective at each iteration over the active set (a subset of the constraints that are locally active) until it reaches a solution.

Binary Integer Programming

Binary integer programming problems involve minimizing a linear objective function subject to linear equality and inequality constraints. Each variable in the optimal solution must be either a 0 or a 1.

Optimization Toolbox solves these problems using a branch-and-bound algorithm that:

• Searches for a feasible binary integer solution
• Updates the best binary point found as the search tree grows
• Verifies that no better solution is possible by solving a series of linear programming relaxation problems

Linear Programming

Linear programming problems consist of a linear expression for the objective function and linear equality and inequality constraints. Two methods are used to solve this type of problem: simplex and interior point.

The interior point method is based on a primal-dual predictor-corrector algorithm, and is used for large-scale linear problems.

The simplex method is a systematic procedure for generating and testing candidate vertex solutions to a linear program.