Optimization (D2) DPK

Easter 2005

1. LAGRANGIAN METHODS

1.1 Constrained optimization

The general problem of optimization under constraints that we will consider in this course may be expressed as

P : minimize f(x) subject to g(x) = b, x ∈ X

where

(i) f : ℝ^{n} → ℝ is known as the objective function of the problem and the components of its argument x = (x_{1}, … x_{n})^{⊤} are the variables to be chosen to optimize the objective function subject to the constraints;

(ii) X ⊆ ℝ^{n} is the constraint region; (iii) g : ℝ^{n} → ℝ^{m} defines m functional constraints; and (iv) b = (b_{1}, …, b_{m})^{⊤} is a fixed element of ℝ^{m}, sometimes known, prosaically, as the

right-hand side of the constraints. The convention throughout will be that all vectors are column vectors. While we will

formulate the general problem as a minimization one may move between maximization and minimization problems by observing that maximizing f is equivalent to minimizing −f. The region X, which is a subset of ℝ^{n}, is usually a set such as the non-negative orthant X = {x : x ⩾ 0}, and in some problems the functional constraints may take the form of inequalities g(x) ⩽ b; these inequality constraints may be turned into equality constraints by the addition of non-negative slack variables z = (z_{1}, …, z_{m})^{⊤} to give

g(x) + z = b, z ⩾ 0.

It can be seen from this that there may be a degree of arbitrariness in how the constraints on x are divided between functional constraints and the constraint region but it is usually clear from the context of the problem how each should be formulated.

The set X_{b} = {x : x ∈ X, g(x) = b} is known as the set of feasible solutions of the problem P, so the constrained problem is to find a feasible x^{∗} ∈ X_{b} that minimizes the function f over X_{b}, that is, f(x^{∗}) ⩽ f(x) for all x ∈ X_{b}; such a x^{∗} is said to be optimal for the problem P. Techniques of unconstrained optimization are usually straightforward, to minimize f the first step would be to set the gradient of f equal to zero; when the problem is constrained such an approach may not be immediately helpful as the optimum will not necessarily occur when the gradient of f is zero. For example, consider the case when f(x) = x^{2} and X = {x : x ⩾ 2}; the minimum trivially occurs when x = 2 but f′(2) ≠ 0. The Lagrangian approach is a powerful method which enables many constrained problems to be turned into unconstrained optimization problems which can then be tackled by conventional means.

1.2 The Lagrangian Sufficiency Theorem

The Lagrangian for the problem P is defined to be the function

L (x, λ) = f(x) + λ^{⊤} (b − g(x))

where λ ∈ ℝ^{m}; here, L : ℝ^{n} × ℝ^{m} → ℝ and the components of λ = (λ_{1}, …, λ_{m})^{⊤} are known as the Lagrange multipliers of the problem. The following very simple result is central to the Lagrangian technique.

Theorem 1.1 (Lagrangian Sufficiency Theorem) Suppose that there exist x^{∗} and λ^{∗} such that

L(x^{∗}, λ^{∗}) ⩽ L(x, λ^{∗}) for all x ∈ X,

and x^{∗} is feasible for P, then x^{∗} is optimal for P.

Proof. For any x ∈ X_{b},

L(x, λ) = f(x) + λ^{⊤} (b − g(x)) = f(x),

which shows that

f(x^{∗}) = L(x^{∗}, λ^{∗}) ⩽ L(x, λ^{∗}), for all x ∈ X;

2 but L(x, λ^{∗}) = f(x) for x ∈ X_{b} and hence f(x^{∗}) ⩽ f(x) for all x ∈ X_{b}, which is the result. □

The Lagrangian Sufficiency Theorem leads to the following procedure which may be used to solve a wide class of constrained optimization problems. Lagrangian Method for Constrained Optimization

1. For each λ for which inf_{x∈X} L(x, λ) > −∞, choose x^{∗}(λ) ∈ X so that

