Question

2. Steepest descent for unconstrained quadratic function minimization The steepest descent method for minimize f(x) is the gradient descent method using exact line search, that is, the step size of the kth iteration is chosen as Ok = argmin f(x“ – av f(x)). a20 (a) (3 points) Consider the objective function f(x):= *xAx- Ax - c^x + d. where A e RrXnCER”, d E R are given. Assume that A is symmetric positive definite and, at xk, f(x) = 0. Give a formula of or in terms xk, A, c, d. (b) (5 points) Consider R2. Starting from xº = (0,0), perform two iterations of the steepest descent method for minimize f (11,22) := 5(+ zì) +222 +1. +

Answer 1

Recall Thus, and, F(x) = Ayo, which is Solution: Given f(x) = ² x TAX - CT X + d where A EIRhon, CEIRA DE IR Let F(X)= A (Hessian matrix) For The function f, If = AX-C (why)?? D [$(x)9()] = (f(x))To gW) + (36X))"o F(X) (D (f(x)))" - v f(x) Q(XT (Ax)) = xT O (AX) + (Qx) AX D (XT (AX)) = XT O (ax) + (AX) DX = XT A+ XTA = 2XTA D (CTX) = CT Therefore, D [+ XTA x - Tx] = (2xTA) - c = 'A-CT V f (x) = (XTA-CT) = AX-C symmetric. By second order sufficient condition , x*, at which vf(x*)=0 and F (x*) is positive definite , real symmetric x* is a strict local minimi zey of f(x) = { XT AX- CT X + d a solution of AX=C is a strict and, That is,

From к oo minimizer of f(x) = ₂ XTAX - CTX + d. now on, for The sake of Simplicity, we write I f (x ) Then. The steepest de scent algorithm for the quadratic xK+ where, ak is a minimizer of f (x*_ LK gk) & 2710 function is, Xk_dk gk That is, dk is a minimizer of Pk (2) = 1 / 2 (xk _ dk gk) A (XE LK gk ) - CT (x* dkg k) +d We can find an explicit formula for ako Assume that, IK Vf(xK) +0. otherwise if gk=0 Then xKt1 = xk stops. ad f (x * d.gk) Note, agk))" (gk) =( f (xk [A (XF_ d gk ) - c] (-k) since, Lk 710 is a minimizer of 44 (d) . Therefore P (2x) = 0

nece ecessary By applying First order condition to Pk (2) to get, - (xt_dk gk JTA A gk + CT gk = 0 - (xK) TA gk + 2x + kk (gr) A + CT gk gk = 7f (xK) = Q AXK -c =0 a gk since, Therefore dx (gv)Ta g* = [(x)TA - cm]ge where, (OK) = (XK)TACT We get, alix (gv) Tage = (g 6)" gk That is, dx = (gkJT gk (g KT Q Where gk = f(x) + 1xK gk = 7 f(xk) -v [Ź (xK)TA (xK) - CT XK +d = AXK_c

(b) Given, f (2182) = + (x2 + x² ) + 2x2 + 1 Now, If X2+2 A (Hessian matrix) Given, xo= LO - 3 = 0 (*) = [] and (go)T = [0 2 we have to calculate (go) I go The step length as [02] [3] [02] [69] [2] (go) A (go) 4 [o 2] [o 4 x = x - do go = []- 119] 4 [9] = [-2 Lo gl= if (21) 0 :. Therefore, function is minimized at x* = * = and Minimum value of f(x1, x2) is, . (0 + 6272) + 2 (2) +1 2 - 4 + 1 = -1 Hence, minimum value of +(2182) is -1