Question

b) Suppose we wish to minimize the function, f(X)-0.5XTCX +bTX+ 1, where b and C 1 ,using Steepest Descent optimization method starting from X Please carry out the first iteration by hand and check for convergence. If the above search direction is called S1 and the one to be used for the second iteration is called S2, what is the relationship between Si and S2, or more specifically, what is ST S2?

Answer 1

b. To start, let us write the function to be minimized and find its gradient.

Let  , then our function is

X = y

8 1 f(X) 0.5 xy [1 2] 1 1 2 +

If we multiply the matrices and simplify further, we get

f(x, y) = 0.5(8 + 2ry+22 ) x + 2y + 1= 4r xy 2y 1

Now we can find the gradient as

fx fy 8x 1 Vf(r, y) 2y2

Now let us apply the Steepest Descent optimization with the initial guess  .

1 Xo 1 0

With this vector, we can find the first search direction .

Vf\x X

This is just

.

811 Vf(1,1)12+2 10 5

The next estimate is found as

X1XO- hVf\x

Substituting for ${X_0}$, we find

1 10h 1 -h 10 X1 1 5h

We now need to choose the appropriate value of h. To do this, we optimize the one variable function .

g(h) f(X1) f(1 10h, 1-5h) 4(1 10h)(1 10h) (1 -5)(1-5h)2 (1 10h)2(1 5h)1

The value of h we need is the one that satisfies . So we find the derivative of g and set it equal to 0.

g(h)0

${g}'(h) = 0 \\ \Rightarrow -80(1-10h) - 10(1-5h) -20 -10(1-5h) - 5(1-10h) = 0 \\ \Rightarrow -85 - 20 + 850 h + 100h =20$

Simplifying the above equation gives us  $h = \frac{125}{950} = \frac{5}{38}$.

This gives us the new estimate

$X_1 = X_0 - \frac{5}{38} \nabla f|_{X_0} = \begin{bmatrix} 1\\ 1 \end{bmatrix} - \frac{5}{38} \begin{bmatrix} 10\\ 5 \end{bmatrix} = \begin{bmatrix} -6/19\\ 13/38 \end{bmatrix}$

To check for convergence:

We can find the optimal value of x and y directly by setting $\nabla f(x,y) = (0,0)$ . This gives us the system of equations

Solving them gives us x = 0, y = -1. The\us the optimal value of X is .

Now we can evaluate the distance from X* to X₀ as well as X₁. If we have convergence, then the distance from X₁ to X* should be smaller than the distance from X* to X₀. Let us find these distances:

$d(X_0, X^*) = \left \| X_0 - X^* \right \| = \left \| \begin{bmatrix} 1\\ 1 \end{bmatrix} - \begin{bmatrix} 0\\ -1 \end{bmatrix} \right \| = \left \| \begin{bmatrix} 1\\ 2 \end{bmatrix} \right \| = \sqrt{1^2 + 2^2} = \sqrt{5} \\ d(X_0, X^*) \approx 2.236$

$d(X_1, X^*) = \left \| X_1 - X^* \right \| = \left \| \begin{bmatrix} -6/19\\ 13/38 \end{bmatrix} - \begin{bmatrix} 0\\ -1 \end{bmatrix} \right \| = \left \| \begin{bmatrix} -6/19\\ 51/38 \end{bmatrix} \right \| \\ = \sqrt{ \left ( \frac{6}{19} \right )^2 + \left ( \frac{51}{38} \right )^2} = \sqrt{\frac{144 + 2601}{38^2}} = \frac{\sqrt{2745}}{38}$

$\Rightarrow d(X_1, X^*) \approx 1.378$

We see that the second iteration has brought us closer to the actual optimal value.

-----------------------------------------------------------------------------------------------------------

c. Now if we repeat this procedure, the search direction for the second iteration will be $S_2 = \nabla f|_{X_1} = \begin{bmatrix} -48/19 + 13/38 + 1\\ -6/16 + 26/38 + 2 \end{bmatrix} = \begin{bmatrix} -45/38\\ 45/19 \end{bmatrix}$

From b, we already know the first search direction $S_1 = \begin{bmatrix} 10\\ 5 \end{bmatrix}$ .

To find the relationship between the 2 search directions, let us find their dot product .

.

S S2= 10 5145/38 45/19 -45 x 5 45 x 5 19 19

The dot products of the consecutive search directions is 0, hence they are orthogonal.