2
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Beautiful! Fact 1 is nice. $\endgroup$ – dohmatob Mar 29 at 16:49
  • $\begingroup$ Yes Fact 1 is super cool. It looks general and powerful. I wonder if it is well known ? It should be :D $\endgroup$ – Thomas Mar 29 at 21:09
  • 1
    $\begingroup$ @Thomas Revised. Thanks. BTW, yes, it is a known result. $\endgroup$ – River Li Mar 29 at 23:43
  • 2
    $\begingroup$ 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. $\endgroup$ – A.Γ. Mar 30 at 1:10
  • 2
    $\begingroup$ @A.Γ. Your proof is impressive. $\endgroup$ – River Li Mar 30 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.