# unstable optimizer, stable objective

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?

## 1 Answer

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.

• 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