L (x^{∗}(λ), λ) = inf_{x∈X} L (x, λ) .

That is, for each λ, we minimize L(x, λ) over x in X, unconstrained by the functional constraints g(x) = b, to get the minimizing x^{∗}(λ). We may exclude any λ for which inf_{x∈X} L(x, λ) = −∞ for such λ cannot satisfy the conditions of Theorem 1.1.

2. Now choose λ = λ^{∗} so that x^{∗} = x^{∗}(λ^{∗}) ∈ X_{b} (in other words, to satisfy g (x^{∗}(λ^{∗})) = b so that x^{∗} is feasible for the problem P); then x^{∗}, λ^{∗} satisfy the conditions of Theorem 1.1 and hence x^{∗} is optimal for P.

Example 1.2 Use of the Lagrangian Method Consider the problem

minimize 2 ln (1/x_{1}) + 3 ln (1/x_{2}) + ln (1/x_{3})
subject to 3x_{1} + 2x_{2} + x_{3} = 1, x_{1} > 0, x_{2} > 0, x_{3} > 0.

The Lagrangian is

L(x, λ) = 2 ln (1/x_{1}) + 3 ln (1/x_{2}) + ln (1/x_{3}) + λ(1 − 3x_{1} − 2x_{2} − x_{3}),

which we have to minimize over the variables x_{1} > 0, x_{2} > 0 and x_{3} > 0. We set the first derivatives of L with respect to each of these to zero to get

\frac{∂L}{∂x_{1}} = −\frac{2}{x_{1}} − 3λ = 0

\frac{∂L}{∂x_{2}} = −\frac{3}{x_{2}} − 2λ = 0

\frac{∂L}{∂x_{3}} = −\frac{1}{x_{3}} − λ = 0,

which give x_{1}^{∗}(λ) = −2/(3λ), x_{2}^{∗}(λ) = −3/(2λ), x_{3}^{∗}(λ) = −1/λ; we need to ensure that this turning point of L(x, λ) is a minimum, so consider the Hessian matrix of L (the matrix of second derivatives)

H_{L} = (\frac{∂^{2}L}{∂x_{i}∂x_{j}} )_{ij} = ( \begin{matrix}2/x_{1}^{2} & 0 & 0 \\ 0 & 3/x_{2}^{2} & 0 \\ 0 & 0 & 1/x_{3}^{2} \end{matrix} )

which shows that these values give a minimum. Substitute x_{i}^{∗}(λ), i = 1, 2, 3, into the constraint 3x_{1} + 2x_{2} + x_{3} = 1

3 (−\frac{2}{3λ}) + 2 (−\frac{3}{2λ}) − \frac{1}{λ} = 1,

to determine the value of λ which makes these feasible for the problem and we obtain λ = −6, to give the optimal solution as x_{1}^{∗} = 1/9, x_{2}^{∗} = 1/4 and x_{3}^{∗} = 1/6. □

1.3 Inequality constraints and complementary slackness

When the functional constraints in the problem P are in inequality form so that the problem becomes

P : minimize f(x) subject to g(x) ⩽ b, x ∈ X

it may be expressed in the previous form with equality constraints using slack variables as

minimize f(x) subject to g(x) + z = b, x ∈ X and z ⩾ 0.

The Lagrangian now becomes

L (x, z, λ) = f(x) + λ^{⊤} (b − g(x) − z)

and it must be minimized over x ∈ X and z ⩾ 0. When minimizing over the slack variables z = (z_{1}, …, z_{m})^{⊤} ⩾ 0, one must be careful not to set ∂L/∂z_{i} = 0, and then conclude that λ_{i} = 0, since the optimum may occur at the boundary of the region z_{i} ⩾ 0, viz. at z_{i} = 0 when ∂L/∂z_{i} is not necessarily zero.

Consider the term in the Lagrangian involving z_{i}, viz. −λ_{i}z_{i}; if λ_{i} > 0 then letting z_{i} become arbitrarily large shows that this term can be made to approach −∞ which

