0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But the objective I am minimizing is quadratic. It should not be so flat?! $\endgroup$ – user25004 Oct 10 '12 at 2:24
  • $\begingroup$ @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... $\endgroup$ – Bitwise Oct 10 '12 at 2:40
  • $\begingroup$ @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...) $\endgroup$ – Rahul Oct 10 '12 at 3:16
  • $\begingroup$ @Rahul Narain It is $AX+ AXBX$ where $A$ and $B$ are positive semidefinite. Minimization is over matrix $X$. $\endgroup$ – user25004 Oct 10 '12 at 4:32

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.