44.01.04 · optimization-control / 01-convex-sets-functions

Quasiconvex Optimization and the Bisection Method

shipped3 tiersLean: none

Anchor (Master): Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.4, §4.2.5, §4.3.2; Avriel, Diewert, Schaible & Zang 1988 Generalized Concavity (Plenum) Ch. 3, Ch. 6; Stancu-Minasian 1997 Fractional Programming (Kluwer) Ch. 2-4

Intuition Beginner

Some quantities you care about are ratios. Think of fuel efficiency, miles per gallon: distance divided by fuel. Or a company's return on capital: profit divided by money invested. Or the cost per useful part produced. When you optimize a ratio, the thing you are minimizing or maximizing is not a simple bowl shape, so the convex-optimization toolkit does not apply directly. But these problems still have a friendly hidden structure, and this unit is about exploiting it.

The friendly structure is this: even though the ratio itself is not bowl-shaped, the question "can the ratio be brought below the number $t$ ?" is an easy, convex question for each fixed $t$ . Asking whether efficiency can beat a target, or whether cost-per-part can be pushed under a threshold, turns into a standard convex check. So instead of attacking the ratio head-on, you guess a target value and ask the easy yes/no question.

Now comes the search idea. Suppose you ask "can the cost-per-part be below 10?" and the answer is yes. Then you ask "below 5?" If yes again, try lower; if no, the true best is between 5 and 10. Each yes-or-no answer cuts the range of possible best values in half. This halving search is called bisection, the same move you use to guess a number someone is thinking of between 1 and 100 by always splitting the gap.

Because each question halves the uncertainty, you close in fast: ten questions shrink the range by a factor of about a thousand, twenty questions by about a million. You never solve the hard ratio problem; you solve a short sequence of easy convex problems and let the halving do the work. That trade — replace one hard problem by a handful of easy ones — is the whole method, and ratios of linear quantities are its cleanest home, where the easy question is just a linear program.

Visual Beginner

Figure: a horizontal axis of candidate optimal values running from a lower guess l to an upper guess u. The true optimum p-star sits somewhere between. At each step a midpoint is tested with a convex feasibility check; a "feasible" answer pulls the upper end down to the midpoint, an "infeasible" answer pushes the lower end up to the midpoint. The bracket containing p-star halves every step until it is narrower than the tolerance.

  step 0:   l |--------------------*--------------| u      test midpoint m0
                                    p*
  step 1:   l |----------*---------| u   (m0 feasible -> u = m0)
  step 2:        l |-----*----| u        (m1 infeasible -> l = m1)
  step 3:           l |--*--| u          bracket halves each step
                        p*
            ...                           stop when (u - l) < epsilon
            width after k steps = (u0 - l0) / 2^k

Worked example Beginner

Maximize the ratio $\frac{x + 2}{x + 1}$ for $x$ between $0$ and $4$ . We will find the best value by the halving search, treating "can the ratio be at least $t$ ?" as the easy question.

Step 1. Turn the ratio question into a plain one. The denominator $x + 1$ is positive on $[0, 4]$ , so " $\frac{x + 2}{x + 1} \geq t$ " is the same as " $x + 2 \geq t (x + 1)$ ", which rearranges to " $2 - t \geq (t - 1) x$ ". For each fixed $t$ this is a plain linear test on $x$ .

Step 2. Bracket the answer. At $x = 0$ the ratio is $2/1 = 2$ ; at $x = 4$ it is $6/5 = 1.2$ . The best value lies somewhere at or above $2$ , so start with a lower guess $l = 1$ and an upper guess $u = 3$ .

Step 3. Test the midpoint $t = 2$ . The question becomes " $2 - 2 \geq (2 - 1) x$ ", i.e. " $0 \geq x$ ". The only $x$ in range that works is $x = 0$ . So a value of $2$ is achievable: pull the upper guess down, $u = 2$ .

Step 4. Test the new midpoint $t = 1.5$ . Now " $2 - 1.5 \geq (1.5 - 1) x$ ", i.e. " $0.5 \geq 0.5 x$ ", so $x \leq 1$ . Values up to $1$ work, so $1.5$ is achievable too; but $2$ was already achievable and is larger.

What this tells us. The ratio is largest at $x = 0$ , where it equals $2$ , and the halving search keeps confirming targets at or below $2$ while ruling out anything above. We never maximized the ratio directly — each step was a one-line linear check, and bisection steered us to the answer $2$ .

Check your understanding Beginner

Exercise (easy, multiple choice).

Why is "fuel efficiency = distance ÷ fuel" a natural candidate for the bisection method rather than ordinary convex optimization?

A. Because distance and fuel are always positive B. Because a ratio of linear quantities is not bowl-shaped, but the question "can efficiency beat a target?" is an easy linear check C. Because efficiency has no maximum D. Because the problem has no constraints

Hint

Think about what shape the ratio has versus what shape the fixed-target question has.

Answer

B. Feedback-correct: correct — the ratio itself is not convex, but each fixed-target feasibility question is convex (here, linear), which is exactly the setting bisection exploits. Feedback-wrong: positivity of the parts matters only to keep the rearrangement valid; the reason for bisection is that the ratio is not bowl-shaped while the target question is convex.

Formal definition Intermediate+