4 implies that inf_{x∈X,z⩾0} L(x, z, λ) = −∞. Thus, for a finite minimum of the Lagrangian we require that λ_{i} ⩽ 0, in which case the minimum of the term −λ_{i}z_{i} is 0, since we could take z_{i} = 0. Thus, with inequality constraints in the problem, minimizing the Lagrangian always leads to sign conditions on the Lagrange multipliers, in this case λ ⩽ 0, and also a joint condition on the Lagrange multipliers and the slack variables in that

λ_{i}z_{i} = 0 for each i = 1, …, m, or equivalently, λ^{⊤}z = 0.

This condition is known as a complementary slackness condition; at least one of the variables λ_{i} and z_{i} must be zero (at the optimum solution) for each i.

To understand what the complementary slackness condition is saying about the optimal solution to the constrained optimization problem, notice that, at the optimum,

(i) if z_{i} > 0 then necessarily λ_{i} = 0; and

(ii) if λ_{i} < 0 then necessarily z_{i} = 0.

The statement (i) is saying that if at the optimum the ith constraint is not tight, that is, g_{i}(x) < b_{i}, then the Lagrange multiplier λ_{i} for that constraint must be zero, so that the term involving the ith constraint is not required in the Lagrangian. Alternatively, (ii) says that if λ_{i} is not zero, so the term in the Lagrangian for the ith constraint is required, then necessarily z_{i} = 0 so the ith constraint is tight at the optimum.

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. •  g_{1}(x) = b_{1} g_{2}(x) = b_{2} λ_{1} = 0 λ_{2} < 0 Optimum .............................................. .............. Feasible set ................................. ..............^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

Sometimes when the optimum to the problem falls on one constraint but inside another (as illustrated in the diagram above and the Example below) the cases λ_{i} = 0 and λ_{i} < 0 may need to be considered separately for each constraint.

Example 1.3 Complementary slackness

Consider the problem

minimize x_{1} − 3x_{2}
subject to x_{1}^{2} + x_{2}^{2} ⩽ 4
x_{1} + x_{2} ⩽ 2.

Adding slack variables the problem becomes

minimize x_{1} − 3x_{2}
subject to x_{1}^{2} + x_{2}^{2} + z_{1} = 4
x_{1} + x_{2} + z_{2} = 2, z_{1} ⩾ 0, z_{2} ⩾ 0.

It is easy to see (by drawing a picture) where the optimum for this problem occurs, but we will use it as an illustration of the methods of this section. The Lagrangian for the problem is

L = x_{1} − 3x_{2} + λ_{1} (4 − x_{1}^{2} − x_{2}^{2} − z_{1}) + λ_{2} (2 − x_{1} − x_{2} − z_{2}) ,

which must be minimized over x_{1}, x_{2} ∈ ℝ and z_{1}, z_{2} ⩾ 0. Minimizing over z_{1} ⩾ 0 and z_{2} ⩾ 0, the arguments above show that for a finite minimum we must have λ_{1} ⩽ 0, λ_{2} ⩽ 0 and at the optimum the complementary slackness conditions λ_{1}z_{1} = 0 and λ_{2}z_{2} = 0 must hold. Minimizing L in x_{1} and x_{2}, we have

\begin{matrix}\frac{∂L}{∂x_{1}} = 1 − 2λ_{1}x_{1} − λ_{2} = 0 \\ \frac{∂L}{∂x_{2}} = −3 − 2λ_{1}x_{2} − λ_{2} = 0, \end{matrix}

which will give a minimum because the Hessian matrix

H_{L} = ( \begin{matrix}−2λ_{1} & 0 \\ 0 & −2λ_{1} \end{matrix} ) ,

is non-negative definite since we have λ_{1} ⩽ 0. Notice that we cannot have λ_{1} = 0, since it would give inconsistent values λ_{2} = 1 and λ_{2} = −3. Suppose that λ_{1} < 0, so necessarily z_{1} = 0, and

