0

Let $A$ be an invertible $p \times p$ matrix, and $\phi(x) = x - A^{-1}f(x) $.

Let $M$ be a subset of $\mathbb{R}^p$. Under which condition do we have $\phi(x)$ Lipschitz-continuous with constant $K$ on $M$. That is, for every $(x_1,x_2) \in M$,

$$|x_1 - x_2 - A^{-1}(f(x_1) - f(x_2))| \le K|x_1 - x_2 |$$

If $f(x)$ is differentiable, a sufficient condition is that, for $\lambda = K \| A^{-1}\|^{-1}$ and $\| B \|$ the sup-norm of $B$, we have, for all $x \in M$,

$$\| \partial_x f(x) - A \| \le \lambda$$

in which case we have

$$ \| \partial_x \phi(x) \| = \| I - A^{-1}\partial_x f(x)\| \le \| A^{-1} \| \times \| \partial_x f(x) - A \| \le \| A^{-1} \| \lambda \le K$$

which implies that $\phi(x)$ is $K$-Lipschitz.

However, what if $f(x)$ isn't differentiable? Is there a sufficient condition for $f(x)$ involving $A$ or $\lambda$?

Bernard
  • 175,478
Guillaume F.
  • 854

2 Answers2

2

I don't know if it helps but:

Claim: $\phi(x)$ is Lipschitz if only if $f(x)$ is Lipschitz.

$(\Rightarrow)$ if $\phi(x)$ is Lipschitz we have $k \in \mathbb{R}$ such that: $$ |x-y-A^{-1}(f(x) - f(y))| \leq k|x-y| $$ In other words: $$ -k|x-y| \leq x-y-A^{-1}(f(x) - f(y)) \leq k|x-y| $$ $$ -k|x-y|+x-y \leq -A^{-1}(f(x) - f(y)) \leq k|x-y|+x-y $$ $$ -k|x-y|-x+y \leq A^{-1}(f(x) - f(y)) \leq k|x-y|-x+y $$ Then we get that $A^{-1}f$ is Lipschitz with constant $k+1$ since $-(k+1)|x-y| \leq -k|x-y|-x+y$ and $ k|x-y|-x+y \leq (k+1)|x+y|$.

From the fact that $A$ is nonsingular we have (check this question) for all $x$: $$ \frac{1}{||A||}|x| \leq |A^{-1}x| \leq ||A^{-1}|||x| $$ Joining these inequalities we have: $$ \frac{1}{||A||}|f(x)-f(y)| \leq |A^{-1}(f(x)-f(y))| \leq (k+1)|x-y| $$ and $$ -(k+1)|x-y| \leq |A^{-1}(f(x)-f(y))| \leq ||A^{-1}|||f(x)-f(y)| $$

Then: $$ |f(x)-f(y)| \leq ||A||(k+1)|x-y| $$ $$ -\frac{1}{||A^{-1}||}(k+1)|x-y| \leq |f(x)-f(y)| $$

Which shows that $f$ is Lipschitz with coeficient $\max \left( \frac{1}{||A^{-1}||}(k+1) , ||A||(k+1) \right)$.

$(\Leftarrow)$ If $f$ is Lipschitz with constant $k$: $$ |x-y-A^{-1}(f(x) - f(y))| \leq |x-y|+|A^{-1}(f(x) - f(y))| \leq |x-y|+||A^{-1}|||(f(x) - f(y))| \leq |x-y|+||A^{-1}||k|x-y| \leq (1+||A^{-1}||k)|x-y|$$

Showing that $\phi$ is Lipschitz.

Lucas Resende
  • 1,286
  • 9
  • 21
  • I don't think that's correct.

    If we take $p = 1$, $A = 1$, and $K = 1$, then clearly $f(x) - f(y)$ must be of the same sign as $x - y$ or else it the statement is wrong. Yet, $|x-y|$ ignores the sign.

     – Guillaume F. Jun 15 '18 at 15:15
  • i can't see that, in that case we have $\phi(x) = x-f(x)$, take $f(x) = -x$, than f(x)-f(y) has the opposite sign as $x-y$. I really don't understant what you are saying. – Lucas Resende Jun 15 '18 at 15:23
  • Sorry, I misread your proof. I meant to say that your method does not provide a sufficient condition for $\phi$ to be $K$-Lipschitz for $K < 1$. In other words I can't use it to prove that $\phi$ is a contraction. But you provided $\phi$ is Lipschitz iff $f$ is Lipschitz, which is great! – Guillaume F. Jun 15 '18 at 15:40
0

For $\bf p = 1$, a sufficient condition for

$$|x_1 - x_2 - A^{-1}(f(x_1) - f(x_2))| \le K|x_1 - x_2 |$$

is that, for $(x_1, x_2) \in M$, $x_1 \ne x_2$,

$$|\frac{f(x_1) - f(x_2)}{x_1 - x_2} - A |\le K |A| $$

Proof. The previous statement is equivalent to

$$|A^{-1}\frac{f(x_1) - f(x_2)}{x_1 - x_2} - 1 |\le K $$

which in turn implies

$$| A^{-1}[f(x_1) - f(x_2)] - x_1 - x_2 | \le K |x_1 - x_2| $$

which provides the proof.

However, I do not know if the argument can be generalized to the case $p > 1$.

Guillaume F.
  • 854