Boyd & Vandenberghe, section 3.3.4 — Quasiconvexity of linear-fractional composition

2k Views Asked by At

In Boyd & Vandenberghe, Section 3.3.4, it is stated that composition of a quasiconvex function with an affine-fractional transformation is quasiconvex. In specific, if $f(x)$ is quasiconvex, then

$$ g(x) = f\Big(\frac{Ax+b}{c^Tx + d}\Big)$$

is also quasiconvex on the domain of $f$ when the denominator of the fraction is positive. Here, $A$ is a matrix, $b$ and $c$ are vectors, and $d$ is a scalar.

I have tried to show this useful fact, but have been unable to. The simpler property that composition with an affine function preserves quasiconvexity follows straightforwardly from the definition of a quasiconvex function, but all my attempts at generalizing to the fractional case have been fruitless.

Any ideas? Oddly I have not been able to find a proof anywhere.

1

There are 1 best solutions below

1
On BEST ANSWER

Just notice $$\frac{A(\lambda x+(1-\lambda)y)+b}{c^T(\lambda x+(1-\lambda)y)+d}=\mu \frac{A x+b}{c^T x+d}+(1-\mu)\frac{A y+b}{c^T y+d},$$ where $\mu=\frac{\lambda (c^T x+d)}{\lambda (c^T x+d)+(1-\lambda) (c^T y+d)}.$ Hence $$g(\lambda x+(1-\lambda)y)=f(\mu \frac{A x+b}{c^T x+d}+(1-\mu)\frac{A y+b}{c^T y+d})\leq\max\{f(\frac{A x+b}{c^T x+d}),f(\frac{A y+b}{c^T y+d})\}.$$