0
$\begingroup$

I know that the definition of the Lipschitz continuity is defines as $$||f(y) - f(x)|| \leq L ||y-x||$$

My professor told me that by knowing $f$ we can find constant $L$ using the power iteration method, which essentially computes the maximum eigenvalues. Yet I don't see how definition above is related to searching for max eigenvalues. Can anyone please help me understand?

$\endgroup$
3
  • $\begingroup$ Is $f$ a linear function(al)? Otherwise, eigenvalue analogy does not make sense. Assuming that this is related to the fixed point problem "find $x$ s.t. $x=f(x)$", you can approximate the constant as $L \approx \max_i \|f(x_{i+1})-f(x_i)\|/\|x_{i+1} - x_i\|$ which is equal to $\max_i \|x_{i+2}-x_{i+1}\|/\|x_{i+1} - x_i\|$ and $\max_i \|f(x_{i+1})-f(x_i)\|/\|f(x_{i}) - f(x_{i-1})\|$. This fairly looks like a power iteration and maybe that is what your professor meant. $\endgroup$ May 17 at 8:48
  • $\begingroup$ I greatly appreciate your reply. This result is necessary as an assumption for the local convergence of primal-dual problem. Can you elaborate more why $\max_{i} $ looks like power iteration? From what I know, the power iteration algorithm is needed to find eigenvalues and I don't see any eigenvalue problem here. $\endgroup$
    – Maria
    May 17 at 9:02
  • $\begingroup$ There may not be an eigenvalue problem at all. That analogy may not be valid. Regarding why the maximum ratio over the iterations may approximate $L$, see cfdlab's answer. $\endgroup$ May 17 at 18:50
1
$\begingroup$

Define the iteration $$ x_{n+1} = f(x_n) $$ Then $$ e_n := \frac{\|x_{n+1} - x_n\|}{\| x_n - x_{n-1}\|} \le L $$ Compute $e_n$ and that should tell you something about L. If the iterations converge ($L < 1$), then $e_n$ should converge to $L$.

$\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.