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.

Let $Q\in\mathbb{R^{dxd}}$ and $A\in\mathbb{R^{d'xd}}$ be two matrixes and $b\in\mathbb{R^d}$, $c\in\mathbb{R^{d'}}$. Suppose $d'\lt d $. For $x\in\mathbb{R^d}$.

Minimize $$f(x)= \frac{1}{2}x^TQx-b^Tx\qquad \text{subject to }Ax=c.$$ Prove that every local minimum is also a global minimum.

Edit ok heres where ive gotten so far,:

Suppose there exists a point $x_1$ such that $f(x_1)\lt f(x_0)$ for $x_0$, a minimum.

Consider the function b(s) = (1/2)x(s).Qx(s) -b.x(s) where x(s)=(1-s)$x_0$ + $x_1$s,

I want to show that the gradient of b(0) is zero but im having trouble simplifying the gradient of this equation b(s)=$(1/2)\sum_{j=1}^d x_j(s) \sum_{i=1}^d Q_{ij}x_i(s)$.

share|improve this question
    
Didn't you post this exact question a few hours ago? –  user7530 Jan 27 '13 at 23:09
    
yes, I re-posted it from before –  bobdylan Jan 27 '13 at 23:12
2  
@bobdylan I don't think you're allowed to do that –  Rustyn Jan 27 '13 at 23:13
    
oh, ok, sorry my bad. –  bobdylan Jan 27 '13 at 23:14
2  
Check that you are optimizing a convex function over a set that is convex and without boundary. –  Louis Jan 27 '13 at 23:35

1 Answer 1

up vote 2 down vote accepted

I don't understand why you want to consider $b(s)$. To show that every local minimum is a global minimum, you may proceed as follows. First, if $Ax=c$ has a solution $x_0$, then the set of solutions to $Ax=c$ are given by $x=x_0+Ky$ where the columns of $K$ form a basis of $\ker A$. For such $x$, $$ f(x)=\frac12(x_0+Kx)^TQ(x_0+Kx)-b^T(x_0+Kx)=\frac12y^TK^THKy-u^Ty+r=g(y) $$ for some constant vector $u$ and some constant scalar $r$, and $H$ is the symmetric part of $Q$. So, the constrained minimization of $f$ is equivalent to the unconstrained minimization of $g$, which is a usual least square problem. Since all local minima are global minima in a usual least square problem, the same also holds in the constrained case. (Note, however, that this doesn't mean a local/global minimum exists. In the nontrivial case, a local minimum of $g$ exists if and only if $Ax=c$ is solvable and $K^THK$ is positive semidefinite.)

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.