Page 246 - Numerical Methods for Chemical Engineering

Lagrangian methods for constrained optimization 235

Taking the dot product with v, at a constrained minimum (5.76) requires that v = 0; hence,

= n e λ i ∇g i | (5.78)
x min
∇F| x min
i=1
For multiple equality constraints we thus define the Lagrangian as
L(x; λ) = F(x) − n e λ i g i (x) (5.79)
i=1
and use the same technique as before. Note that the existence of a constrained minimum is
not guaranteed, for there may exist no points that satisfy all constraints simultaneously.

Example. Finding the closest points on two ellipses

We consider here a simple example in which we wish to find the points on two ellipses that
are nearest to each other. Let (x 1 , y 1 ) and (x 2 , y 2 ) be the coordinates of the points on the
first and second ellipses, centered at (x c1 , y c1 ) = (0, 0) and (x c2 , y c2 ) = (5, 5) respectively.
For (x 1 , y 1 ) and (x 2 , y 2 ) to lie on the ellipses, they must satisfy the two equality constraints
2
2
a 1 (x 1 − x c1 ) + b 1 (y 1 − y c1 ) = 1 a 1 = 0.5 b 1 = 0.3
2
2
a 2 (x 2 − x c2 ) + b 2 (y 2 − y c2 ) = 1 a 2 = 0.2 b 2 = 0.4 (5.80)
ellipse min.m uses the augmented Lagrangian method to minimize
2
F(x 1 , y 1 , x 2 , y 2 ) = (x 1 − x 2 ) + (y 1 − y 2 ) 2 (5.81)
subject to (5.80). The initial guesses are the ellipse centers and the Lagrange multipliers are
set initially to zero.
Figure 5.12 shows the trajectories at each multiplier iteration of (x 1 , y 1 ) (circles)
and (x 2 , y 2 ) (diamonds), with a line connecting the final optimal points. fminunc is
used to minimize the augmented Lagrangian at each multiplier iteration. In practice, the
MATLAB constrained minimizer fmincon would be preferred; ellipse min.m is meant only
to demonstrate the augmented Lagrangian technique. Both fminunc and fmincon are part
of the optional MATLAB optimization toolkit. If your installation of MATLAB does not
include this toolkit, you must apply the augmented Lagrangian procedure directly, as in
ellipse min.m, and use the provided routine gradient minimizer.m to perform each uncon-
strained minimization. The code for solving this problem with fmincon is presented below,
following our discussion of inequality constraints.

Treatment of inequality constraints

We now consider methods to solve the problem
minimize F(x)
g i (x) = 0 i = 1, 2,..., n e
subject to (5.82)
h j (x) ≥ 0 j = 1, 2,..., n i