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)(?)

  • $\begingroup$ 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$.) $\endgroup$ Nov 15 '12 at 13:38
  • $\begingroup$ @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? $\endgroup$
    – usero
    Nov 15 '12 at 14:16
  • $\begingroup$ 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$. $\endgroup$ Nov 15 '12 at 15:32
  • $\begingroup$ @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?) $\endgroup$
    – usero
    Nov 15 '12 at 15:38
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 15 '12 at 15:51

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


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.