# Optimization and algorithms

I'm going over my practice midterm, and the last question has me stuck. It goes:

Let $$n \geq 1$$ be an integer and let A be a symmetric $$n \times n$$ matrix (not necessary positive definite) for which all its eigenvalues are non-zero. Let $$a \in \mathbb{R}^n$$ be a given vector. Consider the function $$f : \mathbb{R}^n → \mathbb{R}$$, defined as $$f (x) = 1/2 ∥A(x − a)∥^2$$, where $$∥ · ∥$$ is the Euclidean norm defined by $$||x|| = \sqrt{x^T x}$$.

a) What is the global minimizer $$x*$$. Why?

b) Write the updates in the steepest descent algorithm starting from a point $$x_0 \in \mathbb{R}^n$$ to approximate the optimizer $$x*$$. Determine the step size $$\alpha_k$$ in each step.

c) Assume we use a fixed step gradient algorithm to approximate $$x*$$. What is the maximal range for the step size $$\alpha$$ in terms of the eigenvalues of $$A$$ that ensures global convergence for the algorithm.

My attempt:

a) $$x*=(0,0,...,0)^T$$ as $$f(x)\geq0$$ with lowest value being $$0$$.

b) I know how to do the algorithm from my textbook. But I can't figure out how to find the gradient. So far I have $$f=1/2(\sqrt{(A(x-a))^T(A(x-a))}^2=1/2(x-a)^TA^TA(x-a)$$. I'm stuck here, so not sure how to go further.

c) I have no clue how to do this question.

• The smallest distance is 0. How can you choose $x$ to attain $f(x)= 0$?
– Sycorax
Oct 31, 2023 at 1:23
• @Sycorax Oh hm good point. I knew it had to be 0 in some form, but didn't think it through fully. I think choosing $x*=a$ makes more sense as $f(x)\geq 0$ and choosing $a$ makes $f(x)=0$. Oct 31, 2023 at 2:24

a) I see in the comments you already got to the correct solution.

b) The gradient is simply $$\frac{1}{2}\cdot\frac{\partial x^TA^TAx}{\partial x}$$.

You can differentiate the Matrix Calculus identities in the very useful link here:

https://en.wikipedia.org/wiki/Matrix_calculus

c) Did you learn about convexity and Smoothness (also called L-smooth functions) in class? If so, I'd suggest you answer yourself the following:

Is $$f$$ a smooth function? Is it convex?

What's its smoothness parameter (what's L)?

How is the smoothness parameter related to eigenvalues?

How is the smoothness parameter linked with maximal step-size?

I'm here for more help. Good luck!

• Thank you. I managed to get a gradient of $\grad f=AA(x-a)$. But now trying the method of steepest descent, it turned into a huge mess of values. It turned into $arg min f(x_0^{(0)}+\alpha AAa - \alpha AAx_0)=arg min(\frac{1}{2}(x_0^{(0)T}(1-\alpha AA)+a^T(\alpha AA-1))AA(x_0^{(0)}(1-\alpha AA)+a(\alpha AA-1)))$. I can't figure out how to simplify this further, if it's even on the right track. As for part c), the function is convex. I'm unfamiliar with what smoothness is. I assume since the eigenvalues are all definite positive, then my step size should be negative to move down the curve. Oct 31, 2023 at 18:37
• Gradient Descent doesn't work that way... The update step in Gradient Descent is of type: $x^{(0)}+\alpha_k \nabla f\left(x^0\right)$. You already calculated the gradient so you can plug it in the above expression. Nov 1, 2023 at 6:24
• c) From what I know maximal step size is $\frac{2}{\max\{|\lambda_i|\}|}$ with $\{\lambda_i\}$ the set of $A$'s eigenvalues. The reason lies in the theory of $L$-smooth convex functions. You can read about it here: math.stackexchange.com/questions/3587312/… jhc.sjtu.edu.cn/public/courses/CS257/2020/slides/lec9.pdf Nov 1, 2023 at 6:43
• @AlexTeusch Thanks so much. I think I'm slowly getting it. I was using a formula from my textbook for b) without really understanding what I was doing. The formula for c) looks familiar, I think the wording confused me. Nov 1, 2023 at 20:07