Search code examples
convex-optimization

Is negative quadratic function quasiconvex

I read in book (Convex Optimization, boyd) that

quasiconvex (or unimodal) if its domain and all its sublevel sets Sα = {x ∈ dom f | f(x) ≤ α}, for α ∈ R, are convex.

And if and only if f(x) is non-decreasing or non-increasing, f(x) is quasiconvex.

So I wonder if f(x) = -x^2 + 10 is quasiconvex, by definition if α = 5, sublevel sets are two distinct (-inf, a) and (b, +inf), which is not convex set. But according to second rule, f(x) is not monotonic, which makes it quasiconvex. Where did I made a mistake?

Solution

  • Where did I made a mistake?

    This sentence is wrong:

    if and only if f(x) is non-decreasing or non-increasing, f(x) is quasiconvex.

    The implication only goes one way, not both ways.

    That is, a monotone function is definitely quasiconvex, but there are quasiconvex functions which are not monotone. x2 is quasiconvex (and convex) but obviously not monotone.

    I wonder if f(x) = -x2 + 10 is quasiconvex

    It is not. It is concave (and quasiconcave; all concave functions are quasiconcave).

    It is however unimodal. A unimodal function has the property that it is monotone increasing up to a point, and then monotone decreasing after that. In your example, f(x) is monotone increasing up to f(0), and then monotone decreasing after.

    We say such functions are "unimodal" because we can think of the "mode" of a function as being a local maximum. Unimodal functions have a single local (and therefore global) maximum and no other local maxima. Plainly all downward-opening parabolas are unimodal.

    All unimodal functions are quasiconcave.

    Let's sum up. For a function from reals to reals, pick any two points on the curve. Some definitions:

    • If the line segment connecting them is always entirely on or above the curve, the function is convex.
    • If the line segment connecting them is always entirely on or below the curve, the function is concave.
    • If one of the two points is always the maximum value of the function between the two points, the function is quasiconvex.
    • If one of the two points is always the minimum value of the function between the two points, the function is quasiconcave.

    Also:

    • If the function is monotone increasing up to a maximum point and monotone decreasing after that, it is unimodal.

    Some theorems:

    • Every convex function is quasiconvex.
    • Every concave function is quasiconcave.
    • Every unimodal function is quasiconcave.
    • Every monotone function is quasiconvex.
    • Every monotone function is quasiconcave.
    • The negative of every convex function is concave.
    • The negative of every concave function is convex.
    • The negative of every quasiconvex function is quasiconcave.
    • The negative of every quasiconcave function is quasiconvex.