Throughout, the ambient space is $R^{n}$ with the standard inner product $⟨ a, x ⟩ = \sum_{i = 1}^{n} a_{i} x_{i}$ . Quasiconvexity is recalled from 44.01.01: a function $f : R^{n} \to R$ with convex domain is quasiconvex if every sublevel set $S_{t} = {x \in dom f : f (x) \leq t}$ is convex, equivalently $f (θ x + (1 - θ) y) \leq max {f (x), f (y)}$ for $θ \in [0, 1]$ . It is quasiconcave if $- f$ is quasiconvex, and quasilinear if both.

Definition (quasiconvex program). A quasiconvex optimization problem in standard form is

p^{⋆} = x in f f_{0} (x) subject to f_{i} (x) \leq 0 (i = 1, \dots, m), A x = b,

where the objective $f_{0}$ is quasiconvex and the inequality functions $f_{1}, \dots, f_{m}$ are convex. The feasible set $C = {x : f_{i} (x) \leq 0, A x = b}$ is convex, but $f_{0}$ need not be, so the problem is not convex; what survives is that each sublevel set of $f_{0}$ is convex.

Definition (sublevel representation by a convex family). A function $f_{0}$ admits a representation by a monotone family of convex inequalities if there is a family of functions $ϕ_{t} : R^{n} \to R$ , indexed by $t \in R$ , each convex in $x$ , such that

f_{0} (x) \leq t ⟺ ϕ_{t} (x) \leq 0, and t \leq u ⟹ ϕ_{t} (x) \geq ϕ_{u} (x) for all x .

The first condition says the $0$ -sublevel set of $ϕ_{t}$ is exactly the $t$ -sublevel set $S_{t}$ of $f_{0}$ ; the second (monotone nonincreasing in $t$ ) makes the encoding consistent as $t$ varies. Every quasiconvex $f_{0}$ admits such a family — for instance $ϕ_{t} (x) = 0$ when $f_{0} (x) \leq t$ and $ϕ_{t} (x) = + \infty$ otherwise, whose $0$ -sublevel set is $S_{t}$ — but useful representations use finite, explicitly convex $ϕ_{t}$ (often affine or convex-quadratic in $x$ , affine in $t$ ) ^{[Boyd & Vandenberghe §4.2.5]}.

Definition (convex feasibility subproblem). For a fixed value $t$ , the feasibility problem $F (t)$ asks whether the convex set

{x : ϕ_{t} (x) \leq 0, f_{i} (x) \leq 0 (\forall i), A x = b}

is nonempty. If it is, then $p^{⋆} \leq t$ (a feasible point achieves objective $\leq t$ ); if it is empty, then $p^{⋆} > t$ (with $ϕ_{t}$ monotone, no feasible point reaches value $t$ ). $F (t)$ is a convex feasibility problem because all the defining inequalities are convex.

Definition (linear-fractional program). A linear-fractional program (LFP) minimizes a ratio of affine functions over a polyhedron,

x in f \frac{c ^{⊤} x + d}{e ^{⊤} x + f} subject to G x ⪯ h, A x = b, on the domain e^{⊤} x + f > 0.

The objective is quasiconvex (and quasiconcave, hence quasilinear) on the open halfspace ${x : e^{⊤} x + f > 0}$ , since each sublevel set ${(c^{⊤} x + d) / (e^{⊤} x + f) \leq t} = {c^{⊤} x + d \leq t (e^{⊤} x + f)}$ is a halfspace there. A generalized linear-fractional program replaces the single ratio by a worst-case maximum $max_{i = 1, \dots, K} (c_{i}^{⊤} x + d_{i}) / (e_{i}^{⊤} x + f_{i})$ over a common positivity region $e_{i}^{⊤} x + f_{i} > 0$ , which is again quasiconvex as a pointwise maximum of quasiconvex functions ^{[Boyd & Vandenberghe §4.3.2]}.

Key theorem with proof Intermediate+

The central result establishes that bisection solves a quasiconvex program to any prescribed accuracy in a number of convex feasibility solves logarithmic in the initial bracket width, and that quasiconvexity is exactly what makes the bisection logic sound (each feasibility answer is conclusive on one side).

Theorem (bisection for quasiconvex optimization). Let $f_{0}$ be quasiconvex with a convex feasibility representation $ϕ_{t}$ as above, let the feasible set $C$ be convex, and suppose $p^{⋆} \in [l_{0}, u_{0}]$ with $l_{0} < u_{0}$ initially bracketing the optimal value. Run bisection: at each step set $t = \frac{1}{2} (l + u)$ , solve $F (t)$ , set $u \leftarrow t$ if feasible and $l \leftarrow t$ if infeasible. Then after $k$ iterations $u - l = (u_{0} - l_{0}) / 2^{k}$ , and $p^{⋆} \in [l, u]$ throughout. Consequently, to guarantee $u - l \leq ε$ it suffices to perform

k = ⌈ lo g_{2} \frac{u _{0} - l _{0}}{ε} ⌉

iterations, each a single convex feasibility solve.

Proof. Invariant. We show $l \leq p^{⋆} \leq u$ holds before and after every step. It holds at step $0$ by hypothesis. Suppose it holds with current bracket $[l, u]$ and let $t = \frac{1}{2} (l + u)$ .

If $F (t)$ is feasible, some $x$ satisfies $ϕ_{t} (x) \leq 0$ together with the constraints, so by the representation $f_{0} (x) \leq t$ and $x \in C$ ; hence $p^{⋆} \leq f_{0} (x) \leq t$ . Updating $u \leftarrow t$ preserves $p^{⋆} \leq u$ , and $l$ is unchanged so $l \leq p^{⋆}$ still holds.

