Lewis c01.

tex V1 - 10/18/2011 3:39pm Page 15

PROBLEMS 15

Equation (1.2-38) allows a further interpretation of the Lagrange multiplier; it

indicates the rate of change of the optimal value of the performance index with
respect to the constraint.

1.3 NUMERICAL SOLUTION METHODS

Analytic solutions for the stationary point (u, x )* and minimal value L* of
the performance index cannot be found except for simple functions L(x, u) and
f (x, u). In most practical cases, numerical optimization methods must be used.
Many methods exist, but steepest descent or gradient (Luenberger 1969, Bryson
and Ho 1975) methods are probably the simplest.
The steps in constrained minimization by the method of steepest descent are
(Bryson and Ho 1975)

1. Select an initial value for u.

2. Determine x from f (x , u) = 0.
3. Determine λ from λ = −fx−T Lx .
4. Determine the gradient vector Hu = Lu + fuT λ.
5. Update the control vector by u = −αHu , where K is a positive scalar
constant (to find a maximum use u = αHu ).
6. Determine the predicted change in the value of L, L = HuT u =
−αHuT Hu . If L is sufficiently small, stop. Otherwise, go to step 2.

There are many variations to this procedure. If the step-size constant K is too
large, then the algorithm may overshoot the stationary point (u, x )* and con-
vergence may not occur. The step size should usually be reduced as (u, x )*
is approached, and several of the existing variations differ in the approach to
adapting K .
Many software routines are available for unconstrained optimization. The
numerical solution of the constrained optimization problem of minimizing
L(x, u) subject to f (x , u) = 0 can be obtained using the MATLAB function
constr.m available under the Optimization Toolbox. This function takes in the
user-defined subroutine funct.m, which computes the value of the function, the
constraints, and the initial conditions.

PROBLEMS
Section 1.1
1.1-1. Find the critical points u* (classify them) and the value of L(u*) in
Example 1.1-1 if
 
−1 1
a. Q = , S T = [0 1].
1 −2
 Lewis c01.tex V1 - 10/18/2011 3:39pm Page 16

16 STATIC OPTIMIZATION

 
−1 1
b. Q = , S T = [0 1].
1 2

Sketch the contours of L and find the gradient Lu .

1.1-2. Find the minimum value of

L(x1 , x2 ) = x12 − x1 x2 + x22 + 3x1 . (1)

Find the curvature matrix at the minimum. Sketch the contours, showing the
gradient at several points.
1.1-3. Failure of test for minimality. The function f (x, y) = x 2 + y 4 has a
minimum at the origin.
a. Verify that the origin is a critical point.
b. Show that the curvature matrix is singular at the origin.
c. Prove that the critical point is indeed a minimum.

Section 1.2
1.2-1. Ship closest point of approach. A ship is moving at 10 miles per hour
on a course of 30◦ (measured clockwise from north, which is 0◦ ). Find its closest
point of approach to an island that at time t = 0 is 20 miles east and 30 miles
north of it. Find the distance to the island at this point. Find the time of closest
approach.
1.2-2. Shortest distance between two points. Let P 1 = (x 1 , y 1 ) and P 2 =
(x 2, y 2) be two given points. Find the third point P 3 = (x 3, y 3) such that
d 1 + d 2 is minimized with the constrain d1 = d2, where d 1 is the distance
from P 3 to P 1 and d 2 is the distance from P 3 to P 2.
1.2-3. Meteor closest point of approach. A meteor is in a hyperbolic orbit
described with respect to the earth at the origin by

x2 y2
− = 1. (1)
a2 b2
Find its closest point of approach to a satellite that is in such an orbit that it has
a constant position of (x 1 , y 1 ). Verify that the solution indeed yields a minimum.
1.2-4. Shortest distance between a parabola and a point. A meteor is moving
along the path
y = x 2 + 3x − 6. (1)

A space station is at the point (x , y) = (2, 2).

a. Use Lagrange multipliers to find a cubic equation for x at the closest point of
approach.
 Lewis c01.tex V1 - 10/18/2011 3:39pm Page 17

PROBLEMS 17

b. Find the closest point of approach (x , y), and the distance from this point
to (2, 2).

1.2-5. Rectangles with maximum area, minimum perimeter

a. Find the rectangle of maximum area with perimeter p. That is, maximize

L(x, y) = xy (1)

subject to
f (x, y) = 2x + 2y − p = 0. (2)

b. Find the rectangle of minimum perimeter with area a 2 . That is, minimize

L(x, y) = 2x + 2y (3)

subject to
f (x, y) = xy − a 2 = 0. (4)

c. In each case, sketch the contours of L(x, y) and the constraint. Optimization
problems related like these two are said to be dual .

1.2-6. Linear quadratic case. Minimize

   
1 T 1 0 1 T 2 1
L= x x+ u u
2 0 2 2 1 1

if    
1 2 2
x=
3 + 1 0
u.

Find x *, u*, λ*, L*.

1.2-7. Linear quadratic case. In the LQ problem define the Kalman gain

K =(B T QB + R)−1 B T Q

(1)

a. Express u*, λ*, x *, and L* in terms of K .

b. Let
S0 = Q − QB(B T QB + R)−1 B T Q

(2)

so that L∗ = cT S0 c/2. Show that

S0 = Q(I − BK) = (I − BK)T Q(I − BK) + K T RK. (3)

√ √
Hence, factor L* as a perfect square. (Let Q and R be the square roots
of Q and R.)
 Lewis c01.tex V1 - 10/18/2011 3:39pm Page 18

18 STATIC OPTIMIZATION

c. Show that

S0 = (Q−1 + BR−1 B T )−1 . (4)

1.2-8. Geometric mean less than or equal to arithmetic mean

a. Show that the minimum value of x 2 y 2 z 2 on the sphere x 2 + y 2 + z 2 = r 2 is
(r 2 /3)3 .
b. Show that the maximum value of x 2 + y 2 + z 2 on the sphere x 2 y 2 z 2 =
(r 2 /3)3 is r 2 .
c. Generalize part a or b and so deduce that, for ai > 0,

(a1 a2 · · · an )1/n ≤ (a1 + a2 + · · · + an )/n.

Note: The problems in parts a and b are dual (Fulks 1967).

1.2-9. Find the point nearest the origin on the line 3x + 2y + z = 1,

x + 2y − 3z = 4.
1.2-10. Rectangle inside Ellipse
a. Find the rectangle of maximum perimeter that can be inscribed inside an
ellipse. That is, maximize 4(x + y) subject to constraint x 2 /a 2 + y 2 /b 2 = 1.
b. Find the rectangle of maximum area 4xy that can be inscribed inside an ellipse.