Projection Methods for Linear Equality Constrained Problems

Projection Methods for Linear Equality Constrained Problems

4 Solving the Direction -Finding Problem (DFP)

Approach 1 to solving DFP: solving linear equations


Create the system of linear equations:

and solve this linear system for by any method at your disposal.

If , then

and so is a Karush-Kuhn-Tucker point of P.

If , then rescale the solution as follows :

Proposition 4.1 defined above satisfy (1), (2), (3), (4), and (5).

Note that the rescaling step is not necessary in practice, since we use a
line-search.

Approach 2 to solving DFP: Formulas

Let

If > 0, let

If =0, let =0.

Proposition 4.2 P is symmetric and positive semi-definite. Hence ≥ 0.

Proposition 4.3 defined above satisfy (1), (2), (3), (4), and (5).

5 Modification of Newton’s Method with Linear
Equality Constraints

Here we consider the following problem:

Just as in the regular version of Newton’s method, we approximate the
objective with the quadratic expansion of f(x) at :

Now we solve this problem by applying the KKT conditions, and so we
solve the following system for (x, u):

Now let us substitute the fact that:

and .

Substituting this and replacing , we have the system:

The solution (d, u) to this system yields the Newton direction d at .

Notice that there is actually a closed form solution to this system, if we
want to pursue this route. It is:

This leads to the following version of Newton’s method for linearly
constrained problems:

Newton’s Method for Linearly Constrained Problems:

Step 0 Given x0 for which Ax0 = b, set k ← 0

Step 1 ← xk. Solve for :

If , then stop.

Step 2 Choose step-size αk =1.

Step 3 Set Go to Step 1.

Note the following:

• If , then is a KKT point. To see this, note from Step 1
that , which are precisely the KKT conditions for
this problem.

• Equations (8) are called the “ normal equations ”. They were derived
presuming that is positive-definite, but can be used even when
is not positive-definite.

• If is positive definite , then is a descent direction. To see this,
 note that from(8) since is positive
definite.

6 The Variable Metric Method

In the projected steepest descent algorithm, the direction d must lie in the
ellipsoid

where Q is fixed for all iterations. In a variable metric method, Q can
vary at every iteration. The variable metric algorithm is:

Step 1. satisfies Compute .

Step 2. Choose a positive-definite symmetric matrix Q. (Perhaps
, i.e., the choice of Q may depend on the current point.) Solve the direction-
finding problem
(DFP):

DFP:

If , stop. In the case, is a KKT point.

 

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

Step 4. Set Go to Step 1.

All properties of the projected steepest descent algorithm still hold here.

Some strategies for choosing Q at each iteration are:

• Q = I

• Q is a given matrix held constant over all iterations

• Q =  where H(x) is the Hessian of f(x). It is easy to show
that that in this case, the variable metric algorithm is equivalent to
Newton
’s method with a line-search, see the proposition below.

, where is chosent to be large for early iterations,
but is chosen to be small for later iterations. One can think of this
strategy as approximating the projected steepest descent algorithm in
early iterations, followed by approximating Newton’s method in later
iterations.

Proposition 6.1 Suppose that Q = in the variable metric algorithm.
Then the direction in the variable metric method is a positive scalar times
the Newton direction.

Proof: If Q = , then the vector of the variable metric method is
the optimal solution of DFP:

DFP:

The Newton direction for P at the point is the solution of the following
problem:

NDP:

If you write down the Karush-Kuhn-Tucker conditions for each of these two
problems, you then can easily verify that for some scalar γ> 0.

q.e.d.

Prev Next