# How to minimize a quasi-convex function in 2 dimensions?

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?

• By "optimize" do you mean maximize or minimize?
– prubin
Mar 4, 2022 at 16:18
• Oh right, I changed it to minimize. Thanks Mar 5, 2022 at 17:31
• 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 ? Mar 5, 2022 at 17:41
• 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? Mar 5, 2022 at 18:25
• How have you established that the black box function is quasi-convex? Mar 6, 2022 at 13:18

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.