x_{1} = \frac{1 − λ_{2}}{2λ_{1}} , x_{2} = −\frac{3 + λ_{2}}{2λ_{1}} ;

6 if we further assume that λ_{2} < 0 so that z_{2} = 0 and substitute into the two constraints to get λ_{1} and λ_{2} we obtain

\begin{aligned}(\frac{1 − λ_{2}}{2λ_{1}} )^{2} + (\frac{3 + λ_{2}}{2λ_{1}} )^{2} & = 4 \\ (\frac{1 − λ_{2}}{2λ_{1}} ) − (\frac{3 + λ_{2}}{2λ_{1}} ) & = 2. \end{aligned}

From the second equation we have λ_{2} = −1 − 2λ_{1} and substituting into the first equation gives

(\frac{1 + λ_{1}}{λ_{1}} )^{2} + (\frac{1 − λ_{1}}{λ_{1}} )^{2} = 4,

which reduces to λ_{1}^{2} = 1 or λ_{1} = ±1. Since necessarily λ_{1} < 0, we must take the case λ_{1} = −1 giving λ_{2} = 1 > 0 which is not allowed. Lastly consider the case λ_{1} < 0 and λ_{2} = 0; substitute into the constraint x_{1}^{2} + x_{2}^{2} = 4, which is tight because z_{1} = 0, to get

(\frac{1}{2λ_{1}} )^{2} + (\frac{3}{2λ_{1}} )^{2} = 4,

and solve to obtain λ_{1} = −\sqrt{10}/4. Thus the optimal values for the problem (and the Lagrange multipliers for the Lagrangian Sufficiency Theorem) are

x_{1}^{∗} = −\sqrt{2/5}, x_{2}^{∗} = 3\sqrt{2/5}, λ_{1}^{∗} = −\sqrt{10}/4, λ_{2}^{∗} = 0.

You should draw a picture to see that the optimum lies on the first constraint and ‘inside’ the second. □

1.4 Shadow prices

The most important approach to understanding the role of Lagrange multipliers in the solution of optimization problems is to regard the problem

P : minimize f(x) subject to g(x) = b, x ∈ X

as one of a family of problems indexed by the right-hand side in the constraints, b. To this end let ϕ(b) be the minimum value of the objective function f subject to the constraints in P, so that ϕ(b) = inf {f(x) : x ∈ X, g(x) = b}. With this notation then there is an important relation between the Lagrange multipliers for the problem and ϕ in that

λ_{i}^{∗} = \frac{∂ϕ}{∂b_{i}} , i = 1, …, m.

It should be noted that this relation is also true if the functional constraints in P are formulated as inequality constraints, g(x) ⩽ b, and ϕ(b) = inf {f(x) : x ∈ X, g(x) ⩽ b}. We illustrate by considering a generalization of the problem in Example 1.3.

Example 1.4 Consider the problem

minimize x_{1} − 3x_{2}
subject to x_{1}^{2} + x_{2}^{2} ⩽ b_{1}
x_{1} + x_{2} ⩽ b_{2},

where here b_{1} and b_{2} are positive constants, which we will assume satisfy b_{2}^{2} > \frac{2}{5}b_{1} (see below). We may add slack variables and carry through the same arguments as before to rule out both λ_{1} < 0 and λ_{2} < 0; we would need

(\frac{1 − λ_{2}}{2λ_{1}} )^{2} + (\frac{3 + λ_{2}}{2λ_{1}} )^{2} = b_{1} and (\frac{1 − λ_{2}}{2λ_{1}} ) − (\frac{3 + λ_{2}}{2λ_{1}} ) = b_{2}.

From the second equation we have λ_{2} = −1 − b_{2}λ_{1} and substituting into the first equation gives

(\frac{2 + b_{2}λ_{1}}{2λ_{1}} )^{2} + (\frac{2 − b_{2}λ_{1}}{2λ_{1}} )^{2} = b_{1},

