Convexity of $x \mapsto \frac{\|Ax-b\|^2_2}{1-\|x\|^2_2}$

Question

Given matrix $A \in \Bbb R^{n \times n}$ and vector $b \in \Bbb R^n$, determine whether the following function is convex.

$$ f: \{x \in \Bbb R^n : \|x\|_2 < 1\} \to \Bbb R, \qquad x \mapsto \frac{\|Ax-b\|^2_2}{1-\|x\|^2_2} $$

The numerator appears to be similar to the Least square function which I know is convex. Since: for convex function f over a convex set for any α ≥ 0, the function α*f is a convex function. Is setting:

$a=\frac{1}{1-\|x\|^2_2} \geq 0$

a valid proof for convexity? I am very thankful for any tips!

River Li · Accepted Answer · 2020-03-29T23:42:25.680

6

The function is convex. Indeed, clearly $S = \{x\in \mathbb{R}^n: \|x\|_2 < 1\}$ is a convex set, $\|Ax-b\|_2$ is convex and nonnegative on $S$, $1-\|x\|_2^2$ is concave and positive on $S$ (since $\|x\|_2^2$ is convex on $\mathbb{R}^n$), from Fact 1 below, the desired result follows.

Fact 1: Let $S\subseteq \mathbb{R}^n$ be a convex set. Let $f: S \to \mathbb{R}$ be convex and $f(x) \ge 0, \forall x \in S$. Let $g: x \to \mathbb{R}$ be concave and $g(x) > 0, \forall x \in S$. Then $\frac{f^2}{g}$ is convex on $S$.

Proof of Fact 1: For any $x_1, x_2 \in S$ and $t\in [0,1]$, we have $$f(t x_1 + (1-t)x_2) \le tf(x_1) + (1-t)f(x_2)$$ and $$g(tx_1 + (1-t)x_2) \ge tg(x_1) + (1-t)g(x_2).$$ Thus, we have \begin{align} &t\frac{(f(x_1))^2}{g(x_1)} + (1-t)\frac{(f(x_2))^2}{g(x_2)} - \frac{(f(tx_1 + (1-t)x_2))^2}{g(tx_1 + (1-t)x_2)}\\ \ge\ & t\frac{(f(x_1))^2}{g(x_1)} + (1-t)\frac{(f(x_2))^2}{g(x_2)} - \frac{(tf(x_1) + (1-t)f(x_2))^2}{tg(x_1) + (1-t)g(x_2)}\\ =\ & \frac{t(1-t)[f(x_1)g(x_2) - f(x_2)g(x_1)]^2}{g(x_1)g(x_2)[tg(x_1) + (1-t)g(x_2)]}\\ \ge\ & 0. \end{align} Q.E.D.

edited Mar 29 '20 at 23:42

answered Mar 29 '20 at 16:27

River Li

37,323

1

Beautiful! Fact 1 is nice. – dohmatob Mar 29 '20 at 16:49
Yes Fact 1 is super cool. It looks general and powerful. I wonder if it is well known ? It should be :D – Thomas Mar 29 '20 at 21:09
Only one typo. In the derivation after "we have" I think the first one is an inequality and not an equality. – Thomas Mar 29 '20 at 21:16
1

@Thomas Revised. Thanks. BTW, yes, it is a known result. – River Li Mar 29 '20 at 23:43
3

To avoid the definition mess: define $L(x,t)=-g(x)t^2+2tf(x)$. The function is convex in $x$ for all $t\ge 0$, hence, $\max_{t\ge 0}L(x,t)=\frac{f^2}{g}$ is convex. – A.Γ. Mar 30 '20 at 01:10
2

@A.Γ. Your proof is impressive. – River Li Mar 30 '20 at 01:44

Convexity of $x \mapsto \frac{\|Ax-b\|^2_2}{1-\|x\|^2_2}$

1 Answers1