Constrained Optimization

Back to Continuous Optimization

Constrained optimization problems consider the problem of optimizing an objective function subject to constraints on the variables. In general terms,
\[ \begin{array}{lllll}
\mbox{minimize} & f(x) & & & \\
\mbox{subject to} & c_i(x) & = & 0 & \forall i \in \mathcal{E} \\
& c_i(x) & \leq & 0 & \forall i \in \mathcal{I}
\end{array}
\]
where \(f\) and the functions \(c_i(x) \,\) are all smooth, real-valued functions on a subset of \(R^n \,\) and \(\mathcal{E}\) and \(\mathcal{I}\) are index sets for equality and inequality constraints, respectively. The feasible set is the set of points \(x\) that satisfy the constraints.

Constrained optimization covers a large number of subfields, including many important special cases for which specialized algorithms are available.

  • Bound Constrained Optimization: the only constraints are lower and upper bounds on the variables
  • Linear Programming: the objective function \(f\) and all of the constraints \(c_i\) are linear functions
  • Quadratic Programming: the objective function \(f\) is quadratic and the constraints \(c_i\) are linear functions
  • Semidefinite Programming: the objective function \(f\) is linear and the feasible set is the intersection of the cone of positive semidefinite matrices with an affine space
  • Nonlinear Programming: at least some of the constraints \(c_i\) are nonlinear functions