Mathematical programs

Linear programs

Linear programming (LP) involves solving problems of the form

minimize	cT x
subject to	Ax≤b

and in practice this encompasses, via transformations, any problem whose objective and constraints are linear functions. Such problems were traditionally solved with the simplex method, although recently interior point methods have come to be favoured for larger instances. Linear programs can be solved quickly, and solution techniques scale to enormous sizes of the matrix A. However, few applications are genuinely linear. It was common in the past, however, to approximate general functions by linear counterparts when LPs were the only class of problem with efficient solution techniques.

Convex quadratic programs

Convex quadratic programming (QP) involves solving problems of the form

minimize	cT x + xT Q x
subject to	Ax≤b

for which the matrix Q is symmetric and positive semi-definite (that is, x^T Q x ≥ 0 for all x). This encompasses, via transformations, all problems with a positive semi-definite Q and linear constraints. Such problems can be solved efficiently by interior point methods, and also by quadratic variants of the simplex method.

Convex quadratically constrained quadratic programs

Convex quadratically constrained quadratic programming (QCQP) involves solving problems of the form

minimize	cT x + xT Q x
subject to	Ax≤b
	qjTx + xT Pj x ≤ dj, ∀j

for which the matrix Q and all matrices P_j are positive semi-definite. The most efficient solution techniques are based on interior point methods.

Second order conic problems

Second order conic problems is a special form of a convex quadratically constrained quadratic program, where although the quadratic matrix is not positive semi-definite, the feasible range of the problem is convex, and there are specialized algorithm to solve them.

minimize	cT x + xT Q x
subject to	Ax≤b
	x is in Cj, ∀j

for which the matrix C_j is a convex second order cone and Q is positive semi-definite. The standard form of a second order cone is x^TI x≤y*y where y is non-negative, or (a rotated second order cone) x^TI x≤y*z where y and z are non-negative. Many quadratic problems can be formulated as a second order convex conic problem, including any convex quadratically constrained quadratic programs. Transformation happens automatically for most convertible problems.

General nonlinear optimization problems

Nonlinear programming (NLP) involves solving problems of the form

minimize	f(x)
subject to	gj(x)≤b, ∀j

where f(x) is an arbitrary function, and g(x) are a set of arbitrary functions. This is the most general type of problem, and any constrained model can be realised in this form via simple transformations. Until recently, few practical techniques existed for tackling such problems, but it is now possible to solve even large instances using Successive Linear Programming solvers (SLP) or second-order methods.

Mixed integer programs

Mixed-integer programming (MIP), in the most general case, involves solving problems of the form

minimize	f(x)
subject to	gj(x)≤b, ∀j
	xk integral

It can be combined with any of the previous problem types, giving Mixed-Integer Linear Programming (MILP), Mixed-Integer Quadratic Programming (MIQP), Mixed-Integer Quadratically Constrained Quadratic Programming (MIQCQP), Mixed-Integer Second Order Conic Problems (MISOCP) and Mixed-Integer Nonlinear Programming (MINLP). Efficient solution techniques now exist for all of these classes of problem.