2
$\begingroup$

I know that if $f$ is a quasi-convex function in one dimension (that is, $f: \mathbb{R} \to \mathbb{R}$), then we can use the 'golden section' line search to find the optimizer.

Now suppose I have a function $f: \mathbb{R}^2 \to \mathbb{R}$ which is quasi-convex. I seek to minimize $f$. We can assume that we are initially given a bounded axis-aligned rectangle which is guaranteed to contain the minimizer.

Is there an analogy to line search in 2D which I can use to minimize this function?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ By "optimize" do you mean maximize or minimize? $\endgroup$
    – prubin ♦
    Mar 4, 2022 at 16:18
  • $\begingroup$ Oh right, I changed it to minimize. Thanks $\endgroup$
    – Karagounis Z
    Mar 5, 2022 at 17:31
  • $\begingroup$ I don't understand exactly what your problem of interest is, but are you familiar with the Bisection method for quasiconvex optimization, as explained in section 4.2.5 "Quasiconvex optimization" of Boyd and Vandenberghe "Convex Optimization" web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf ? $\endgroup$
    – Mark L. Stone
    Mar 5, 2022 at 17:41
  • $\begingroup$ This is a useful resource. But I don't understand how to practically use his method. Given my quasi-convex function $f$, how can I obtain the functions $\phi_t$ which are required to use the bisection method? $\endgroup$
    – Karagounis Z
    Mar 5, 2022 at 18:25
  • 1
    $\begingroup$ How have you established that the black box function is quasi-convex? $\endgroup$
    – Mark L. Stone
    Mar 6, 2022 at 13:18

1 Answer 1

Reset to default
2
$\begingroup$

Without some differentiability/smoothness requirements for $f$ beyond just quasi-convexity, I'm not sure if there are globally convergent analogs to golden section search. If you are willing to live with the possibility of convergence to a suboptimal point, there is the Nelder-Mead algorithm, which generates a sequence of simplices in a manner similar to how golden section search generates a sequence of intervals. If you do a search on "Nelder-Mead", you will find literature on some variants that, at least in some cases, may come with convergence guarantees when $f$ is sufficiently smooth.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.