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$
$\endgroup$
7
-
$\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$ – Wolfgang Bangerth 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$ – Wolfgang Bangerth 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$ – Wolfgang Bangerth Nov 15 '12 at 15:51
|
Show 2 more comments
$\begingroup$
$\endgroup$
$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.
