6
$\begingroup$

How to compute Lipschitz Constant for multivariate function $f(x,y)=1-xy$? I know the definition for one variable? What is its definition for multivariate functions?

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Lipschitz_continuity $\endgroup$ – Daniele A Apr 15 '14 at 19:04
  • 1
    $\begingroup$ @DanieleA The wiki page only contains information for univariate function. $\endgroup$ – E.J. Apr 15 '14 at 19:09
  • $\begingroup$ There is also the definition for a general metric space. In your case, a function $f\colon \mathbb{R}^2 \to \mathbb{R}^2$ is said to be Lipschitz continuous if there exists a $C>0$ such that $|f(x)-f(y)|\leq C\cdot |x-y|$ for all $x,y\in \mathbb{R}^2$. By $|\cdot |$ you could take the standard euclidean norm on $\mathbb{R}^2$. $\endgroup$ – Daniele A Apr 15 '14 at 19:16
12
$\begingroup$

The function

$f(x,y)= 1 - xy \tag{1}$

is differentiable, and its derivative is both easy to compute and estimate; there is a more-or-less systematic procedure for finding a Lipschitz constant in such cases. Allow me to explain:

Let us set

$\mathbf r = \begin{pmatrix} x \\ y \end{pmatrix}; \tag{2}$

then we may also write

$f(\mathbf r) = 1 - xy. \tag{3}$

With this notation, Lipschitz continuity may be expressed via the inequality

$\Vert f(\mathbf r_1) - f(\mathbf r_2) \Vert < K \Vert \mathbf r_1 - \mathbf r_2 \Vert \tag{4}$

for a suitably chosen constant $K > 0$ and any $\mathbf r_1$, $\mathbf r_2$ within some open set $\Omega$ on which $f(\mathbf r)$ is defined; but there is one caveat which should be mentioned: when the function of interest such as $f(\mathbf r)$ is unbounded on $\Omega$, then quite often there will be no finite $K$ such that (4) holds for all $\mathbf r_1, \mathbf r_2 \in \Omega$; in such circumstances we may, however, be able to find a value of $K$ such that (4) holds if we restrict the set in which $\mathbf r_1$, $\mathbf r_2$ lie to be some suitable subset of $\Omega$; often, an open ball $B(\mathbf x, \rho)$, centered at $\mathbf x$ and with radius $\rho$, so that $B(\mathbf x, \rho) = \{ \mathbf y \mid \Vert \mathbf y - \mathbf x \Vert < \rho \}$, is chosen, provided $\mathbf x$ and $\rho$ are such that $B(\mathbf x, \rho) \subset \Omega$. Then the unqualified assertion of Lipschitz continuity, i.e. that (4) holds for all $\mathbf r_1, \mathbf r_2 \in \Omega$, is replaced by the requirement that (4) apply for all $\mathbf r_1, \mathbf r_2 \in B(\mathbf x, \rho) \subset \Omega$ for any $\mathbf x \in \Omega$ with some suitable $\rho > 0$; the key here is that $K = K_{\mathbf x}$ may now depend on $\mathbf x$, as may $\rho = \rho_{\mathbf x}$. Under such circumstances, we say that $f(\mathbf r)$ is locally Lipschitz on the domain $\Omega$; possession of this property is sufficient to guarantee that an ordinary differential equation of the form

$\dot{\mathbf r} = f(\mathbf r) \tag{5}$

has a unique solution $\mathbf r(t)$ satisfying

$\mathbf r(t_0) = \mathbf r_0 \tag{6}$

through any point $\mathbf r_0 \in \Omega$; such local solutions may indeed be pieced together to form solutions on maximal extent in $\Omega$; this is one of the main applications of the concept of local Lipschitz continuity.

We give examples to illustrate these ideas. Let

$\Omega = (-\dfrac{\pi}{2}, \dfrac{\pi}{2}) \tag{7}$

and let

$f(x) = \tan x \tag{8}$

defined on $\Omega$. $f(x)$ cannot satisfy a Lipschitz condition on $\Omega$, no matter how large the value of $K$ may be, for, taking $x_1 \in \Omega$ we see that, for any $K > 0$,

$K \vert x_2 - x_1 \vert < K\vert \dfrac{\pi}{2} - x_1 \vert \tag{9}$

since $x_2 < \pi / 2$. But

$\vert \tan x_2 - \tan x_1 \vert \to \infty \; \text{as} \; x_2 \to \dfrac{\pi}{2}, \tag{10}$

so that

