2

For $\alpha \in \mathbb{R}$ and $x, c \in \mathbb{R}^n$ and $R \in \mathbb{S}_+^n$ (positive semi-definite), let

\begin{equation*} f(x) = \frac{\alpha - c^t x}{\sqrt{x^t R x}} \end{equation*}

with $\text{dom}f = \{ x | c^t x \geq \alpha\}$ and $x^t R x > 0$ for all $x \in \text{dom}f$.

How can I show that $f$ is or is not quasiconvex?

I tried disproving this by testing 100,000 random lines segments sampled in $\text{dom} f$ but found no counter-examples.

Solution

I've determined the solution to the problem and posted it as an answer. It turns out that in general a function of the form $f(x) = p(x)/q(x)$ where $p(x)$ and $q(x)$ are convex, and $p(x) \leq 0$ and $q(x) > 0$ for all $x \in \text{dom}(f)$ is always quasi-convex if $\text{dom} f$ is a convex set.

jodag
  • 800
  • 1
    For $t\ge 0$: are you sure that dom($f$) is convex? Since $R$ is only semidefinite the linear subspace $x^TRx=0$ may divide dom($f$) in two disconnected components, thus the overall set is nonconvex. For example, $f(x,y)=\frac{1-y}{x^2}$. – A.Γ. Nov 05 '17 at 22:56
  • dom($f$) is a half-space in $\mathbb{R}^n$ which is convex. I guess it isn't clear from the question but the fact that $x^t R x > 0$ for all $x \in \text{dom}f$ is a constraint on $R$ not on $\text{dom}f$. The reason for this is that this problem is part of a bigger problem where I explicitly deal with $x^t R x = 0$ before getting to the problem I posted here. Therefore I'm sure that $x \in {x | c^t x \geq \alpha} \Rightarrow x^t R x > 0$. – jodag Nov 06 '17 at 00:06
  • 1
    Then I see no problem with your proof. – A.Γ. Nov 06 '17 at 00:34

1 Answers1

0

Thanks to @A.Γ. for verifying the proof.

From the definition of quasi-convexity. A function $f$ is quasi-convex if the $t$-sublevel sets $\{ x \in \text{dom} f | f(x) \leq t \}$ are convex sets for all $t \in \mathbb{R}$.

In this problem $f$ has the form

\begin{equation*} f(x) = \frac{p(x)}{q(x)} \end{equation*}

where $p(x)$ and $q(x)$ are convex and $p(x) \leq 0$ and $q(x) > 0$.

For $t \geq 0$, the $t$-sublevel set is $\text{dom} f$ because $f(x) \leq 0$ for all $x$ in $\text{dom}f$ which is a half-space and therefore convex.

From A.Γ.'s comment I realize it may not be clear from the original problem but we assume here that $x \in \text{dom}f = \{x | c^t x \geq \alpha\} \Rightarrow x^t R x > 0$, so $\text{dom}f$ is always a half-space and is therefore a convex set.

For $t < 0$ we have

\begin{equation*} \frac{p(x)}{q(x)} \leq t \iff p(x) - tq(x) \leq 0. \end{equation*}

Because $p(x)$ is convex and $-tq(x)$ is convex, the sum is convex. The $t$-sublevel set of $f$ is the zero-sublevel set of the convex function $p(x) - t q(x)$ which is a convex set. Therefore $f(x)$ is quasi-convex.

jodag
  • 800