which reduces to λ_{1} = −2/\sqrt{2b_{1} − b_{2}^{2}}; if 2b_{1} ⩽ b_{2}^{2} it is clear that there can be no solution with both λ_{1} < 0 and λ_{2} < 0 while if 2b_{1} > b_{2}^{2} then take λ_{2} = −1 + 2b_{2}/\sqrt{2b_{1} − b_{2}^{2}} which gives λ_{2} > 0 if 5b_{2}^{2} > 2b_{1}. As before, we must have the case λ_{1} < 0 and λ_{2} = 0; substitute into the constraint x_{1}^{2} + x_{2}^{2} = b_{1} to get

(\frac{1}{2λ_{1}} )^{2} + (\frac{3}{2λ_{1}} )^{2} = b_{1},

from which we deduce that the optimal values for the problem are

x_{1}^{∗} = −\sqrt{b_{1}/10}, x_{2}^{∗} = 3\sqrt{b_{1}/10}, λ_{1}^{∗} = −\sqrt{10/(4b_{1})}, λ_{2}^{∗} = 0.

8 We then have ϕ(b) = x_{1}^{∗} − 3x_{2}^{∗} = −\sqrt{10b_{1}} from which we can confirm that

\frac{∂ϕ}{∂b_{1}} = −\sqrt{10/(4b_{1})} = λ_{1}^{∗}, and \frac{∂ϕ}{∂b_{2}} = 0 = λ_{2}^{∗}.

You should think about what happens when b_{2}^{2} < \frac{2}{5}b_{1}; compute ϕ(b) and confirm that λ_{i}^{∗} = ∂ϕ/∂b_{i} in this case. □

Because of the relationship λ_{i}^{∗} = ∂ϕ/∂b_{i} the Lagrange multipliers are often known as shadow prices for the problem. The terminology makes most intuitive sense if we formulate the problem as a maximization as

P′ : maximize f(x) subject to g(x) ⩽ b, x ∈ X

and we think of some company with production processes i = 1, …, n which are operated at levels x_{i} to give a total profit f(x). There are m different raw materials, j = 1, …, m such that if the production processes are at levels x = (x_{1}, …, x_{n})^{⊤} then an amount g_{j}(x) of raw material j is consumed where the available supplies are b_{j}, 1 ⩽ j ⩽ m. The fact that we require x ∈ X may represent some technological constraints (incidental to the consumption of raw materials). Then the problem is one of choosing the production levels with the aim of maximizing the profit subject to using no more than the available supply of the raw materials. Then ϕ(b) = sup {f(x) : x ∈ X, g(x) ⩽ b} is the maximal profit.

If one considers now how much the company should be prepared to pay to secure Δb_{j} extra units of raw material j, then one can see that the marginal price, p_{j}, that it would be prepared to pay should be given by

p_{j}Δb_{j} = \frac{∂ϕ}{∂b_{j}} Δb_{j} or p_{j} = \frac{∂ϕ}{∂b_{j}} = λ_{j}^{∗}.

1.5 The dual problem

A further important idea coming from the Lagrangian approach to constrained optimization is the notion of a related optimization problem, known as the dual problem, to the original problem

P : minimize f(x) subject to g(x) = b, x ∈ X,

known as the primal problem. In a large class of cases the solutions to the primal and dual problems are very closely related and studying the dual problem gives insight into the solution of the primal problem and vice-versa. To formulate the dual, let

Λ = {λ : inf_{x∈X} L(x, λ) > −∞}

be the set of Lagrange multipliers for which the minimum of the Lagrangian for P is finite. For each λ ∈ Λ let h(λ) = inf_{x∈X} L(x, λ). The dual problem is

D : maximize h(λ) subject to λ ∈ Λ.

The function h is the objective function for the dual problem and the set Λ is the set of feasible solutions to the dual. We let

ψ(b) = sup {h(λ) : λ ∈ Λ} ,

