Slide 1:Direction Generation Methods Based on Linearization We present a method to solve the inequality constrained problem: This time, the constraints will not be added to the objective function as we used to do previously.


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:The Method of Feasible Directions 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:Define the set I to be the set of the active constraints at x(1), i.e. I = { j: gj(x(1)) = 0, j = 1, …, J} For j  I, the first order Taylor approximation of gj(x) is gj(x)  gj(x(1)) + gj(x(1))T(x  x(1)) For j  I, gj(x(1)) = 0 (because it is binding). In order for x to be feasible, gj(x) ≥ 0, hence gj(x(1))T(x  x(1)) ≥ 0 or gj(x(1))T d ≥ 0 Any direction d satisfying this relationship is called a feasible direction.


Slide 11:This relationship dictates the angle between d and gj(x(1)) to be between 0o and 90o. Area of feasible directions


Slide 12:Example Consider the problem min f(x) s.t. g(x) = 2x1 – x22 – 1 ≥ 0 for x(0) = [1, 1]T. Find a feasible direction at x(0). Can d* = [–1, 2]T be a feasible direction? Can d** = [2, 1]T be a feasible direction?


Slide 13:Solution The gradient of g(x) is given by g(x) = [2, –2x2]T The constraint is binding at x(0). A feasible direction has to satisfy the following relation: g(x(0))T d > 0  [2, –2]T [d1, d2]T = 2d1 – 2d2 > 0  d1 > d2 The direction d* is not a feasible direction because g(x(0))T d* = –6 < 0


Slide 14:The direction d** is a feasible direction because g(x(0))T d** = +2 > 0


Slide 15:Area of descent and feasible directions In order for x to solve the inequality constrained problem, the direction d has to be both a descent and feasible direction.


Slide 16:There are an infinite number of descent and feasible directions. To find the best direction, we solve this LP problem: max z =  s.t. f(x(1))T d ≤   gj(x(1))T d ≥  for j  I 1 ≤ di ≤ 1 i = 1, …, N


Slide 17:Once the direction of descent and feasibility is determined, a step of size  along this direction is made until either the optimum of f(x) is reached or some constraint is encountered, whichever occurs first. We first conduct a line search to find the value  at which some constraint gj(x) first becomes binding. For every constraint gj(x), we find j > 0 at which gj(x(1) + j d(1)) = 0 We choose  to be the smallest of these j’s. Now, we find  in the range 0 ≤  ≤  that will minimize f(x(1) +  d(1))


Slide 18:The step from x(0) along direction d to the first binding constraint is .


Slide 19:The Algorithm At a given feasible point x(t), let I(t) be the set of the active constraints at x(t): I = { j: gj(x(t)) = 0, j = 1, …, J} Step 1: Solve the LP problem max z =  s.t. f(x(t))T d ≤   gj(x(t))T d ≥  for j  I(t) 1 ≤ di ≤ 1 i = 1, …, N Label the solution d(t) and (t).


Slide 20:Step 2: If (t) ≤ 0, the iteration terminates, since no further improvement is possible. Otherwise, determine  = min{: gj(x(t) +  d(t)) = 0, j = 1, …, J and  ≥ 0} If no > 0 exists, set = . Step 3: Find (t) such that f(x(t) + (t) d(t)) = min{f(x(t) +  d(t)): 0≤  ≤ } Set x(t+1) = x(t) + (t) d(t).


Slide 21:Example Solve the NLP problem using the method of feasible directions with x(1) = [1, 1]T.


Slide 22:Solution Iteration 1: Identify the active constraints: g1(x(1)) = 0.0 g2(x(1)) = 6.2 Thus, g1 is the only active constraint and I(1) = {1}. Find the direction: The optimal solution is d(1) = [1, -1/3]T and  = 2.66 > 0.


Slide 23:Define x as x = x(1) +  d(1) Find  : g1(x) = 2(1 + ) – (1 – /3) – 1 = 2  + 2/3  – 2 / 9 = 0   = 0 or  = 24 Set 1 = 24. g2(x) = 9 – 0.8(1 + )2 – 2(1 – /3) = 6.2 – 14/15  – 0.8 2  = 2.261 or  = – 3.428 Set 2 = 2.261


Slide 24:Thus  = min (24, 2.261) = 2.261. Find the optimal : min f() = [(1+ ) – 3]2 + [(1 – /3) – 3]2  f ' = 2( – 3) – 2/3 (– /3 – 2) = 0   = 6/5 Since 6/5 < 2.261, set (1) = 6/5. Compute the next point: x(2) = [2.2, 0.6]T.


Slide 25:Iteration 2: Identify the active constraints: g1(x(2)) = 3.04 g2(x(2)) = 3.9 Both constraints are not active. Find the direction: The optimal solution is d(2) = [1, 1]T and  = 6.4 > 0.


Slide 26:Define x as x = x(2) +  d(2) Find  : g1(x) = 2(2.2 + ) – (0.6 + )2 – 1 = 0   = -1.3888 or  = 2.1888 Set 1 = 2.1888. g2(x) = 9 – 0.8(2.2 + )2 – 2(0.6 + ) = 0   = -7.55030 or  = 0.65030 Set 2 = 0.65030. Thus  = 0.65030.


Slide 27:Find the optimal : min f() = [(2.2+ ) – 3]2 + [(0.6 + ) – 3]2   = 1.6. Since 0.65030 < 1.6, set (2) = 0.65030. Compute the next point: x(3) = [2.8503, 1.2503]T.