If $F (t)$ is infeasible, no feasible point has $ϕ_{t} (x) \leq 0$ , i.e. no $x \in C$ has $f_{0} (x) \leq t$ ; therefore $p^{⋆} > t$ . Here quasiconvexity is what guarantees the answer is conclusive: $S_{t} \cap C$ is the intersection of the convex sublevel set $S_{t}$ with the convex set $C$ , so it is convex, and a convex feasibility solver returns a definite empty/nonempty verdict rather than getting trapped in a nonconvex component. Updating $l \leftarrow t$ preserves $l \leq p^{⋆}$ , and $u$ is unchanged so $p^{⋆} \leq u$ still holds. In both branches the invariant survives.

Geometric width decay. Each branch replaces one endpoint by the midpoint, so the new width is exactly half: $u^{'} - l^{'} = \frac{1}{2} (u - l)$ . By induction $u_{k} - l_{k} = (u_{0} - l_{0}) / 2^{k}$ .

Iteration count. The width drops to $\leq ε$ as soon as $(u_{0} - l_{0}) / 2^{k} \leq ε$ , i.e. $2^{k} \geq (u_{0} - l_{0}) / ε$ , i.e. $k \geq lo g_{2} ((u_{0} - l_{0}) / ε)$ . The least integer $k$ meeting this is $⌈ lo g_{2} ((u_{0} - l_{0}) / ε)⌉$ . Since the invariant gives $p^{⋆} \in [l, u]$ at termination, the midpoint $\frac{1}{2} (l + u)$ estimates $p^{⋆}$ within $ε /2$ . $□$

Bridge. This theorem builds toward the algorithmic core of every method that converts a nonconvex-looking objective into a sequence of convex solves, and appears again in the linear-fractional reductions below and in the parametric (Dinkelbach) view of fractional programming. This is exactly the device that generalises the elementary number-guessing game to optimization: the unknown is the scalar $p^{⋆}$ , each feasibility query is one comparison, and convexity of the sublevel sets is what makes the comparison return a side. The foundational reason bisection needs quasiconvexity and not full convexity is that only the sublevel sets, not the epigraph, must be convex — a strictly weaker demand identified in 44.01.01 — which widens the reach of convex feasibility solvers to ratios and worst-case ratios. Putting these together, the convex feasibility subproblem $F (t)$ is dual to the value question through the duality theory of 44.02.01: an infeasibility certificate for $F (t)$ is a dual proof that $p^{⋆} > t$ , so each bisection step is backed by a verifiable certificate, and the bridge is the sublevel-set family $ϕ_{t}$ through which a quasiconvex program becomes $⌈ lo g_{2} ((u_{0} - l_{0}) / ε)⌉$ convex programs.

Exercises Intermediate+

Exercise 1 (easy, symbolic).

Show that for the linear-fractional objective $f_{0} (x) = (c^{⊤} x + d) / (e^{⊤} x + f)$ on the domain $e^{⊤} x + f > 0$ , the sublevel set ${x : f_{0} (x) \leq t}$ is a halfspace, and write the affine representative $ϕ_{t}$ .

Hint

Multiply through by the positive denominator; the inequality direction is preserved.

Answer

Since $e^{⊤} x + f > 0$ , the inequality $(c^{⊤} x + d) / (e^{⊤} x + f) \leq t$ is equivalent to $c^{⊤} x + d \leq t (e^{⊤} x + f)$ , i.e. $(c - t e)^{⊤} x + (d - t f) \leq 0$ . So $ϕ_{t} (x) = (c - t e)^{⊤} x + (d - t f)$ is affine in $x$ (and affine in $t$ ), and its $0$ -sublevel set is the halfspace ${x : (c - t e)^{⊤} x \leq t f - d}$ . As $t$ increases, the coefficient $- t e$ and intercept $- t f$ shift the halfspace, and one checks $ϕ_{t} (x)$ is nonincreasing in $t$ on the domain because $\partial ϕ_{t} / \partial t = - (e^{⊤} x + f) < 0$ . Each feasibility subproblem is therefore an LP.

Exercise 3 (medium, symbolic).

Carry out the Charnes-Cooper transformation: show that the LFP $min (c^{⊤} x + d) / (e^{⊤} x + f)$ subject to $G x ⪯ h$ , $e^{⊤} x + f > 0$ becomes the LP $min c^{⊤} y + d z$ subject to $G y ⪯ h z$ , $e^{⊤} y + f z = 1$ , $z \geq 0$ , under the substitution $y = x / (e^{⊤} x + f)$ , $z = 1/ (e^{⊤} x + f)$ .

Hint

Scale every constraint by the positive quantity $z = 1/ (e^{⊤} x + f)$ and use $x = y / z$ .

Answer

Set $z = 1/ (e^{⊤} x + f) > 0$ and $y = z x$ . Then $e^{⊤} y + f z = z (e^{⊤} x + f) = 1$ , the normalization. The objective becomes $(c^{⊤} x + d) / (e^{⊤} x + f) = z (c^{⊤} x + d) = c^{⊤} (z x) + d z = c^{⊤} y + d z$ . The polyhedral constraint $G x ⪯ h$ multiplied by $z > 0$ gives $G (z x) ⪯ h z$ , i.e. $G y ⪯ h z$ . Conversely, any $(y, z)$ feasible with $z > 0$ recovers $x = y / z$ feasible for the original with the same objective value. The case $z = 0$ corresponds to recession directions of the feasible polyhedron and is admitted as a limit (or excluded when the denominator is bounded away from $0$ ). Thus the LFP and LP have equal optimal values, and the ratio objective is solved by a single LP — no bisection needed in the linear-fractional case.

