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.

I am trying to minimize a convex objective numerically using gradient descent. I select the starting point randomly. I repeat the experiment multiple times. The optimal objective value I get each time is quit the same, but the minimizer is very different. Is it natural? How should it be handled in experiments?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

Yes, this is entirely possible. The fact that a problem is convex just guarantees that any local minimum is a global minimum. You can have many points that reach this global minimum. Intuitively, you can think of a function with a "flat" bottom, somewhat like a bath tub, so two points can be far away but still be minimal.

share|improve this answer
    
But the objective I am minimizing is quadratic. It should not be so flat?! –  user25004 Oct 10 '12 at 2:24
    
@user25004 consider even a low dimensional linear program where the feasible set is a polygon, you can still see intuitively that you can have a "flat" bottom... –  Bitwise Oct 10 '12 at 2:40
    
@user25004, is your quadratic positive definite or merely positive semidefinite? Consider minimizing $f(x,y) = y^2$ over $(x,y)\in\mathbb R^2$. (Or even $f(x,y) = 10^{-6}x^2 + y^2$, what with the slow convergence of gradient descent...) –  Rahul Oct 10 '12 at 3:16
    
@Rahul Narain It is $AX+ AXBX$ where $A$ and $B$ are positive semidefinite. Minimization is over matrix $X$. –  user25004 Oct 10 '12 at 4:32

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.