= 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)\leq t$ becomes a convex <feasibility problem>. The <objective function> itself need not be a <convex function>.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[Section4.2.5, printed pp144–145]{ref}
For an original one-dimensional example, minimize
$$
f(x)=\frac{x+1}{x+2},\qquad 0\leq x\leq2.
$$
Its derivative $f'(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''(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 inequality
$$
(1-t)x\leq2t-1.
$$
At $t=0.4$, no allowed $x$ satisfies it; at $t=0.6$, the allowed interval $0\leq x\leq0.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 is
$$
\frac{U_0-L_0}{2^k}.
$$
Starting 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.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[Section4.2.5, Algorithm4.1, bisection for quasiconvex optimization]{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.
Back to article page
