0

Let $F(x)=〈Ax,x〉+〈2b,x〉+c, x\in\mathbb R^n$, A is real, symmetric, regular and positive definite matrix, $a,b\in\mathbb R^n$, $c\in\mathbb R$ are fixed.

  1. What is necessary condition for local minimum of F?

  2. Is enough condition satisfied too?

I know that necessary condition is that differential of F, if exists, is 0.

I have this written in my notebook:

$F(x+h)-F(x)= 〈A(x+h),x+h〉+〈2b,x+h〉+c-〈Ax,x〉-〈2b,x〉-c= 〈Ax,x〉+〈Ax,h〉+〈Ah,x〉+〈Ah,h〉+〈2b,x〉+〈2b,h〉-〈Ax,x〉-〈2b,x〉= 〈Ax,h〉+〈Ah,x〉+〈Ah,h〉+〈2b,h〉= 2〈Ax,h〉+〈2b,h〉= 2〈Ax+b,h〉$

since h is not 0, this $F(x+h)-F(x)=0$ iff $Ax+b=0$ $=>$ $Ax=-b$ $=>$ $x=\frac{-b}{A}$.

What is not really clear to me is why

  1. 〈Ah,x〉=〈Ax,h〉

  2. 〈Ah,h〉=0

  3. What is enough condition?

gorica
  • 15
  • 2

1 Answers1

0

Presumably the inner product is the usual dot product.

  1. Since $A$ is positive definite, it is self-adjoint. Thus $\langle Ah,x\rangle=\langle h,Ax\rangle=\langle Ax,h\rangle$.
  2. When $h$ is nonzero, $\langle Ah,h\rangle$ must be nonzero too, because $A$ is positive definite. However, $\langle Ah,h\rangle=O(h^2)$. So, in first order approximation, $\langle Ah,h\rangle$ can be ignored when $h$ is small. By the way, what you should solve is not $F(x+h)-F(x)=0$ but $F(x+h)-F(x)=o(h)$. That is, you are going to find $x$ such that the first-order term in $h$ of $F(x+h)-F(x)$ is zero. Also, the solution is $x=-A^{-1}b$, not $x=\frac{-b}{A}$. Division of a vector by a matrix is in general undefined.
  3. Yes. In fact, by completing square, $$F(x)=\langle Ax,x\rangle+2\langle b,x\rangle+c=\left\langle A(x+A^{-1}b),(x+A^{-1}b)\right\rangle-\langle A^{-1}b,b\rangle+c.$$ The two trailing terms on RHS are constants. As $A$ is positive definite, the least possible value of $\left\langle A(x+A^{-1}b),(x+A^{-1}b)\right\rangle$ is zero, which occurs when $x+A^{-1}b=0$, i.e. when $x=-A^{-1}b$.
user1551
  • 139,064
  • Thank you, but I don't understand part 3. How should I check if enough condition is satisfied?

    And I know that I can't divide by A, I just didn't know how to write $x=-A^{-1}b$ (I was writing wrong bracket)

     – gorica Mar 12 '13 at 16:35
  • @gorica This is already shown in my answer to part 3, isn't it? You see, by saying that $x=-A^{-1}b$ is a necessary condition for $x$ to be a minimizer, what we mean is that if a minimum exists, the minimizer has to be $-A^{-1}b$. And by saying that $x=-A^{-1}b$ is a sufficient condition for $x$ to be a minimizer, we mean that the minimum of $F$ does occur at $x=-A^{-1}b$. Now what part 3 shows is exactly this: $\left\langle A(x+A^{-1}b),(x+A^{-1}b)\right\rangle$ is always nonnegative, regardless of $x$, and it is zero at $x=-A^{-1}b$. So $x=-A^{-1}b$ is indeed a minimum point. – user1551 Mar 12 '13 at 16:52
  • which I still don't understand, sorry. What am I asking is: "Is there any theorem that says something about sufficient condition for local extremes? Anything that includes second derivative? (because I have written just that since $F''=2A$ and A is positive definite, $x=-A^{-1}b$ is minimizer. – gorica Mar 12 '13 at 17:40
  • @gorica In this case, you may argue like this: Since the Hessian matrix of $F$ is $2A$, which is positive definite, the critical point $x=-A^{-1}b$ is a local minimum. However, as the Hessian matrix $2A$ is positive definite at every $x$, $F$ is a convex function. Every local minimum of a convex function is a global minimum. Hence $x=-A^{-1}b$ is a global minimum point. – user1551 Mar 12 '13 at 20:46
  • ok, I know what is Hessian matrix, but I don't know how to find it for this function. In general, if Hessian matrix is positive definite, than every local minimum is global minimum? – gorica Mar 12 '13 at 20:57
  • @gorica No. There are three separate facts. (1) If the Hessian matrix evaluated at a critical point is positive definite, then that critical point is a local minimum. (2) If the Hessian matrix is positive definite everywhere, the function is convex. (3) Every local minimum of a convex function is a global minimum. Combining these three facts, your $x=-A^{-1}b$ is a global minimum. – user1551 Mar 12 '13 at 21:02
  • Thank you. I hope I will understand this :) – gorica Mar 12 '13 at 21:12