Presentation Transcript
Slide 1:Gradient Projection Method for Linearly Constrained Problems We present a method to solve problems of this type:
where the rows of A1 are the coefficient vectors of the inequality linear constraints and the rows of A2 are the coefficient vectors of the equality constraints.
Slide 2:Preliminaries Consider two vectors, u and v. If the angle between them is 90o or less, then uTv ≥ 0. The product uTv = 0 if the angle is 90o.
Slide 3:If the angle between them is more than 90o, then uTv < 0.
Slide 4:Suppose x(1) is a feasible starting point.
Define x as
x = x(1) + d with ≥ 0
The first order Taylor approximation of f(x) is given by
In order for f(x) < f(x(1)), we have to have
A direction satisfying this relationship is called a descent direction.
Slide 5:This relationship dictates the angle between d and f(x(1)) to be greater than 90o and less than 270o. Area of descent directions
Slide 6:The smallest value of the product f(x(1))T d can be attained by setting d = f(x(1)).
The negative of the gradient is called the steepest descent direction. Steepest descent direction
Slide 7:Example Consider the problem
f(x) = (x1 – 3)2 + (x2 – 3)2
for x(0) = [1, 1]T.
Find the steepest descent direction at x(0).
Can d* = [–1, –2]T be a descent direction?
Can d** = [1, 1]T be a descent direction?
Slide 8:Solution The gradient of f(x) is given by
f(x) = [2(x1 – 3), 2(x2 – 3)]T
The steepest descent direction is given by the negative of the gradient evaluated at x(0):
–f(x(0)) = [4, 4]T
For d* to be a descent direction, we have to have
f(x(0))T d* 0
d* cannot be a descent direction.
Slide 9:For d** to be a descent direction, we have to have
f(x(0))T d** < 0
[–4, –4]T [1, 1]T = –8 < 0
d** is a descent direction.
Slide 10:Projection of a Vector on Another:
Take two vectors u and v, where the angle between them is .
We need to find the projection p of u on v:
Slide 11:The vectors p and v are in parallel, we can write:
Slide 12:Consider the following linear constraint:
g1(x) = 2x1 + x2 = 3
The gradient of g1 is orthogonal (perpendicular) to the surface of g1.
Slide 13:Single Linear Equality Constraint Case
The linear constraint can be written in general as
aT x = b
Given a feasible x(t) at which f 0.
We need to find a search direction that lies on the constraint and is a descent direction.
This direction can be found by projecting the negative of f(x(t)) onto the constraint surface.
This component of -f, denoted by fc, is a feasible direction.
Slide 14:The direction is also a descent direction because the angle between f and fc is greater than 90o.
Finding the direction fc requires the decomposition of -f into two orthogonal components: one parallel to the constraint surface and one perpendicular to the surface.
The parallel component will be the desired direction.
Note that the vector a (gradient of the constraint function) is perpendicular to the surface of the constraint.
Therefore, a direction s’’ for which aTs’’ = 0 is a feasible direction.
Slide 15:For any vector s, the component s’ that is perpendicular to the constraint surface must be equal to a constant times a (s’ = a).
The component of s (s’’) that is parallel to the constraint surface must satisfy aTs’’ = 0.
Any vector s can be written as:
s = s’ + s’’
Consider the product aTs:
aTs = aT(a) + aTs’’ = (aTa) + 0
Solving for :
= (aTa)-1 aTs
Now we have:
s = s’ + s’’ = a +s’’ = a(aTa)-1 aTs + s’’
Slide 16:Solving for s’’:
s’’ = s - a(aTa)-1 aTs = (I - a(aTa)-1 aT)s = P s
The matrix P is called the projection matrix.
Slide 17:Example
See the example and the solution in the book.
Slide 18:In case of multiple constraints, the extension can be easily made.
Given a system with K linear constraints:
A x = b
A is a KN matrix and b is a K vector.
The projection matrix is given by
P = I – AT (AAT)-1 A
The matrix P is symmetric and positive semi-definite.
Slide 19:The properties of projection constructions are
s = -Pf is a descent direction.
If s = 0, the point x(t) satisfies the Lagrange necessary conditions.
The vector of Lagrange multipliers is given by
= (AAT)-1 A f
Slide 20:Gradient Projection Algorithm
Step 0: Calculate P.
Step 1: Calculate s(t) = -Pf.
Step 2: If ||s(t)||≤ , terminate.
Step 3: Determine the maximum step size:
Step 4: Solve the line-search problem
min f(x(t) + s(t)) for 0 ≤ ≤ max
Step 5: Set x(t+1) = x(t) + * s(t), and go to step 1.
Slide 21:Treatment of Inequality Constraints
The gradient project algorithm can be extended to handle inequality constraints.
We will apply the active constraint strategy.
The constraint matrix A is formed so that the first K rows correspond to the equality constraints and the next M constraints correspond to the active inequality constraints.
The Lagrange multipliers are calculated as
The sign of uj is checked, it must be nonnegative at the optimum.
Slide 22:The constraint with the most negative uj is deleted from the active constraint set.
The new P is calculated.
Slide 23:Example
See the example and the solution in the book.