Exercise 4 (medium, symbolic).

Prove that the pointwise maximum $g (x) = max_{i = 1, \dots, K} f_{i} (x)$ of quasiconvex functions $f_{i}$ is quasiconvex, and deduce that a generalized linear-fractional objective is quasiconvex.

Hint

A sublevel set of a maximum is an intersection of sublevel sets.

Answer

For any $t$ , ${x : g (x) \leq t} = {x : max_{i} f_{i} (x) \leq t} = ⋂_{i = 1}^{K} {x : f_{i} (x) \leq t}$ , an intersection of the convex sublevel sets of the quasiconvex $f_{i}$ , hence convex (intersection of convex sets is convex, 44.01.01). Convex sublevel sets at every level give quasiconvexity of $g$ . For the generalized LFP, each $f_{i} (x) = (c_{i}^{⊤} x + d_{i}) / (e_{i}^{⊤} x + f_{i})$ is quasiconvex on the common region ${e_{i}^{⊤} x + f_{i} > 0 \forall i}$ (Exercise 1), so their maximum is quasiconvex; the feasibility subproblem at level $t$ is the LP ${(c_{i} - t e_{i})^{⊤} x + (d_{i} - t f_{i}) \leq 0 \forall i} \cap {G x ⪯ h}$ , again solvable by bisection over LPs.

Exercise 5 (medium, symbolic).

Show that the sum of two ratios $\frac{c _{1}^{⊤} x + d _{1}}{e _{1}^{⊤} x + f _{1}} + \frac{c _{2}^{⊤} x + d _{2}}{e _{2}^{⊤} x + f _{2}}$ need not be quasiconvex, and explain why bisection does not directly apply to sum-of-ratios objectives.

Hint

A sublevel set of a sum is not an intersection of sublevel sets; try a one-dimensional example whose sublevel set is disconnected.

Answer

Take $h (x) = \frac{x}{1} + \frac{1}{x}$ on $x > 0$ (each term linear-fractional with positive denominator). Then $h (x) = x + 1/ x$ has $h (1) = 2$ , $h (2) = 2.5$ , $h (1/2) = 2.5$ , and $h \to \infty$ at both ends; its sublevel set ${x > 0 : h (x) \leq 2.4}$ is two disjoint intervals around the two points where $h = 2.4$ , hence not convex. So $h$ is not quasiconvex even though each summand is. Because the sublevel sets are nonconvex, the feasibility subproblem $F (t)$ is no longer convex, and the bisection invariant (a conclusive empty/nonempty verdict) breaks; sum-of-ratios is in fact NP-hard in general and needs branch-and-bound or specialized global methods, not plain bisection.

Exercise 6 (hard, symbolic).

Establish the Dinkelbach parametric characterization: for the fractional program $t^{⋆} = min_{x \in C} \frac{p ( x )}{q ( x )}$ with $q > 0$ on $C$ , define $F (t) = min_{x \in C} (p (x) - t q (x))$ . Show $F$ is nonincreasing, and that $t^{⋆}$ is the unique root $F (t^{⋆}) = 0$ .

Hint

$p (x) / q (x) \leq t$ is equivalent to $p (x) - tq (x) \leq 0$ when $q (x) > 0$ . Relate the sign of $F (t)$ to whether $t$ over- or under-estimates $t^{⋆}$ .

Answer

For each $x \in C$ , $p (x) - tq (x)$ is affine and strictly decreasing in $t$ (slope $- q (x) < 0$ ); $F$ is a pointwise minimum of strictly decreasing affine functions, hence nonincreasing (in fact concave) in $t$ . If $t < t^{⋆}$ then for every $x$ , $p (x) / q (x) \geq t^{⋆} > t$ , so $p (x) - tq (x) > 0$ , giving $F (t) > 0$ . If $t > t^{⋆}$ , the minimizer $x^{⋆}$ of the ratio gives $p (x^{⋆}) / q (x^{⋆}) = t^{⋆} < t$ , so $p (x^{⋆}) - tq (x^{⋆}) < 0$ and $F (t) < 0$ . At $t = t^{⋆}$ , $p (x) - t^{⋆} q (x) \geq 0$ for all $x$ with equality at $x^{⋆}$ , so $F (t^{⋆}) = 0$ . Monotonicity makes the root unique, and $F (t^{⋆}) = 0$ is the Dinkelbach equation; Newton's method on $F$ converges superlinearly, an alternative to bisection that uses the convex value rather than just feasibility.

Exercise 7 (hard, symbolic).

Show that an infeasibility certificate for the convex subproblem $F (t)$ — produced by Lagrangian duality 44.02.01 — proves $p^{⋆} > t$ , and explain how this turns each bisection step into a verifiable certificate rather than a black-box answer.

Hint

A separating hyperplane / Farkas-type multiplier exhibiting that ${ϕ_{t} (x) \leq 0} \cap C = \emptyset$ is a dual object; relate it to $p^{⋆}$ .

Answer

