Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose a convex quadratic function $f(x)$ is given. To find a minimum of such function, one sets its derivative so zero, and solves for $x$. For instance, suppose that the result of differentiation of $f(x)$ yields the following stationary equation: $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$ is some square matrix, and $b\in\mathbb{R}^n$. Can it be guaranteed that the above linear system always has a solution (the one that exactly satisfies the condition)?

I understand that, in general, $x=A^{-1}b$ may not always exist; however, I wonder if a solution satisfying $Ax=b$ exists, given that the system is a result of a derivative of a convex quadratic function. Stating that a solution does not exist implies that a global optimum of a convex quadratic function does not exist (which is not true?). So, if $A$ is non-invertible, but a solution exist, one would find it by least-squares. But my question is if such a solution satisfies $Ax=b$ (obtained as above).

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Since your convex function is quadratic, it is clear that $A$ is either positive definite or positive semi-definite. If $A$ is positive definite, a unique solution exists and is given by $x=A^{-1}b$. If $A$ is not full rank, then if $b~\epsilon ~range(A)$, then a solution exists (unique or infinitely many), else you will have to go for the least squares solution.

share|improve this answer
    
I wonder about the statement on the least squares solution. If that is implying that $x$ might sometimes exist only is least-squares sense, then that would mean that a global optimum of a convex quadratic function does not exist (which is not true?). Or, are you stating that a least-squares is the way to obtain the solution (which would satisfy $Ax=b$)? –  user506901 Nov 14 '12 at 16:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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