Optimization Methods - Recitation 11

Recitation 11 1 Methods for Unconstrained Problems Steepest descent method Direction dk = −∇f (xk), which is guaranteed to be a descent direction if ∇f (xk) =  0. Step length α is selected so that f (xk+1) < f (xk). Linear convergence, any initial solutions Newton method Minimize the 2nd order Taylor expansion approximation of the function f (x) around a point x. Direction dk = −(∇2f (x))−1∇f (x) Equally attracted to local maxima, initial solution matters, locally quadratic convergence with good intial solutions. Conjugate gradient method Based on expanding subspace theorem: given d1 , . . . , dm ∈ Rn are Q-conjugate (d
i Qdj =0, i = j,
m −∇f (x0 )� di m ≤ n, fnction f (x) = 12 x
Qx + c
x, initial starting point x0 , then x = x0 + i=1 di is the d�i Qdi
m related solution of the problem minα f (x0 + i=1 αi di ). If m = n then the solution above is the optimal solution to the problem minx f (x) k+1 � k (xk+1 )2 Direction dk+1 = −∇f (xk+1 ) + λk dk , where λk = ∇f(d(xk )� Qd)kd in quadratic case and λk = ∇f in ∇f (xk )2 general case, which is used to maintain the Q-conjugate property. Finite convergence for quadratic case. 2 Constrained Optimization KKT necessary condition If the feasible region is K = {x ∈ Rn |gj (x) ≤ 0, hi (x) = 0} then the KKT necessary condition is stated as follows: x is a local minimum, I = {j|gj (x) = 0}, one of the following condition holds: 1. Constraint qualification condition: all ∇gj (x), j ∈ I and all ∇hi (x) are linearly independent 2. Slater condition: there exist an x such that gj (x) < 0 and hi (x) = 0 for all i, j. 3. All constraints are linear then there exists u and v: 1 1. ∇f (x) +
j uj ∇gj (x) +
i vi ∇hi (x) =0 2. u ≥ 0 3. gj (x) ≤ 0, hi (x) = 0 4. uj gj (x) = 0 KKT sufficient condition If K is a convex
set, f is a convex
function, x is a feasible solution, then if there exists u ≥ 0 and v such that ∇f (x) + j uj ∇gj (x) + i vi ∇hi (x) = 0 and uj gj (x) = 0 for all j then x is a global optimum of the problem. KKT condition is both necessary and sufficient for convex optimization problems under the constraint qualification condition. 3 Interior Point Methods Affine scaling method An initial interior starting point x0 A descent direction is found by solving the optimization problem min s.t. c
d Ad = 0
d X −2 d ≤ 1 where X = diag(x0 ). A closed form of d could be obtained using KKT condition. Step length can be selected to be short step or long step. Barrier methods A barrier function G(x) is a continuous function that tends to ∞ when gj (x) tends to 0− . The barrier method removes all inequality constraints and put them into the objective function using an appropriate barrier function with a parameter µ that tends to 0. Primal path following algorithm uses quadratic approximation to calculate the Newton direction in each iteration: min (c
− µe
X −1 )d + 12 µd
X −2 d s.t. Ad = 0 Primal-dual path following algorithm computes the Newton direction for both primal and dual problem in each iteration by solving the system of equations F (z) = 0 where ⎡ ⎤ Ax − b F (z) = ⎣ A
p + s − c ⎦ XSe − µe 2