$F (t)$ is the convex system $ϕ_{t} (x) \leq 0$ , $f_{i} (x) \leq 0$ , $A x = b$ . When it is infeasible, a theorem of the alternative (the convex Farkas / Lagrangian-duality result of 44.02.01) supplies multipliers $μ \geq 0$ , $λ ⪰ 0$ , $ν$ , not all zero, with $μ ϕ_{t} (x) + \sum_{i} λ_{i} f_{i} (x) + ν^{⊤} (A x - b) > 0$ for all $x$ in the domain — a single inequality certifying emptiness. Because $ϕ_{t} (x) \leq 0 ⟺ f_{0} (x) \leq t$ , emptiness of the system means no feasible $x$ attains $f_{0} (x) \leq t$ , i.e. $p^{⋆} > t$ . The multipliers are a short, independently checkable proof of that strict bound, so a verifier need not re-solve $F (t)$ ; it only checks the certificate inequality. Each bisection step thus narrows $[l, u]$ with a dual proof attached, which is what makes bisection trustworthy as a building block in certified optimization.

Exercise 8 (hard, symbolic).

Consider the worst-case fractional problem $min_{x} max_{i} \frac{c _{i}^{⊤} x + d _{i}}{e _{i}^{⊤} x + f _{i}}$ over $G x ⪯ h$ with all $e_{i}^{⊤} x + f_{i} > 0$ . Write the feasibility subproblem $F (t)$ explicitly, confirm it is an LP, and state the resulting overall complexity in terms of LP solves.

Hint

Use Exercise 1 on each ratio at level $t$ ; intersect the resulting halfspaces with the polyhedron.

Answer

At level $t$ , the objective is $\leq t$ iff every ratio is $\leq t$ iff $(c_{i} - t e_{i})^{⊤} x + (d_{i} - t f_{i}) \leq 0$ for all $i$ . So $F (t)$ asks whether the polyhedron

{x : (c_{i} - t e_{i})^{⊤} x \leq t f_{i} - d_{i} (i = 1, \dots, K), G x ⪯ h}

is nonempty — a linear feasibility problem (an LP with a dummy objective). Each step is one LP; bisection to tolerance $ε$ over an initial bracket $[l_{0}, u_{0}]$ takes $⌈ lo g_{2} ((u_{0} - l_{0}) / ε)⌉$ LP solves. Each LP has $K$ fractional-derived constraints plus the rows of $G$ , and the positivity hypotheses $e_{i}^{⊤} x + f_{i} > 0$ are maintained on the domain. The total cost is logarithmic in the accuracy and polynomial per step, so the worst-case fractional program is solved in polynomial time despite its nonconvex-looking objective.

Advanced results Master

The representation theorem and the geometry of quasiconvex sublevel families

A function is quasiconvex if and only if it admits a family ${ϕ_{t}}$ of convex functions, nonincreasing in $t$ , with ${x : ϕ_{t} (x) \leq 0} = S_{t}$ for every $t$ . The forward direction packages the convex sublevel sets as the indicator-style family $ϕ_{t} = ι_{S_{t}}$ relaxed to a finite convex gauge; the converse reads convexity of every $S_{t} = {ϕ_{t} \leq 0}$ directly off convexity of each $ϕ_{t}$ , and quasiconvexity follows from convex sublevel sets at all levels. The content of the theorem is constructive: for the algorithmically interesting classes the $ϕ_{t}$ are jointly structured — affine in $x$ for linear-fractional objectives, convex-quadratic for quadratic-over-affine objectives, linear matrix inequalities for the largest-generalized-eigenvalue objective $λ_{m a x} (A (x), B (x))$ with $B (x) ≻ 0$ . The bisection method runs over whatever convex class the $ϕ_{t}$ inhabit, so the same logarithmic outer loop solves a quasiconvex program over LPs, QPs, SOCPs, or SDPs depending only on the representation, which is why quasiconvex modeling sits one layer above the conic hierarchy of 44.05.01.

First-order and differentiable characterizations of quasiconvexity

For differentiable $f_{0}$ on a convex open set, quasiconvexity is equivalent to the first-order condition $f_{0} (y) \leq f_{0} (x) ⟹ ⟨ \nabla f_{0} (x), y - x ⟩ \leq 0$ : along any direction in which the function does not increase the gradient cannot point uphill. This is strictly weaker than the convex supporting-line inequality of 44.01.01 and admits stationary points that are not global minimizers, so an unconstrained gradient zero is not by itself decisive — the reason bisection, which interrogates sublevel sets globally, is preferred to gradient descent for genuinely quasiconvex objectives. The twice-differentiable refinement involves the bordered Hessian: $f_{0}$ is quasiconvex on a convex set if, restricted to the subspace ${v : ⟨ \nabla f_{0} (x), v ⟩ = 0}$ , the Hessian is positive semidefinite, encoded by sign conditions on the leading principal minors of the matrix $\begin{psmallmatrix} 0 & \nabla f_0^\top \\ \nabla f_0 & \nabla^2 f_0 \end{psmallmatrix}$ . These conditions are the generalized-concavity analogue of the PSD-Hessian test and are the working criteria in ^{[Avriel, Diewert, Schaible & Zang Ch. 3]}.

Fractional programming: Charnes-Cooper, Dinkelbach, and the conic generalizations

