2
$\begingroup$

I am thinking about the Lipschitz continuity of a generalized Rayleigh quotient: $f(x)=\frac{x^\top Ax}{x^\top Bx}$ with the constraint $||x||\geq c$, where both $A$ and $B$ are positive definite matrices, $c$ is some positive constant, and I have the following questions:

  1. If $f(x)$ is Lipschitz continuous with respect to $\ell_2$ ($\ell_1$) norm?

  2. If so, how to compute the Lipschitz constant $L$?

It seems that it's difficult to compute $L$ directly using the definition of Lipschitz constant. I read somewhere that if $f(x)$ is convex, then $L\geq ||z||_*$ for all $x$, where $z$ is the gradient of $f(x)$: $z=\nabla f(x)$, and $||z||_*$ is the dual norm of $z$ (For $\ell_2$ norm, $||z||_*=||z||$.) .

So I am wondering if I can compute $L$ by $L=\sup \{\nabla f(x) : \nabla f(x)=\frac{2Ax(x^\top Bx)-2x^\top AxBx}{(x^\top Bx)^2}\}$ ?

Even though it's true, I don't know what to do next step. How can I prove if $||\nabla f(x)||_*$ is bounded and how to compute its upper bound?

In addition, we know that a generalized Rayleigh quotient is not convex, can we still use $||\nabla f(x)||_*$ to compute its Lipschitz constant?

Thanks.

$\endgroup$
1
$\begingroup$

The function $f$ is homogeneous of degree zero: $f(tx)=f(x)$ for all $t>0$. This implies that its gradient (with respect to whatever norm) is homogeneous of degree $-1$, that is $\nabla f(tx)=t^{-1}\nabla f(x)$ for all $t>0$.

The gradient is bounded on every set of the form $\{x:\|x\|\ge r\}$ with $r>0$. Indeed, it is bounded on the unit sphere by some constant $M$ (by continuity and compactness), hence bounded by $M/r$ on the aforementioned set.

One can estimate $M$ (the supremum of the gradient on the unit sphere) as follows: $$\|\nabla f(x)\| \le \left\|\frac{2Ax }{x^\top Bx}\right\|+ \left\| \frac{2x^\top AxBx}{(x^\top Bx)^2}\right\|\le 2\|A\|\,\|B^{-1}\|+2\|A\|\,\|B\|\,\|B^{-1}\|^2$$

In a convex domain, the supremum of the gradient equals the Lipschitz constant. The set $\{x:\|x\|\ge r\}$ is not convex, but it is quasiconvex, namely: any two points $a,b$ can be joined by a curve $\gamma$ of length at most $\frac{\pi}{2}|a-b|$ (an arc of a circle will do). Integrating the gradient along such a curve gives a bound for the Lipschitz constant: $$ |f(a)-f(b)|\le \int_\gamma \|\nabla f\| \le \frac{\pi}{2}|a-b|\sup\|\nabla f\| $$ Hence $L\le \frac{\pi}{2}\sup\|\nabla f\|$.

$\endgroup$
  • $\begingroup$ Thanks for pointing out that, @Behaviour. I omitted a constraint: $||x||\leq c$. $\endgroup$ – user3138073 Dec 26 '14 at 4:48
  • $\begingroup$ That does not help because the gradient blows up near the origin. If you had $\|x\|\ge c$, the function would be Lipschitz there. $\endgroup$ – user147263 Dec 26 '14 at 4:54
  • $\begingroup$ Yes. It should be $||x||\geq c$... Given this constraint, how can we compute the Lipschitz constant $L$? $\endgroup$ – user3138073 Dec 26 '14 at 4:59
  • $\begingroup$ I guess I can just let the constraint be $||x||=c$. Am I right? $\endgroup$ – user3138073 Dec 26 '14 at 5:01
  • $\begingroup$ Yes, the supremum on $\|x\|=c $ is the supremum on $\|x\|\ge 1$. Also, you might as well take $c=1$ in the calculation instead of carrying it around; it contributes the factor of $1/c$ to the final result. $\endgroup$ – user147263 Dec 26 '14 at 5:02

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.