1
$\begingroup$

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).

1 Answers 1

1

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.

  • 0
    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$)?2012-11-14