Linear-fractional programs collapse entirely to LPs by the Charnes-Cooper change of variables ^{[Charnes & Cooper 1962]}, so they need no bisection; the homogenization $y = x / (e^{⊤} x + f)$ , $z = 1/ (e^{⊤} x + f)$ is the projective trick that linearizes a single ratio over a polyhedron. For nonlinear ratios $p (x) / q (x)$ with $p$ convex, $q$ concave, and both positive on a convex feasible set, the objective is quasiconvex, and two routes coexist: bisection on the optimal value, solving a convex feasibility problem per step, and the Dinkelbach parametric method ^{[Dinkelbach 1967]}, solving the convex optimization $F (t) = min_{x} (p (x) - tq (x))$ and updating $t$ by Newton's method on the root equation $F (t) = 0$ , which converges superlinearly versus bisection's linear (one-bit-per-step) rate. The generalized fractional program $min_{x} max_{i} p_{i} (x) / q_{i} (x)$ retains quasiconvexity and is handled by a Dinkelbach-type method on $max_{i} (p_{i} - t q_{i})$ ; its conic incarnations — the linear-fractional SOCP and the generalized-eigenvalue SDP $min t$ s.t. $A (x) ⪯ tB (x)$ , $B (x) ≻ 0$ — are exactly the bisection-over-conic-feasibility programs that modeling systems compile quasiconvex ratios into.

Quasiconvexity that is not convexity: where the extra generality buys problems

The value of the quasiconvex layer is that it captures objects no convex reformulation reaches without lifting. The condition number $λ_{m a x} (X) / λ_{m i n} (X)$ of a positive-definite matrix depending affinely on $x$ , the largest generalized eigenvalue, the maximum-of-ratios scheduling objectives, and the Von Neumann growth-rate model of an expanding economy are quasiconvex (or quasiconcave) without being convex; each becomes a sequence of SDP or LP feasibility checks under bisection. The price is that quasiconvexity does not compose the way convexity does: sums of quasiconvex functions are generally not quasiconvex (Exercise 5), so there is no quasiconvex analogue of the disciplined-convex-programming additive calculus of 44.01.01. Quasiconvex modeling is therefore organized around a fixed list of recognized quasiconvex atoms combined only by the operations that preserve quasiconvexity — pointwise maximum, composition with a monotone map, and the ratio and perspective constructions — rather than by free addition.

Synthesis. The sublevel-family representation is exactly the device that generalises the epigraph encoding of 44.01.01 from convex to quasiconvex objectives: where a convex function is its convex epigraph, a quasiconvex function is its nested family of convex sublevel sets, and the central insight of this unit is that optimization over that family is bisection on a single scalar. The foundational reason the method works with only quasiconvexity is that bisection never needs the objective's epigraph to be convex — it needs only that each level question $F (t)$ be a convex feasibility problem, which the monotone family $ϕ_{t}$ guarantees, and this is dual to the duality theory of 44.02.01 in that each infeasible level supplies a certificate $p^{⋆} > t$ . Putting these together, the Charnes-Cooper transformation linearizes the single-ratio case to one LP, the Dinkelbach parametric root-finding trades bisection's linear convergence for Newton's superlinear convergence on the convex value function $F (t)$ , and the generalized-eigenvalue and worst-case-ratio problems lift the whole construction onto the self-dual cones of 44.05.01; the bridge is the monotone convex family $ϕ_{t}$ , the single object through which a nonconvex ratio objective becomes a logarithmic sequence of convex programs, and it appears again in the central-path homotopy of interior-point methods and in every parametric optimization scheme that solves a hard problem by sweeping a scalar through convex subproblems.

Full proof set Master

Proposition 1 (correctness and complexity of bisection). Under the hypotheses of the Key theorem, bisection terminates after $⌈ lo g_{2} ((u_{0} - l_{0}) / ε)⌉$ convex feasibility solves with a bracket $[l, u]$ of width $\leq ε$ containing $p^{⋆}$ ; the midpoint estimates $p^{⋆}$ within $ε /2$ .

Proof. The bracket invariant $l \leq p^{⋆} \leq u$ and the exact halving $u_{k} - l_{k} = (u_{0} - l_{0}) / 2^{k}$ are established in the Key theorem. The width meets $\leq ε$ at the least $k$ with $2^{k} \geq (u_{0} - l_{0}) / ε$ , namely $k = ⌈ lo g_{2} ((u_{0} - l_{0}) / ε)⌉$ . With $p^{⋆} \in [l, u]$ and $u - l \leq ε$ , the midpoint $m = \frac{1}{2} (l + u)$ satisfies $∣ m - p^{⋆} ∣ \leq \frac{1}{2} (u - l) \leq ε /2$ . Each iteration solves exactly one $F (t)$ , a convex feasibility problem. $□$

Proposition 2 (quasiconvexity $⟺$ convex sublevel sets $⟺$ a monotone convex family). For $f_{0} : R^{n} \to R$ with convex domain, the following are equivalent: (a) $f_{0}$ is quasiconvex; (b) every sublevel set $S_{t}$ is convex; (c) there is a family ${ϕ_{t}}$ , each convex in $x$ and nonincreasing in $t$ , with ${x : ϕ_{t} (x) \leq 0} = S_{t}$ for all $t$ .

Proof. (a) $\Leftrightarrow$ (b) is the definition recalled from 44.01.01: $f_{0} (θ x + (1 - θ) y) \leq max {f_{0} (x), f_{0} (y)}$ holds for all $x, y, θ$ if and only if each $S_{t}$ is convex. (b) $\Rightarrow$ (c): for each $t$ let $ϕ_{t} = ι_{S_{t}}$ , the convex indicator that is $0$ on the convex set $S_{t}$ and $+ \infty$ off it; its $0$ -sublevel set is $S_{t}$ , it is convex in $x$ , and since $t \leq u$ implies $S_{t} \subseteq S_{u}$ (sublevel sets nest upward) we have $ι_{S_{t}} \geq ι_{S_{u}}$ , the required monotonicity. (c) $\Rightarrow$ (b): if $ϕ_{t}$ is convex then ${x : ϕ_{t} (x) \leq 0}$ is a sublevel set of a convex function, hence convex; this set equals $S_{t}$ , so each $S_{t}$ is convex. The indicator family proves existence; finite, explicitly convex $ϕ_{t}$ exist for the structured classes and are what bisection actually consumes. $□$

