0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The smallest distance is 0. How can you choose $x$ to attain $f(x)= 0$? $\endgroup$
    – Sycorax
    Oct 31, 2023 at 1:23
  • $\begingroup$ @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$. $\endgroup$
    – Albibi
    Oct 31, 2023 at 2:24

1 Answer 1

0
$\begingroup$

Per your sections:

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!

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Albibi
    Oct 31, 2023 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – Alex Teush
    Nov 1, 2023 at 6:24
  • $\begingroup$ 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 $\endgroup$
    – Alex Teush
    Nov 1, 2023 at 6:43
  • $\begingroup$ @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. $\endgroup$
    – Albibi
    Nov 1, 2023 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.