$\vert \tan x_2 - \tan x_1 \vert < K \vert x_2 - x_1 \vert \tag{11}$

cannot possibly be satisfied for all $x_1, x_2 \in \Omega$. On the other hand, for any $x_0 \in \Omega$, if $\rho > 0$ is sufficiently small that $[x_0 - \rho, x_0 + \rho] \subset \Omega$, we can take

$K_{x_0} > \sup \{ \sec^2 x = (\tan x)', x \in [x_0 - \rho, x_0 + \rho] \}$ $= \max(\sec^2(x_0 - \rho), \sec^2(x_0 + \rho)), \tag{12}$

and then

$\mid \tan x_2 - \tan x_1 \mid < K_{x_0} \mid x_2 - x_1 \mid \tag{13}$

for $x_1, x_2 \in (x_0 - \rho, x_0 + \rho)$. (13) holds by virtue of the fact that the derivative of $\tan x$ is $\sec^2 x$, as we shall see in somewhat greater generality below; this shows that $\tan x$ is in fact locally Lipschitz continuous on $\Omega$. An example with two variables $x$ and $y$ may now easily be had by taking $f(x, y) = (\tan x)(\tan y)$ on the open set $(-\pi / 2, \pi / 2) \times (-\pi / 2, \pi / 2) \subset \Bbb R^2$; we refrain for the moment from presenting all the details in this two-dimensional case since they follow directly from the general result which will next be addressed.

We show that any $f(\mathbf r) \in C^1(\Omega, \Bbb R)$ is locally Lipschitz continuous throughout $\Omega$ for any domain $\Omega \subseteq \Bbb R^2$; to this end, let $\mathbf r_0 \in \Omega$ and select $\rho > 0$ sufficiently small that the closed ball $\bar B(\mathbf r_0, \rho) \subset \Omega$. For $\mathbf r_1, \mathbf r_2 \in B(\mathbf r_0, \rho) \subset \Omega$ let $\gamma:[0, 1] \to B(\mathbf r_0, \rho)$ be the path

$\gamma(t) = (1 - t)\mathbf r_1 + t\mathbf r_2 \tag{14}$

from $\mathbf r_1$ to $\mathbf r_2$ in $B(\mathbf r_0, \rho)$. Considering $f(\gamma(t))$, we have

$\Vert f(\mathbf r_2) - f(\mathbf r_1) \Vert = \Vert f(\gamma(1)) - f(\gamma(0)) \Vert = \Vert \int_0^1 \dfrac{df(\gamma(t))}{dt} dt \Vert \tag{15}$

and

$\dfrac{df(\gamma(t))}{dt} = \nabla f(\gamma(t)) \cdot \gamma'(t) = \nabla f(\gamma(t)) \cdot (\mathbf r_2 - \mathbf r_1); \tag{16}$

from (16) we have

$\Vert \int_0^1 \dfrac{df(\gamma(t))}{dt} dt \Vert = \Vert \int_0^1 (\nabla f(\gamma(t)) \cdot (\mathbf r_2 - \mathbf r_1))dt \Vert \le \int_0^1 \Vert \nabla f(\gamma(t)) \Vert \Vert \mathbf r_2 - \mathbf r_1 \Vert dt$ $= \Vert \mathbf r_2 - \mathbf r_1 \Vert \int_0^1 \Vert \nabla f(\gamma(t)) \Vert dt < K_{\mathbf r_0} \Vert \mathbf r_2 - \mathbf r_1 \Vert \tag{17}$

for any finite $K_{\mathbf r_0} > \sup \{\Vert \nabla f(\mathbf r) \Vert \mid \mathbf r \in B(\mathbf r_0, \rho) \}$; that such a $K_{\mathbf r_0}$ exists is a consequence of the fact that $f \in C^1(\Omega, \Bbb R)$ implies $\Vert \nabla f \Vert$, being continuous, is in fact bounded on compact subsets of $\Omega$, of which $\bar B(\mathbf r_0, \rho)$ is but one example. It may be helpful to note that the vector form of the fundamental theorem of calculus has been used in establishing (15), as has the chain rule been deployed to arrive at (16). Furthermore, a technique for obtaining a local Lipschitz constant $K_{\mathbf x}$ for any $x \in \Omega$ is implicit in the preceding argument: simply choose $K_{\mathbf x} > \sup \{\Vert \nabla f(\mathbf r) \Vert \mid \mathbf r \in B(\mathbf x, \rho) \}$ for $\bar B(\mathbf x, \rho) \subset \Omega$.

Bearing the above discussion in mind, we return to $f(\mathbf r) = 1 - xy$. Whereas there is no global Lipschitz constant $K$ valid on all of $\Omega = \Bbb R^2$ in this case, as has been shown by xavierm02 and Christian Blatter in their answers, $f(\mathbf r)$ is in fact locally Lipschitz. To see this, observe that $\nabla f = (-y, -x)^T$ so that $\Vert \nabla f \Vert = \sqrt{x^2 + y^2}$; thus $\Vert \nabla f \Vert$ is bounded on any closed ball $\bar B(0, R)$ centered at the origin; thus for $\mathbf x \in \Bbb R^2$ and for any $\rho \in \Bbb R$ taking $R > \Vert \mathbf x \Vert + \rho$ we have $\Vert \nabla f \Vert < R$ in $\bar B(\mathbf x, \rho)$; taking $K_{\mathbf x} = R$ thus provides a local Lipschitz constant at $\mathbf x$.

Just to round things out, consider once again the previously mentioned example

$f(\mathbf r) = (\tan x)(\tan y), \mathbf r \in \Omega = (\dfrac{-\pi}{2}, \dfrac{\pi}{2})^2; \tag{18}$

by holding $y = y_0 \ne 0$ constant, it is easy to see that there can be no Lipschitz constant for $f(\mathbf r)$ on $\Omega$; the argument is essentially the same as that given for $\tan x$ above. Also, $\nabla f = ((\sec^2 x)(\tan y), (\tan x)(\sec^2 y))^T$ for every $\mathbf r \in \Omega$ and thus

$\Vert \nabla f \Vert = \sqrt{(\sec^4 x)(\tan^2 y) + (\tan x)^2 (\sec^4 y)}; \tag{19}$

given $\mathbf r = (x, y)^T \in \Omega$, it is easy to find a bound for $\nabla f$ on $\bar B(\mathbf r, \rho) \subset \Omega$, $\rho$ sufficiently small, by noting that $[x - \rho, x + \rho] \times [y - \rho, y + \rho] \subset \Omega$ as well. I leave the simple details to any reader interested enough to execute them.

Hope this helps. Cheerio,

and as always,

Fiat Lux!!!

$\endgroup$
  • 1
    $\begingroup$ I lost on $r = \binom{x}{y}$ — you didn't mean a binomial coefficient, did you? Otherwise the following $f(r) = 1-xy$ doesn't make sense because $x$ and $y$ would never be equal to anything. $\endgroup$ – Hi-Angel Apr 17 '17 at 9:01
  • 1
    $\begingroup$ @Hi-Angel: $\mathbf r = \begin{pmatrix} x \\ y \end{pmatrix}$ is the two-vector whose entries are $x$ and $y$. $\endgroup$ – Robert Lewis Apr 17 '17 at 17:41
9
$\begingroup$

As $f$ is a quadratic polynomial in $x$ and $y$ you cannot expect that there is a globally valid Lipschitz constant for $f$, because such a constant would allow only a linear increase of $f$ on a large scale.

For a formal proof consider the point ${\bf z}_0:=(x_0,0)$ and the "nearby" point ${\bf z}:=(x_0,h)$, $\>h>0$. Then $|{\bf z}-{\bf z}_0|=h$ and $$|f({\bf z})-f({\bf z_0})|=|(1-x_0h)-1|=|x_0|\>h=|x_0|\>|{\bf z}-{\bf z}_0|\ .$$ Since $|x_0|$ can be arbitrarily large it follows that there is no universal $C>0$ such that $$|f({\bf z})-f({\bf z_0})|\leq C\>|{\bf z}-{\bf z}_0|$$ for all ${\bf z}$, ${\bf z}_0\in{\mathbb R}^2$.

$\endgroup$
4
$\begingroup$

There is no Lipschitz constant.

Suppose there was one. $\forall x_1,y_1,x_1,y_2 \in \Bbb R, |(1- x_1y_1)+(1-x_2y_2)|\le C \|(x_1,y_1)-(x_2,y_2)\|$

$|x_1y_1-x_2y_2|\le C \|(x_1,y_1)-(x_2,y_2)\|$

Take $x_1=x_2=2C$

$|2Cy_1-2Cy_2|\le C \|(2C,y_1)-(2C,y_2)\|=C|y_1-y_2|$

$2C|y_1-y_2|\le C|y_1-y_2|$

Take $y_2\not=y_1$

$2C\le C$ which is absurd since $C>0$

$\endgroup$

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.