Let f,g1,…,gm,h1,…,hp:Rn→Rf,g_1,\ldots,g_m,h_1,\ldots,h_p:\mathbb{R}^n\rightarrow\mathbb{R} be functions. A constrained optimisation problem in standard form is the problem of minimising the objective function ff subject to mm inequality constraints and pp equality constraints.

min⁡x‾∈Rn  f(x‾)subject to  gi(x‾)≤0  ∀ i=1,…,mhj(x‾)=0  ∀ j=1,…,p\begin{align*} \min_{\underline{x}\in\mathbb{R}^n}\,\,&f(\underline{x})\\ \mathrm{subject}\,\mathrm{to}\,\,&g_i(\underline{x})\leq 0\,\,\forall\,i=1,\ldots,m\\ &h_j(\underline{x})=0\,\,\forall\,j=1,\ldots,p \end{align*}

The feasible set is X={x‾∈Rn:gi(x‾)≤0  ∀ i, hj(x‾)=0  ∀ j}X=\left\{\underline{x}\in\mathbb{R}^n:g_i(\underline{x})\leq 0\,\,\forall\,i,\,h_j(\underline{x})=0\,\,\forall\,j\right\} and a point of XX is feasible. A constraint of the form g(x‾)≥0g(\underline{x})\geq 0 or g(x‾)≤bg(\underline{x})\leq b is written in standard form as −g(x‾)≤0-g(\underline{x})\leq 0 or g(x‾)−b≤0.g(\underline{x})-b\leq 0. Let x‾∈X.\underline{x}\in X. The inequality constraint gig_i is active at x‾\underline{x} if and only if gi(x‾)=0g_i(\underline{x})=0 and inactive if and only if gi(x‾)<0.g_i(\underline{x})<0. Equality constraints are active at every feasible point. The active set A(x‾)\mathcal{A}(\underline{x}) is the set of indices of the active constraints at x‾.\underline{x}. The problem is a convex optimisation problem if ff and every gig_i are convex and every hjh_j is affine, since the feasible set is then an intersection of convex sublevel sets and hyperplanes.

The substitution method applies to equality constraints that can be solved explicitly for some of the variables. If the constraints hj(x‾)=0h_j(\underline{x})=0 are equivalent to x‾=φ‾(z‾)\underline{x}=\underline{\varphi}(\underline{z}) for z‾∈Rn−p\underline{z}\in\mathbb{R}^{n-p} then the constrained problem is equivalent to the unconstrained problem of minimising f(φ‾(z‾))f\left(\underline{\varphi}(\underline{z})\right) over z‾.\underline{z}. For example, minimising x12+x22x_1^2+x_2^2 subject to x1+x2=1x_1+x_2=1 becomes minimising x12+(1−x1)2,x_1^2+\left(1-x_1\right)^2, whose stationary point gives x1=x2=12.x_1=x_2=\frac{1}{2}. The method fails when the constraints cannot be solved in closed form.

Consider a problem with equality constraints only and f,hj∈C1.f,h_j\in C^1. The Lagrangian is the objective function plus a weighted sum of the constraint functions,

L(x‾,ν‾):=f(x‾)+∑j=1pνjhj(x‾),\mathcal{L}\left(\underline{x},\underline{\nu}\right):=f(\underline{x})+\sum_{j=1}^p\nu_j h_j(\underline{x}),

where the weights ν1,…,νp∈R\nu_1,\ldots,\nu_p\in\mathbb{R} are the Lagrange multipliers. The method of Lagrange multipliers states that if x‾∗\underline{x}^* is a local minimiser at which the constraint gradients ∇h1(x‾∗),…,∇hp(x‾∗)\nabla h_1(\underline{x}^*),\ldots,\nabla h_p(\underline{x}^*) are linearly independent then there exist multipliers ν‾∗\underline{\nu}^* such that (x‾∗,ν‾∗)\left(\underline{x}^*,\underline{\nu}^*\right) is a stationary point of the Lagrangian.

∇f(x‾∗)+∑j=1pνj∗∇hj(x‾∗)=0‾,hj(x‾∗)=0  ∀ j\nabla f(\underline{x}^*)+\sum_{j=1}^p\nu_j^*\nabla h_j(\underline{x}^*)=\underline{0},\qquad h_j(\underline{x}^*)=0\,\,\forall\,j

