# Projection Methods for Linear Equality Constrained Problems

1 Review of Steepest Descent

Suppose we want to solve

where f(x) is differentiable . At the point , f(x) can be approximated
by its linear expansion

for d “small.” This leads to the choice of d dictated by the direction-finding
problem:

which is equivalent to :

The solution to this direction finding problem is:

Because we choose our next step as

for some choice of step-length α, then we can re-scale the direction simply
as:

That is, the steepest descent direction is simply the negative of the
of f(x) at .

2 Equality Constrained Problems

Now consider the slightly more complicated problem

P : minimize f(x)

where f(x) is differentiable. The KKT conditions for this problem are as
follows:

We wish to find such a KKT point.

Suppose that we are at the point , where, , i.e.,   is a feasible
point. Again we have

for d “small.” In order to choose the direction and compute the next point

for some stepsize α, we will solve the fol lowing direction -finding problem:

or equivalently (by setting )

Note that Ad = 0 ensures that for any α. Also note
that the constraint says that d must lie in the Euclidean unit
ball B, defined as:

However, the Euclidean ball is but one metric , and we might instead be
more general, and choose to restrict d to lie in an ellipsoid

where Q is a given symmetric and positive -definite matrix. This leads to the
more general direction-finding problem:

The projected steepest descent algorithm is:

Step 1. satisfies . Compute.

Step 2. Solve the direction-finding problem (DFP):

If , stop . In the case , is a Karush-Kuhn-Tucker point.

Step 3. Solve ,for the stepsize , perhaps chosen by an exact
or inexact linesearch.

Step 4. Set . Go to Step 1.

Note that if Q = I and the equality constraints Ax = b are absent, this
algorithm is just the steepest descent algorithm.

3 Properties of the Projected Steepest Descent
Direction

Note that DFP is a convex program, and d = 0 is a Slater point. Therefore,
the Karush-Kuhn-Tucker conditions are necessary and sufficient for
optimality in DFP. These conditions are:

As it turns out, it is extremely easy to solve these equations . (We will
see this shortly.) Let solve the equations (1)-(5) with multipliers and .

Proposition 3.1 is a Karush-Kuhn-Tucker point of P if and only if

Proposition 3.2   is a Karush-Kuhn-Tucker point of P if and only if =
0.

Proposition 3.3 If is not a Karush-Kuhn-Tucker point of P, then is
a descent direction.

Proposition 3.4 The projected steepest descent algorithm has the same
convergence properties and the same linear convergence as the steepest descent
algorithm. Under the same conditions as in the steepest descent algorithm,
the iterates converge to a Karush-Kuhn-Tucker point of P, and the
convergence rate is linear, with a convergence constant that is bounded in
terms of eigenvalues identically as in the steepest descent algorithm.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of April 25th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!