1
$\begingroup$

If the analytical form global minimum value of a nonconvex $C^{\infty} f:R^n\to R$ is already known, will it be easier to find its global minimizer $x^*\in R^n$?

$\endgroup$
  • 1
    $\begingroup$ I think you need to specify the case better. Are you asking if anything changes in a practical implementation, or in the theoretical complexity? Are you asking if it is easier to find the solution, or find it and prove that it is optimal (the problem is typically proving optimality. I can give you not only the optimal objective value but the actual optimal solution, but you will not be able to say if it is optimal efficiently) $\endgroup$ – Johan Löfberg Jan 9 '14 at 15:29
  • 1
    $\begingroup$ Typo: Of course, if I give you the optimal solution, I won't tell you the optimal objective, then it would be trivial to check if the candidate was optimal... $\endgroup$ – Johan Löfberg Jan 9 '14 at 15:39
5
$\begingroup$

Within a branch and bound scheme, having a good lower bound on the optimal value can be very helpful in speeding up the algorithm. If your function is Lipschitz continuous with a known Lipschitz constant, and the region of interest can be bounded then you can readily apply branch and bound to the problem.

More generally, the problem is hopeless, since it's possible to hide the global minimum in a $C^{\infty}$ bump that could be located anywhere in $R^{n}$ and which could have arbitrarily small support.

| cite | improve this answer | |
$\endgroup$

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.