Proposition 3 (Charnes-Cooper equivalence). Let the LFP be $in f {(c^{⊤} x + d) / (e^{⊤} x + f) : G x ⪯ h}$ on ${e^{⊤} x + f > 0}$ , assumed nonempty with the denominator bounded away from $0$ on the feasible set. Then it has the same optimal value as the LP $in f {c^{⊤} y + d z : G y ⪯ h z, e^{⊤} y + f z = 1, z \geq 0}$ , and optimal solutions correspond via $y = z x$ , $z = 1/ (e^{⊤} x + f)$ .

Proof. ( $\leq$ ) Given feasible $x$ for the LFP, set $z = 1/ (e^{⊤} x + f) > 0$ and $y = z x$ . Then $e^{⊤} y + f z = z (e^{⊤} x + f) = 1$ and $G y = z G x ⪯ z h = h z$ (using $z > 0$ ), so $(y, z)$ is LP-feasible with objective $c^{⊤} y + d z = z (c^{⊤} x + d) = (c^{⊤} x + d) / (e^{⊤} x + f)$ , the LFP objective at $x$ . Thus the LP optimum is $\leq$ the LFP optimum. ( $\geq$ ) Given LP-feasible $(y, z)$ with $z > 0$ , set $x = y / z$ . Then $e^{⊤} x + f = (e^{⊤} y + f z) / z = 1/ z > 0$ and $G x = G y / z ⪯ h$ , so $x$ is LFP-feasible with objective $(c^{⊤} x + d) / (e^{⊤} x + f) = z (c^{⊤} (y / z) + d) = c^{⊤} y + d z$ , the LP objective. So the LFP optimum is $\leq$ the LP optimum over the $z > 0$ region. The boundedness-away-from- $0$ hypothesis ensures the LP optimum is attained with $z > 0$ rather than only in the $z \to 0^{+}$ recession limit, giving equality and the stated correspondence. $□$

Proposition 4 (Dinkelbach root equation and convergence). Let $C$ be convex compact, $p$ convex, $q$ concave with $q > 0$ on $C$ , and $t^{⋆} = min_{x \in C} p (x) / q (x)$ . With $F (t) = min_{x \in C} (p (x) - tq (x))$ : $F$ is concave, strictly decreasing, $F (t^{⋆}) = 0$ , and the Newton-Dinkelbach iteration $t_{k + 1} = p (x_{k}) / q (x_{k})$ with $x_{k} \in ar g min_{x} (p (x) - t_{k} q (x))$ converges monotonically to $t^{⋆}$ .

Proof. For fixed $x$ , $t \mapsto p (x) - tq (x)$ is affine with slope $- q (x) < 0$ ; $F$ is a pointwise minimum of these, hence concave and (since every slope is $\leq - min_{C} q < 0$ ) strictly decreasing. Sign analysis as in Exercise 6 gives $F (t) > 0$ for $t < t^{⋆}$ , $F (t) < 0$ for $t > t^{⋆}$ , and $F (t^{⋆}) = 0$ with the minimizing $x^{⋆}$ attaining the ratio $t^{⋆}$ ; uniqueness of the root follows from strict monotonicity. For convergence, start with $t_{0} \leq t^{⋆}$ feasible-side; given $t_{k}$ , the minimizer $x_{k}$ of $p - t_{k} q$ has $F (t_{k}) = p (x_{k}) - t_{k} q (x_{k}) \geq 0$ , and the update $t_{k + 1} = p (x_{k}) / q (x_{k})$ satisfies $p (x_{k}) - t_{k + 1} q (x_{k}) = 0 \geq F (t_{k + 1})$ , so $t_{k + 1} \geq t^{⋆}$ is impossible to overshoot below and the sequence increases toward $t^{⋆}$ . Concavity of $F$ makes the update exactly a Newton step on $F (t) = 0$ using a supergradient $- q (x_{k}) \in \partial F (t_{k})$ , yielding superlinear convergence; compactness of $C$ secures attainment of each inner minimum. $□$

Connections Master

The quasiconvexity definition, the convex sublevel sets, and the convexity-preserving operations consumed throughout — pointwise maximum, affine precomposition, perspective, and the intersection of convex sets — are exactly the apparatus of 44.01.01; this unit specializes that apparatus to objectives that are quasiconvex but not convex, where the sublevel-set view rather than the epigraph view is the operative one, and the linear-fractional sublevel halfspaces are the simplest nontrivial instance of its operation calculus.
Each bisection feasibility subproblem $F (t)$ is a convex program whose solvability, and whose infeasibility certificate proving $p^{⋆} > t$ , rest on the Lagrangian-duality and Slater theory of 44.02.01; the dual multipliers turn a black-box feasibility answer into a checkable proof, so the bisection outer loop inherits the certified-optimality guarantees of convex duality at every step.
The conic and semidefinite programs of 44.05.01 are the feasibility classes that bisection runs over when the family $ϕ_{t}$ consists of linear matrix inequalities: the generalized-eigenvalue problem $min t$ s.t. $A (x) ⪯ tB (x)$ , $B (x) ≻ 0$ is the canonical quasiconvex-over-SDP program, and the Charnes-Cooper-linearized LFP is its polyhedral shadow, tying the quasiconvex outer loop to the self-dual cone hierarchy.
The central-path homotopy of interior-point methods sweeps a scalar barrier parameter through a family of convex subproblems exactly as bisection sweeps the value $t$ through the feasibility family $F (t)$ ; both are parametric reductions of a hard problem to a one-parameter path of convex programs, and the Dinkelbach Newton iteration on $F (t) = 0$ is the value-based analogue that interior-point predictor-corrector schemes generalize.