The first condition states that the gradient of ff lies in the span of the constraint gradients, so that no direction that keeps the constraints satisfied to first order is a descent direction. The two conditions give n+pn+p equations in the n+pn+p unknowns (x‾,ν‾).\left(\underline{x},\underline{\nu}\right). For example, minimising x12+x22x_1^2+x_2^2 subject to x1+x2=1x_1+x_2=1 gives 2x1+ν=2x2+ν=02x_1+\nu=2x_2+\nu=0 and x1+x2=1,x_1+x_2=1, so x1=x2=12x_1=x_2=\frac{1}{2} and ν=−1.\nu=-1.

Consider the standard form problem with f,gi,hj∈C1.f,g_i,h_j\in C^1. The Lagrangian is

L(x‾,λ‾,ν‾):=f(x‾)+∑i=1mλigi(x‾)+∑j=1pνjhj(x‾)\mathcal{L}\left(\underline{x},\underline{\lambda},\underline{\nu}\right):=f(\underline{x})+\sum_{i=1}^m\lambda_i g_i(\underline{x})+\sum_{j=1}^p\nu_j h_j(\underline{x})

with multipliers λi≥0\lambda_i\geq 0 for the inequality constraints and νj∈R\nu_j\in\mathbb{R} for the equality constraints. The Karush–Kuhn–Tucker (KKT) conditions at a point x‾∗\underline{x}^* with multipliers (λ‾∗,ν‾∗)\left(\underline{\lambda}^*,\underline{\nu}^*\right) are:

  • stationarity: ∇f(x‾∗)+∑i=1mλi∗∇gi(x‾∗)+∑j=1pνj∗∇hj(x‾∗)=0‾;\nabla f(\underline{x}^*)+\sum_{i=1}^m\lambda_i^*\nabla g_i(\underline{x}^*)+\sum_{j=1}^p\nu_j^*\nabla h_j(\underline{x}^*)=\underline{0};
  • primal feasibility: gi(x‾∗)≤0  ∀ ig_i(\underline{x}^*)\leq 0\,\,\forall\,i and hj(x‾∗)=0  ∀ j;h_j(\underline{x}^*)=0\,\,\forall\,j;
  • dual feasibility: λi∗≥0  ∀ i;\lambda_i^*\geq 0\,\,\forall\,i;
  • complementary slackness: λi∗gi(x‾∗)=0  ∀ i.\lambda_i^*g_i(\underline{x}^*)=0\,\,\forall\,i.

Complementary slackness states that an inactive constraint has a zero multiplier and a constraint with a positive multiplier is active, so the KKT conditions reduce to the method of Lagrange multipliers applied to the active constraints. A constraint qualification is a regularity condition on the constraints at x‾∗,\underline{x}^*, such as linear independence of the gradients of the active constraints or Slater’s condition for convex problems, which requires a feasible point at which every inequality constraint is strictly satisfied. If x‾∗\underline{x}^* is a local minimiser at which a constraint qualification holds then there exist multipliers satisfying the KKT conditions, so the conditions are necessary. If the problem is convex then any point satisfying the KKT conditions is a global minimiser, so the conditions are sufficient, and under Slater’s condition they are necessary and sufficient. The multiplier λi∗\lambda_i^* measures the rate at which the optimal value would improve if the constraint gi(x‾)≤0g_i(\underline{x})\leq 0 were relaxed to gi(x‾)≤ε,g_i(\underline{x})\leq\varepsilon, and is called the shadow price of the constraint.

The Lagrange dual function is the infimum of the Lagrangian over x‾\underline{x} for fixed multipliers.

q(λ‾,ν‾):=inf⁡x‾∈RnL(x‾,λ‾,ν‾)q\left(\underline{\lambda},\underline{\nu}\right):=\inf_{\underline{x}\in\mathbb{R}^n}\mathcal{L}\left(\underline{x},\underline{\lambda},\underline{\nu}\right)

