Equality Constrained Optimization Using a Tangent Plane Approach

Frank J. Kampas (fkampas@msn.com)

Introduction

The usual method for minimization or maximization of an objective function f((Subscript[x, i])) , i = 1 to n, subject to m equality constraints (Subscript[h, j])( (Subscript[x, i]) ) =  0, j = 1 to m, is the method of Lagrange multipliers (see http://mathworld.wolfram.com/LagrangeMultiplier.html).  One introduces m Lagrange multipliers (Subscript[λ, j]) in  n subsididary equations  ∇f + Σ (Subscript[λ, j]) ∇(Subscript[h, j]) = 0 and simultaneously solves the constraint equations and the subsidiary equations.  The Lagrange multipliers have the useful feature that they are the negative of the sensitivities of the objective function at the optimum with respect to small changes in the right-hand side of the constraints.

The geometric interpretation of the Lagrange multiplier method is straightforward for one constraint.  The gradient of the objective function must be parallel to the gradient of the constraint function and therefore is a multiple of it.  For multiple constraints, a more rigorous approach uses the concept of the tangent plane.  Luenberger uses this approach to derive the Lagrange mulitplier method( "Linear and Nonlinear Programming, 2nd edition" by David G. Luenberger, Addison-Wesley, 1989, p. 300.)

The tangent plane, at a point on the surface defined by the constraints, is defined by the tangents, at that point, to all curves lying in the surface passing through the point.  Following Luenberger, we define the tangent plane M at the point (SuperStar[x]) as the set of all t such that t is orthogonal to the gradient of the constraints ∇h at that point.

M = { t : ∇h((SuperStar[x])) t = 0 }

Note that ∇h((SuperStar[x])) t represent a matrix multiplication when there is more than one constraint, since the gradient, taken with respect to the n coordinates, is a gradient of the m constraints. Luenberger notes that there is another condition in the definition of the tangent plane, namely that the point (SuperStar[x]) is a regular point, which means that the gradient vectors ∇(Subscript[h, j])((SuperStar[x])) are linearly independent.

If a point (SuperStar[x]) on the constraint surface h = 0 is an optimum point of the function f, then f '((SuperStar[x])) must be zero for any curve on the surface passing through (SuperStar[x]).  Therefore the gradient of f must be orthogonal to the tangent vector of any curve on the surface passing through x* and therefore must be orthogonal to the tangent plane at x*.  In mathematical terms, the condition that x* is an optimum point becomes the following:  any t which sastisfies ∇h((SuperStar[x])) t = 0  must also satisfy ∇f t = 0 (and x* must be a regular point).

Rather than derive the Lagrange multiplier method from the statement in the previous paragraph, the remainder of this article will show how the tangent space approach can be used to perform simple equality-constrained optimizations.  For those readers familiar with linear programming, it can be noted that the Lagrange multiplier approach is the dual problem to a formulation of the tangent plane approach in which the objective function is the maximization of ∇f t.

A Single Constraint Example

Consider the simple example of finding the extremes of the expression x + y subject to the constraint (x^2) + (y^2) == 1.  The problem is solved 3 different ways:  with Maximize and Minimize, with Lagrange multipliers and with the tangent plane approach.  All 3 approaches give the same result.

Problem Definition

vars  =  {x, y};

f =  x + y;

h  =  (x^2) + (y^2) - 1;

Maximize and Minimize

It is easy to find the maximum and minimum using the built-in functions.

Maximize[{f, h == 0}, vars] // Simplify

Minimize[{f, h == 0}, vars] // Simplify

The uniqueness of these solutions can also be verified using Reduce, since it gives all solutions to a set of equations.

Reduce[{f  ==  (Sqrt[2]) ,  h == 0}, vars] // 
      Simplify

Reduce[{f  ==  -(Sqrt[2]) ,  h == 0}, vars] // 
      Simplify

Lagrange Multiplier Approach

Performing the minimization using Lagrange multipliers can be done in a manner similar to the vector notation used in the introduction:

∇f  =  D[f, {vars}]

∇h  =  D[h, {vars}]

The value of the objective function at the optimum points can be obtained by adding a variable obj equal to the objective function.  A little manipulation is required to combine the Lagrange multiplier equations and the constraint.   Thread[∇f+λ ∇h==0] gives a list of two constraints. Applying And to the list of two constraints converts them into two constraints joined by &&, which are then "anded" to the two remaining constraints.

Reduce[
      And  @@  Thread[∇f + λ ∇h == 0]  &&  
        h == 0  &&  obj  ==  f, Join[vars, {obj, λ}], 
      Backsubstitution  ->  True]

Tangent Plane Approach

For the tangent plane approach a vector t in the tangent plane is needed, rather than the multiplier.

t = {tx, ty};

The three-part version of the ForAll function is used to specify that ∇f t = 0 for all t that satisfy ∇h t = 0.

?ForAll

Reduce[
      ForAll[{tx, ty}, ∇h . t  == 0, ∇f . t  == 
            0] &&  h == 0  &&  obj  == f, {x, y, obj}, 
      Backsubstitution  ->  True]

A Multiple Constraint Example

Consider the optimization of x + y + z subject to two constraints (((x - 1))^2)  + (y^2)  +  (z^2) = 3 and (((x + 1))^2)  + (y^2)  +  (z^2) = 3.  As before, the 3 approaches give the same result.

Problem Definition

f  =  x  +  y  +  z;

h  =  {(((x - 1))^2) + (y^2) + (z^2) - 3, (((x + 1))^2) + (y^2) + 
            (z^2) - 3 };

vars  =  {x, y, z};

Maximize and Minimize

There in one maximum point and one minimum point.

Maximize[Join[{f}, Thread[h == 0]], vars]

Minimize[Join[{f}, Thread[h == 0]], vars]

Reduce[Join[{f == 2}, Thread[h == 0]], vars]

Reduce[Join[{f == -2}, Thread[h == 0]], 
      vars]

Lagrange Multiplier Approach

The Lagrange multiplier code is modified slightly since ∇h is now a matrix and there are two multipliers, which can be expressed as a vector.

∇f  =  D[f, {vars}]

∇h  =  D[h, {vars}]

Reduce[
      And  @@  
          Thread[∇f + {λ1, λ2} .  ∇h == 
              0]  &&  h == 0  &&  obj  ==  f, 
      Join[vars, {obj, λ1, λ2}], 
      Backsubstitution  ->  True]

Tangent Plane Approach

t = {tx, ty,  tz};

Reduce[
      ForAll[{tx, ty, tz}, 
          And  @@  Thread[∇h . t  == 0], ∇f . t  == 
            0] &&  And  @@  Thread[h == 0]  &&  obj  == f, 
      Join[vars, {obj}], 
      Backsubstitution  ->  True]

Summary

The tangent plane approach to equality-constrained optimization is shown to give the same results as the built in functions Maximize and Minimize and the Lagrange multiplier approach, for two simple problems.  This approach is not computationally useful, since the time required by Reduce increases rapidly with the number of variables and inequalities.  However, it is useful for providing insight into the underlying mathematics of the Lagrange multiplier approach.  Also it provides an instructive application of the quantifier ForAll.