Historical & philosophical context Master

Quasiconvexity emerged from mathematical economics, where indifference curves and the diminishing-marginal-rate-of-substitution principle demanded a class of functions weaker than concave but still guaranteeing convex upper-contour sets. Bruno de Finetti's 1949 study of "stratified" functions and Werner Fenchel's 1953 Princeton lectures isolated quasiconvex and quasiconcave functions as the functions with convex sublevel (respectively superlevel) sets, and the systematic theory of generalized concavity was consolidated by Mordecai Avriel, W. E. Diewert, Siegfried Schaible, and Israel Zang ^{[Avriel, Diewert, Schaible & Zang Ch. 3]} (Plenum, 1988), which catalogued the first-order, bordered-Hessian, and operation-preserving characterizations.

The fractional-programming thread runs in parallel. Abraham Charnes and William Cooper ^{[Charnes & Cooper 1962]} published the projective change of variables in Naval Research Logistics Quarterly (volume 9, 1962, 181-186) that reduces a linear-fractional functional over a polyhedron to a linear program, and Werner Dinkelbach ^{[Dinkelbach 1967]} gave the parametric method in Management Science (volume 13, 1967, 492-498), recasting $max p / q$ as the root of $F (t) = max (p - tq)$ and thereby connecting fractional optimization to root-finding on a concave value function. The bisection-on-the-optimal-value method and its $lo g_{2} ((u - l) / ε)$ complexity were given their modern algorithmic packaging for convex modeling by Stephen Boyd and Lieven Vandenberghe ^{[Boyd & Vandenberghe §4.2.5]} (Cambridge, 2004), where quasiconvex optimization via a sequence of convex feasibility problems became a standard reduction in the disciplined-convex-programming toolkit.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{avriel1988generalized,
  author    = {Avriel, Mordecai and Diewert, Walter E. and Schaible, Siegfried and Zang, Israel},
  title     = {Generalized Concavity},
  series    = {Mathematical Concepts and Methods in Science and Engineering},
  publisher = {Plenum Press},
  year      = {1988}
}

@book{stancuminasian1997fractional,
  author    = {Stancu-Minasian, I. M.},
  title     = {Fractional Programming: Theory, Methods and Applications},
  series    = {Mathematics and Its Applications},
  publisher = {Kluwer Academic Publishers},
  year      = {1997}
}

@article{charnes1962programming,
  author  = {Charnes, Abraham and Cooper, William W.},
  title   = {Programming with Linear Fractional Functionals},
  journal = {Naval Research Logistics Quarterly},
  volume  = {9},
  number  = {3--4},
  pages   = {181--186},
  year    = {1962}
}

@article{dinkelbach1967nonlinear,
  author  = {Dinkelbach, Werner},
  title   = {On Nonlinear Fractional Programming},
  journal = {Management Science},
  volume  = {13},
  number  = {7},
  pages   = {492--498},
  year    = {1967}
}

@book{schaible1981fractional,
  author    = {Schaible, Siegfried and Ibaraki, Toshihide},
  title     = {Fractional Programming},
  publisher = {European Journal of Operational Research},
  year      = {1983}
}

Prerequisites

44.01.01

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.4, §4.2.5 — the sublevel-set picture and bisecting on the optimal value
intermediate: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.4, §4.2.5, §4.3.2; Bazaraa, Sherali & Shetty 2006 Nonlinear Programming (Wiley) §3.5
master: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.4, §4.2.5, §4.3.2; Avriel, Diewert, Schaible & Zang 1988 Generalized Concavity (Plenum) Ch. 3, Ch. 6; Stancu-Minasian 1997 Fractional Programming (Kluwer) Ch. 2-4

References

Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §3.4 quasiconvex functions and the sublevel-set / family-of-convex-inequalities representation; §4.2.5 quasiconvex optimization and the bisection method; §4.3.2 linear-fractional and generalized linear-fractional programming
Avriel, M., Diewert, W. E., Schaible, S. & Zang, I. — Generalized Concavity (Plenum Press, 1988) · Ch. 3 quasiconcave/quasiconvex functions and their characterizations; Ch. 6 fractional and generalized-concave programming
Stancu-Minasian, I. M. — Fractional Programming: Theory, Methods and Applications (Kluwer, 1997) · Ch. 2 linear-fractional programming and the Charnes-Cooper transformation; Ch. 4 generalized fractional programming and the Dinkelbach parametric method
Charnes, A. & Cooper, W. W. — Programming with Linear Fractional Functionals · Naval Research Logistics Quarterly 9 (1962), 181-186 — the change-of-variables reducing a linear-fractional program to a linear program
Dinkelbach, W. — On Nonlinear Fractional Programming · Management Science 13 (1967), 492-498 — the parametric reformulation max f/g = root of F(t) = max (f - t g)

Estimated time

beginner: 16m
intermediate: 42m
master: 78m