The dual function is concave, as a pointwise infimum of affine functions of (λ‾,ν‾),\left(\underline{\lambda},\underline{\nu}\right), whether or not the original problem is convex, and may take the value −∞.-\infty. Let p∗p^* be the optimal value of the standard form problem, which is the primal problem. Weak duality states that the dual function is a lower bound on the optimal value for every λ‾≥0‾,\underline{\lambda}\geq\underline{0}, since for feasible x‾\underline{x} the multiplier terms in the Lagrangian are non-positive.

q(λ‾,ν‾)≤p∗  ∀ λ‾≥0‾, ν‾∈Rpq\left(\underline{\lambda},\underline{\nu}\right)\leq p^*\,\,\forall\,\underline{\lambda}\geq\underline{0},\,\underline{\nu}\in\mathbb{R}^p

The dual problem is the problem of finding the best lower bound,

max⁡λ‾≥0‾, ν‾q(λ‾,ν‾),\max_{\underline{\lambda}\geq\underline{0},\,\underline{\nu}}q\left(\underline{\lambda},\underline{\nu}\right),

which is a convex optimisation problem with optimal value d∗≤p∗.d^*\leq p^*. The duality gap is p∗−d∗≥0.p^*-d^*\geq 0. Strong duality holds when p∗=d∗,p^*=d^*, which is the case for a convex primal problem satisfying Slater’s condition, and then the optimal multipliers of the dual problem are the KKT multipliers of the primal problem. A feasible dual point certifies that no feasible primal point has objective value below q(λ‾,ν‾),q\left(\underline{\lambda},\underline{\nu}\right), which is how iterative methods bound their distance from optimality.

A linear program is a constrained optimisation problem whose objective function and constraint functions are all affine. Let c‾∈Rn,\underline{c}\in\mathbb{R}^n, A∈R m×nA\in\mathbb{R}^{\,m\times n} with rank m≤nm\leq n and b‾∈Rm.\underline{b}\in\mathbb{R}^m. The standard form linear program is

min⁡x‾∈Rn  c‾⊺x‾subject to  Ax‾=b‾x‾≥0‾\begin{align*} \min_{\underline{x}\in\mathbb{R}^n}\,\,&\underline{c}^\intercal\underline{x}\\ \mathrm{subject}\,\mathrm{to}\,\,&A\underline{x}=\underline{b}\\ &\underline{x}\geq\underline{0} \end{align*}

where the inequality holds element-wise. Any linear program can be written in standard form by adding a non-negative slack variable sis_i to convert each inequality constraint a‾i⊺x‾≤bi\underline{a}_i^\intercal\underline{x}\leq b_i into the equality constraint a‾i⊺x‾+si=bi\underline{a}_i^\intercal\underline{x}+s_i=b_i and by writing each unrestricted variable as a difference of two non-negative variables. The feasible set of a linear program is a polyhedron and a linear program is a convex optimisation problem. The dual of the standard form linear program is the linear program

max⁡y‾∈Rmb‾⊺y‾    subject to  A⊺y‾≤c‾\max_{\underline{y}\in\mathbb{R}^m}\underline{b}^\intercal\underline{y}\,\,\,\,\mathrm{subject}\,\mathrm{to}\,\,A^\intercal\underline{y}\leq\underline{c}

and strong duality holds whenever either problem has a feasible point.

A vertex or extreme point of a polyhedron XX is a point of XX that is not a convex combination of two other points of X.X. Let B⊆{1,…,n}B\subseteq\{1,\ldots,n\} be a set of mm indices such that the columns AB∈R m×mA_B\in\mathbb{R}^{\,m\times m} of AA indexed by BB are linearly independent. BB is called a basis of the linear program, the variables indexed by BB are the basic variables and the others are the non-basic variables. The basic solution for BB sets the non-basic variables to zero and solves for the basic variables,

x‾B=AB−1b‾,x‾N=0‾,\underline{x}_B=A_B^{-1}\underline{b},\qquad\underline{x}_N=\underline{0},

