Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 1 down vote favorite

Given a convex quadratic function $f(x)$, to obtain a solution for which $f(x)$ has minimal value one sets $\nabla f(x)=0$, and solves for $x$. Suppose that the result of differentiation of convex quadratic $f(x)$ is $$Ax=b.$$ Does the solution $x$ satisfying the above always exist? Statement that a solution can be obtained in a least-squares sense imply that $Ax=b$ is not exactly solvable, which means that a global minimum of convex quadratic does not exists (which is not true)(?)

share|improve this question
This looks a lot like homework to me :-) But you approach the problem the wrong way. If you're looking for a minimum, then $f(x)$ is obviously a scalar function and $\nabla f(x)$ is a vector. Thus, there is no relation to any linear system $Ax=b$. (You are thinking of taking the next step and solving the optimality condition $\nabla f=0$ using Newton's method, where you then get the linear system you state with $A=\nabla^2 f$.) – Wolfgang Bangerth Nov 15 '12 at 13:38
@WolfgangBangerth Let $f(x)= tr x'Ax - 2 tr x'b$, $A$ is symmetric. So, minimum of such function is at $x$ satisfying $Ax=b$. Does such $x$ always exist? Does the above $f(x)$ have an optimum? – usero Nov 15 '12 at 14:16
Ah, ok, so you have a quadratic objective function (though I don't understand what the "tr" part refers to -- there is no trace to be taken). But the answer is no. Think, for example of the case where $A=0$ then you have an unbounded objective function that does not have a minimum. You can easily extend this to the case where $A$ is singular and $b$ is not in the range of $A$. – Wolfgang Bangerth Nov 15 '12 at 15:32
@WolfgangBangerth Yes, $tr$ denotes trace. But, does that mean that for a bounded function that has a minimum, $Ax=b$ has a solution? That's why I state that $f(x)$ is a convex quadratic (it is bounded and has a global minimum, or?) – usero Nov 15 '12 at 15:38
1  
About the minimum: Yes, any quadratic function that is bounded from below necessarily has a minimum. But it doesn't have to be unique. For example, the function $f(x_1,x_2)=x_1^2$ is quadratic, convex an bounded from below. But it doesn't have a unique minimum and the corresponding equation you have is singular. What you need is strict convexity which in that case would correspond to positive definiteness of the matrix $A$. Any positive definite matrix is invertible and so $Ax=b$ has a unique solution. – Wolfgang Bangerth Nov 15 '12 at 15:51
show 2 more comments

1 Answer

up vote 4 down vote accepted

$f(x):=\frac{1}{2}x^TGx+c^Tx+\gamma~~~~$ with symmetric Hessian $G$ is bounded below iff $G$ is positive semidefinite and $c$ lies in the column space of $G$. In this case, the equation fior a stationary point is $Gx+c=0~$ and has at least one solution, and all solutions (infinitely many exists if $G$ is singular) are global minimizers of $f$.

If the function is not bounded below $Gx+c=0~$ may or may not have a solution, but if it has one, the solution will never be a local minimizer.

share|improve this answer

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.