Presentation Transcript
Reduced Gradient Method :Reduced Gradient Method The discussions in this section focus on solving constrained nonlinear programs by methods that resemble the solution approach of the simplex method for linear programming.
We focus on the reduced gradient method for linear constraints.
Slide 2:The linearly constrained problem can be written as
where f is a continuously differentiable real function, A is an mn matrix, b is an m vector, and m ≤ n.
The vector of variables x can be partitioned into two sub-vectors x = (xB, xN)T.
The vector xB = (xB1,. . . , xBm)T is the vector of basic, or dependent variables.
The vector xN = (xN1, . . . , xNn-m) is the vector of nonbasic, or independent, variables.
Slide 3:The matrix A is partitioned into A = [B, C], where we assume that the first m columns of A correspond to the basic variables.
We can write
BxB + CxN = b (1)
and
xB = B-1b - B-1CxN (2)
We assume that the basic variables are non-degenerate, that is, xB > 0.
The nonbasic variables are called independent, since by assigning some numerical values to them, we obtain a unique solution of (1).
Slide 4:The basic idea of reduced gradient methods is to eliminate xB (as a function of xN) via (2) and consider the optimization problem only in terms of xN.
We can obtain the reduced gradient r Rn-m by the formula
If we could make a small move from a current value of xN in the direction of the negative reduced gradient without violating the nonnegativity constraints on the vector x, a decrease in the function value of f would occur.
Slide 5:To find the step size, for a feasible xk, compute for i = l, . . . , n - m:
and
Then, zk+1 = (zB,k+1 , zN,k+1)T.
The next point, xk+1 = (xB,k+1 , xN,k+1)T, is given by
(3)
Slide 6:where *k+1 is computed from the relations
and
If *k+1< 1k+1, let xk+1 be defined by (3). Otherwise,
for some l, and xlB is dropped from the vector of basic variables in exchange for the largest positive nonbasic variable. The algorithm terminates if |zk+1|≤ . If no such exists, set 1=
Slide 7:Example
See the example and the solution in the handout.