and is a basic feasible solution if x‾B≥0‾.\underline{x}_B\geq\underline{0}. The vertices of the feasible set are exactly the basic feasible solutions. The fundamental theorem of linear programming states that if a linear program has a feasible point then it has a basic feasible solution, and if it has an optimal solution then some basic feasible solution is optimal, so the search can be restricted to the finitely many vertices. A linear program whose objective is unbounded below on the feasible set is unbounded and one with an empty feasible set is infeasible.

The simplex method moves from one basic feasible solution to an adjacent one, differing in a single basic variable, so that the objective does not increase, until no improving move exists. Let BB be the current basis with basic feasible solution x‾\underline{x} and let c‾B\underline{c}_B be the objective coefficients of the basic variables. The reduced cost of the non-basic variable jj is the rate of change of the objective when xjx_j is increased from zero and the basic variables adjust to keep Ax‾=b‾.A\underline{x}=\underline{b}.

cˉj:=cj−c‾B⊺AB−1a‾j\bar{c}_j:=c_j-\underline{c}_B^\intercal A_B^{-1}\underline{a}_j

The current basic feasible solution is optimal if cˉj≥0\bar{c}_j\geq 0 for every non-basic j.j. Otherwise a non-basic variable with negative reduced cost is chosen as the entering variable and increased until some basic variable reaches zero, which is identified by the minimum ratio test over the components of d‾=AB−1a‾j\underline{d}=A_B^{-1}\underline{a}_j with di>0,d_i>0,

α=min⁡i: di>0xBidi,\alpha=\min_{i:\,d_i>0}\frac{x_{B_i}}{d_i},

and that variable is the leaving variable that is swapped out of the basis. If no di>0d_i>0 exists the linear program is unbounded. An initial basic feasible solution is found by solving an auxiliary linear program with artificial variables in a first phase. With a rule that prevents the same basis from recurring the simplex method terminates in finitely many iterations. Its worst case visits exponentially many vertices, but in practice it typically takes a number of iterations proportional to m.m.

Interior point methods approach a minimiser through the interior of the feasible set rather than along its boundary. Consider a convex problem in standard form with f,gi∈C2f,g_i\in C^2 and a feasible point satisfying Slater’s condition. The logarithmic barrier function is finite on the strictly feasible points and grows without bound as any inequality constraint becomes active.

ϕ(x‾):=−∑i=1mlog⁡e(−gi(x‾))\phi(\underline{x}):=-\sum_{i=1}^m\log_e\left(-g_i(\underline{x})\right)

Let t>0.t>0. The barrier problem replaces the inequality constraints by adding the barrier function to the objective,

min⁡x‾  f(x‾)+1tϕ(x‾)    subject to  hj(x‾)=0  ∀ j,\min_{\underline{x}}\,\,f(\underline{x})+\frac{1}{t}\phi(\underline{x})\,\,\,\,\mathrm{subject}\,\mathrm{to}\,\,h_j(\underline{x})=0\,\,\forall\,j,

and has a unique minimiser x‾∗(t)\underline{x}^*(t) when the objective is strictly convex. The set of minimisers {x‾∗(t):t>0}\left\{\underline{x}^*(t):t>0\right\} is the central path, and x‾∗(t)\underline{x}^*(t) is feasible for the original problem with multipliers λi=−1t gi(x‾∗(t))\lambda_i=-\frac{1}{t\,g_i\left(\underline{x}^*(t)\right)} that are dual feasible, so by weak duality

f(x‾∗(t))−p∗≤mt.f\left(\underline{x}^*(t)\right)-p^*\leq\frac{m}{t}.

The barrier method solves the barrier problem by Newton’s method for an increasing sequence of values of t,t, typically t←μtt\leftarrow\mu t with μ>1,\mu>1, starting each solve from the previous minimiser, until mt\frac{m}{t} is below the required accuracy. Primal-dual interior point methods instead apply Newton’s method to the KKT conditions with complementary slackness perturbed to −λigi(x‾)=1t,-\lambda_i g_i(\underline{x})=\frac{1}{t}, updating the primal variables and multipliers together, and are the most widely used variant. For linear programs the number of Newton iterations needed to reach accuracy ε\varepsilon grows as mlog⁡e1ε,\sqrt{m}\log_e\frac{1}{\varepsilon}, so interior point methods run in polynomial time where the simplex method does not.