 Quasiconvex optimization

Quasiconvex optimization minimizes a quasiconvex function over a convex set of feasible points. Its defining advantage is that every sublevel set is convex: for each fixed threshold $t$, asking whether a feasible $x$ satisfies $f(x)\le t$ becomes a convex feasibility problem. The objective function itself need not be a convex function.^[ref]

For an original one-dimensional example, minimizeIts derivative $f^{\prime }(x)=1/(x+2{)}^2$ is positive, so its sublevel sets on this interval are intervals and the function is a quasiconvex function. Yet $f^{\prime \prime }(x)=-2/(x+2{)}^3<0$, so this nonconstant function is strictly concave rather than convex. For fixed $t$, the denominator is positive, and the threshold condition becomes the linear inequalityAt $t=0.4$, no allowed $x$ satisfies it; at $t=0.6$, the allowed interval $0\le x\le 0.5$ does. The true minimum is $f(0)=0.5$.

Interval bisection can search thresholds without directly minimizing the original ratio. Maintain an infeasible lower threshold $L$ and a feasible upper threshold $U$, with a stored feasible witness for $U$. Test $t=(L+U)/2$: on feasibility replace $U$ and its witness; on infeasibility replace $L$. With exact decisions, after $k$ tests the bracket width isStarting with $L=0$, $U=1$ and witness $x=2$, the example's first test finds $x=0$ feasible at $t=0.5$. Later tests below0.5tighten the lower bound.^[ref]

The threshold search is only as reliable as its feasibility problem solver and tolerances. Convexity of the sublevel sets does not supply an inexpensive representation of every such set, and the interval-width guarantee assumes justified feasibility decisions. Returning a feasible witness also matters: an objective bound alone is not an implementable solution.