represent the optimal value of the dual problem. An important relation between the two problems is contained in the following simple result. Theorem 1.5 Weak duality If x is any feasible solution for the primal problem P and λ is any feasible solution for the dual problem D then

h(λ) ⩽ f(x).

In particular, it follows that ψ(b) ⩽ ϕ(b).

Proof. For any feasible x, g(x) = b which implies that L(x, λ) = f(x), and so

h(λ) = inf_{x′∈X} L(x′, λ) ⩽ L(x, λ) = f(x);

maximizing over the left-hand side and minimizing over the right-hand side shows that ψ(b) ⩽ ϕ(b). □

Example 1.6 The dual problem

Consider the problem of Example 1.2 but with a general right-hand side b > 0,

minimize 2 ln (1/x_{1}) + 3 ln (1/x_{2}) + ln (1/x_{3})
subject to 3x_{1} + 2x_{2} + x_{3} = b, x_{1} > 0, x_{2} > 0, x_{3} > 0.

10 The Lagrangian is now

L (x, λ) = 2 ln (1/x_{1}) + 3 ln (1/x_{2}) + ln (1/x_{3}) + λ(b − 3x_{1} − 2x_{2} − x_{3}),

which is minimized, as before, at x_{1}^{∗}(λ) = −2/(3λ), x_{2}^{∗}(λ) = −3/(2λ), x_{3}^{∗}(λ) = −1/λ (and the choice of λ to make these feasible for the problem is λ^{∗} = −6/b); note that Λ = {λ : λ < 0}, and substituting these values gives

h(λ) = inf_{x_{i}>0} L(x, λ) = λb + 6 ln(−λ) + 2 ln(3/2) + 3 ln(2/3) + 6.

The dual problem is to maximize h(λ) in λ < 0; we see that the maximizing value is λ^{∗} = −6/b and we can verify that in this case ϕ(b) = ψ(b). □

Remarks

1. The weak duality result shows that the value of the objective function at a feasible solution for the dual problem provides a lower bound for the objective function for the primal problem at any feasible solution for the primal problem; the largest such lower bound is the value of the dual problem.

2. The conclusion in this example, that the maximum value of the dual problem equals the minimum value of the primal problem, is true for any problem that can be solved using the Lagrangian method, that is for any problem for which there exists a λ^{∗} for which

inf_{x∈X} L(x, λ^{∗}) = inf_{x∈X_{b}} L(x, λ^{∗}) = inf_{x∈X_{b}} f(x),

where these terms are > −∞; the general proof of this fact, which is known as strong duality, is beyond the scope of this course, but we will exploit it later for a particular class of problems, viz. linear programming.

3. The primal problem here is formulated as a minimization; if the primal problem is formulated as a maximization, then the dual objective function is obtained by maximizing the Lagrangian and the dual problem involves a minimization.

4. To get a feel for why the maximization and minimization are interchanged when going between the primal and dual problems, note that if we maximize the Lagrangian in the Lagrange multipliers we get, for x ∈ X,

