1
$\begingroup$

To my knowledge, if $A \in \mathbf{S}^n_{++}$, then given any $b \in \mathbb{R}^n$, the system of linear equations $Ax = b$ has a unique solution $x^* \in \mathbb{R}^n$. Moreover, the solution $x^* \in \mathbb{R}^n$ of $Ax = b$ minimizes the objective function $$f(x) = \frac{1}{2}x^TAx - b^Tx$$ It is known that $f$ is a convex smooth function. The gradient and the Hessian of $f$ are correspondingly $$\nabla f(x) = Ax - b$$ $$\nabla^2 f(x) = A \succeq 0$$ So in fact the unique solution $x^*$ of $Ax = b$ satisfies the optimality conditions. Although it is stupid, we can use any convex optimization method on $f$ in order to find the solution $x^*$.


Now my question is what if $A$ is a general nonsingular square matrix (not necessarily SPD) and we follow the same idea to define an objective function $$f(x) = \frac{1}{2}x^TAx - b^Tx$$ where $b \in R(A) = \mathbb{R}^n$. Then

  1. Is the unique solution $x^*$ of $Ax = b$ an optimal point of $f$?
  2. What kind of optimization methods would converge to $x^*$ given any initial guess (with the fastest rate)?
  3. Any improvements if $A$ has a positive real symmetric part?

My guess for the first question is $x^*$ may be a saddle point of $f$ which satisfies the first-order optimality condition, but not the second-order. I don't know anything about non-convex optimization so I have no ideas for the second and the third question. I know there are numerical linear algebra methods like conjugate gradient which converges for SPD matrix and GMRES which converges for any matrix, but I don't have much knowledge about the underlying principle and which methods are the best ones either.

Any ideas and reference are welcome. Thanks in advance. :)

$\endgroup$
  • 2
    $\begingroup$ You can without loss of generality assume that $A$ is symmetric. if $A$ is not positive semi-definite then the function is not bounded below and so the minimum is $-\infty$. $\endgroup$ – Thoth Jun 16 '15 at 4:59
  • $\begingroup$ Well if $Ax=b$, then $f(x^*) = x'Ax - x'Ax = 0$. If $A$ is not PSD, then I think it would be pretty easy to find counter-examples where $f(x)<0$ for some $A$ and some $x$... $\endgroup$ – Benjamin Lindqvist Jul 29 '15 at 7:57
  • $\begingroup$ I understand the solution is not an optimality point in general, and most optimization methods I learn serve to find the optimality point. But is there any method that could converge to the saddle points, provided my first hypothesis is correct? Also, would it be easier to search for the point if $A$ is positive real? $\endgroup$ – Empiricist Jul 29 '15 at 8:14
  • $\begingroup$ If you are in the first place interested in solving $Ax=b$ then why not to consider minimizing $f(x)=\|Ax-b\|^2$ which is a nice convex function with existing global minimum? $\endgroup$ – A.Γ. Aug 3 '15 at 14:43
  • $\begingroup$ Maybe I am wrong because I haven't read a book or take a course about it. Please correct me if I am wrong: I think it is essentially solving the normal equation. We can use, say, conjugate gradient method, but the condition number of the system is $\kappa(A)^2$ which is not preferred. Is there an efficient way to minimize the residual instead? $\endgroup$ – Empiricist Aug 4 '15 at 1:48
1
$\begingroup$

In general you should investigate on iterative methods to solve $Ax=b$. If $A$ is not positive definite, there are provable no cheap methods. Rate of convergence and effective complexity depends strongly on the structure of $A$ and preconditioning is almost a must.

There are fix point iteration based methods and Krylov space based methods (like CG). A good starting point is Wikipedia: https://en.wikipedia.org/wiki/Iterative_method

Fun fact aside: You should avoid applying CG on the normal equation for large sized or ill conditioned $A$, as the condition of $A^T A$ is the squared condition of $A$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I am particularly interested in your saying "there are provable no cheap methods". Can I have some classical text which has a discussion on this? I know very little about Krylov subspace methods. Is there a consensus which iterative method is the best for non-symmetric matrices? I basically only know GMRES is a suitable candidate. Again, do we have special results/methods for matrices $A = S + H$ where $S \in \mathbb{S}^n_{++}$ and $H$ is skew-symmetric? Last question: does Krylov subspace methods, say CG, has a relation/derivation from methods in convex optimization? $\endgroup$ – Empiricist Jul 31 '15 at 2:44
  • $\begingroup$ 1) last first, CG can be interpreted as a gradient methods. there is even a variant for $C^1$ objective function. However you need a line search. 2) As for iterative solver. I am no expert either. There is a result that says three term recursions like those in CG happen only in positive definite case. It is in fact a variant of gram Schmidt. you should find it in most introductory book about numerical mathematic. 3) there is no consensus about which methods are best. in general preconditioning is the key for any method. 4) I know nothing about your particular case. however I am no expert. $\endgroup$ – user251257 Jul 31 '15 at 2:57
0
$\begingroup$

There are several mistakes in the body of question.

  1. $\nabla(f)(x)=2Ax-b$.

Assume that $A$ is a square matrix. Then $x^*$ is a critical point of $f$ iff $(A+A^T)x^*=b$; as Thoth wrote, putting $A:=A+A^T$, we may assume that $A$ is symmetric, $f(x)=1/2x^TAx-b^Tx$ and the required equation becomes (*) $Ax^*=b$.

2 $A$ must be invertible, otherwise there is no solutions or an infinity of solutions in $x^*$.

Your equation (*) is equivalent to $Bx^*=c$ where $B=A^2$ -a symmetric $> 0$ matrix- and $c=Ab$. In this way, the second problem is reduced to the first one: find the minimum of $1/2x^TBx-c^Tx$.

$\endgroup$
  • $\begingroup$ Thanks for pointing out my mistakes. For your second point, I suppose you mean the normal equation $A^TAx = A^Tb$, instead of $A^2$. This may lead to the CGNR method, etc. Please let me ask one more question: what if I want to avoid calculating the transpose, even to a vector, as my matrix has an order up to $10^6$? $\endgroup$ – Empiricist Jul 30 '15 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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