Quasiconvex optimization¶

$$ \newcommand{\eg}{{\it e.g.}} \newcommand{\ie}{{\it i.e.}} \newcommand{\argmin}{\operatornamewithlimits{argmin}} \newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb} \newcommand{\mf}{\mathbf} \newcommand{\minimize}{{\text{minimize}}} \newcommand{\argmin}{{\text{argmin}}} \newcommand{\diag}{{\text{diag}}} \newcommand{\cond}{{\text{cond}}} \newcommand{\rank}{{\text{rank }}} \newcommand{\range}{{\mathcal{R}}} \newcommand{\null}{{\mathcal{N}}} \newcommand{\tr}{{\text{trace}}} \newcommand{\dom}{{\text{dom}}} \newcommand{\dist}{{\text{dist}}} \newcommand{\E}{\mathbf{E}} \newcommand{\var}{\mathbf{var}} \newcommand{\Z}{\mathbf{Z}} \newcommand{\R}{\mathbf{R}} \newcommand{\SM}{\mathbf{S}} \newcommand{\ball}{\mathcal{B}} \newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}} $$

Jong-Han Kim (jonghank@inha.ac.kr)

Quasiconvex functions¶

A function $f:\R^n \rightarrow \R$ is quasiconvex if $\dom f$ is convex and the sublevel sets

$$ S_t = \left\{ x \in \dom f \mid f(x) \le t \right\} $$

are convex for all $t$.

• $f$ is quasiconcave if $-f$ is quasiconvex
• $f$ is quasilinear if it is quasiconvex and quasiconcave

Alternative definition¶

A function $f$ is quasiconvex if and only if $\dom f$ is convex and for any $x,y\in\dom f$ with $0\le \theta \le 1$,

$$ f\left(\theta x + (1-\theta)y\right) \le \max\left\{f(x), f(y) \right\} $$

Compare with the convexity contition, $f\left(\theta x + (1-\theta)y\right) \le \theta f(x) + (1-\theta) f(y)$.

Quasiconvex functions on $\R$¶

A continuous function $f:\R\rightarrow \R$ is quasiconvex if and only if at least one of the following conditions holds:

• $f$ is monotonic: $f$ is nondecreasing or nonincreasing
• There is a point $c\in\dom f$ such that for $t\le c$ and $t\in\dom f$, $f$ is nonincreasing, and $t\ge c$ and $t\in\dom f$, $f$ is nondecreasing

Examples¶

• $\sqrt{|x-a|}+b$ is quasiconvex on $\R$

• $\sqrt{x}$ is quasilinear and concave on $\R$

• Gaussian distribution is quasiconcave

• Monotonic functions are quasilinear

• Discontinuous functions can be quasiconvex. For example, $\text{ceil}(x) = \inf\left\{z\in\Z \mid z \ge x\right\}$ and $\text{floor}(x) = \sup\left\{z\in\Z \mid z \le x\right\}$ are quasilinear.

Quasiconvex optimization via convex feasibility problems¶

Recall that a quasiconvex optimization problem has the standard form

$$ \begin{aligned} \underset{x}{\minimize} \quad & f_0(x) \\ \text{subject to} \quad & f_i(x) \le 0, &i=1,\dots,m \\ & Ax = b \end{aligned} $$

where $f_1,\dots,f_m$ are convex and the objective $f_0$ is quasiconvex. Let $\phi_t : \R^n \rightarrow \R$ with $t\in\R$, be a family of convex functions that satisfy

$$ f_0(t) \le t \quad \Longleftrightarrow \quad \phi_t (x) \le 0 $$

and also, for each $x$, $\phi_t(x)$ is a nonincreasing function of $t$, i.e., $\phi_s(x) \le \phi_t(x)$ whenever $s\ge t$.

Now let $p^*$ denote the optimal value of the quasiconvex optimization problem. If the feasibility problem

\begin{equation} \begin{aligned} \text{find} \quad & x \\ \text{subject to} \quad & \phi_t(x) \le 0, \\ & f_i(x) \le 0, &i=1,\dots,m \\ & Ax = b \end{aligned} \end{equation}

is feasible, then we have $p^*\le t$. Conversely, if the problem is infeasible, then we can conclude $p^*\ge t$. This observation can be used as the basis of a simple algorithm for solving the quasiconvex optimization problem using bisection.

Bisection method for quasiconvex optimization¶

given:

• $l\le p^*$, $u\ge p^*$, tolerance $\epsilon >0$.

repeat:

• Set $t:=(l+u)/2$

• Solve the convex feasibility problem

• if feasible, set $u:=t$, else set $l:=t$

until:

• $u-l \le \epsilon$