sup_{λ} L(x, λ) = sup_{λ} [f(x) + λ^{⊤} (b − g(x)] = \{ \begin{matrix}f(x) & if g(x) = b, \\ ∞ & otherwise; \end{matrix}

this is because the Lagrange multipliers here can be either sign so that if any entry of b − g(x) is non-zero the corresponding entry of λ can be taken large (either positive or negative) to get ∞ as the supremum. Thus the primal and dual problems are

Primal: min_{x∈X} [max_{λ} L(x, λ)] Dual: max_{λ} [min_{x∈X} L(x, λ)] ,

and when the primal and dual problems have the same value it is the same as the statement that min_{x∈X} max_{λ} L = max_{λ} min_{x∈X} L.

1.6 Lagrangian necessity

One may ask under what circumstances will the problem

P : minimize f(x) subject to g(x) = b, x ∈ X

(or its inequality version) be such that it can be guaranteed to be solved using the Lagrangian approach; that is, there will exist a λ^{∗} satisfying the condition in Remark 2 of the previous section.

Consider the region {(g(x), f(x)) : x ∈ X} in ℝ^{m} × ℝ, illustrated in the diagram. The function ϕ(·) is the lower boundary of that region, and whether or not the problem P can be solved by minimizing the Lagrangian for appropriate Lagrange multipliers depends on whether or not the function ϕ has a tangent plane, at the point b, which lies entirely below the function (known as a supporting hyperplane).

Theorem 1.7 For the problem P, there exist Lagrange multipliers λ^{∗} satisfying

inf_{x∈X} L(x, λ^{∗}) = inf_{x∈X_{b}} L(x, λ^{∗})

12

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{•}  ^{ϕ(c)} b  ^{ϕ(b) + (λ^{∗})^{⊤}(c − b)}^{•}^{(g(x), f(x))}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} _{c (∈ ℝ^{m})} ℝ^{ϕ(b)}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

if and only if at the point b the function ϕ has a supporting hyperplane with slope λ^{∗}; i.e.,

ϕ(c) ⩾ ϕ(b) + (λ^{∗})^{⊤} (c − b) for all c.

Proof. The condition (in the statement of the Theorem and in Remark 2) is equivalent to

ϕ(b) = inf_{x∈X} L(x, λ^{∗}) = inf_{x∈X} [f(x) + (λ^{∗})^{⊤}(b − g(x)]

= inf_{c} inf_{x∈X_{c}} [f(x) + (λ^{∗})^{⊤}(b − g(x)]

= inf_{c} [ϕ(c) + (λ^{∗})^{⊤}(b − c));

it is immediate that this is equivalent to ϕ(b) + (λ^{∗})^{⊤}(c − b) ⩽ ϕ(c) for all c. □

Remarks

1. There remains the question of how one can tell from properties of the functions f and g and of the set X whether or not the function ϕ has a supporting hyperplane at the relevant point. If ϕ has a supporting hyperplane at every point then necessarily it is a convex function. Recall that a function f : ℝ^{n} → ℝ is convex if for all x, y ∈ ℝ^{n} and θ, 0 ⩽ θ ⩽ 1,

f (θx + (1 − θ)y) ⩽ θf(x) + (1 − θ)f(y);

this is equivalent to requiring that the region {(y, f(x)) : y ⩾ f(x), x ∈ ℝ^{n}} lying above the function f is a convex set in ℝ × ℝ^{n}. A function f : ℝ^{n} → ℝ^{m} is convex if each component function is convex. Recall that a set X ⊆ ℝ^{n} is convex if, for all x, y ∈ X and θ, 0 ⩽ θ ⩽ 1, then θx + (1 − θ)y ∈ X. That is, if x and y are in X then the whole line segment joining x and y also lies in X. It follows (by induction on k) that if f is a convex function

f (∑_{i=1}^{k} θ_{i}x_{i}) ⩽ ∑_{i=1}^{k} θ_{i}f(x_{i}),

for any choice of x_{i} ∈ ℝ^{n}, and θ_{i} ⩾ 0, i = 1, …, k, with ∑_{i=1}^{k} θ_{i} = 1.

2. For the problem P, it is sufficient that f be a convex function, g be a linear function and X be a convex set to ensure that ϕ is convex and consequently the problem can be solved by minimizing the Lagrangian.

3. For the inequality formulation of the problem

minimize f(x) subject to g(x) ⩽ b, x ∈ X

then ϕ is the lower boundary of the region {(g(x) + z, f(x)) : x ∈ X, z ⩾ 0} in ℝ^{m} × ℝ; in this case to ensure that ϕ is convex (and so as before, we can obtain the solution by minimizing the Lagrangian) it is sufficient that f and g are convex functions and X is a convex set.

4. It should be noted that the conditions in the situation of 3 are not enough in the context of 2. To see this, consider minimizing f(x) = x^{2} subject to g(x) = x^{3} = b, with b > 0, then ϕ(b) = b^{2/3} which is not convex.

6 April 2005

14