<p>Consider an iterative algorithm of the form $x^{t+1} = x^t - \eta g(x^t)$. (..if necessary feel free to assume that a function $L$ is explicitly known such that $g = \frac{\partial L}{\partial x}$..). Suppose that now I want to show that there exists a point $x^*$ within some pre-determined ball which is a fixed point for this iterative algorithm. </p>

<ul>
<li><p>I would like to know what methods are generally known to show such a thing in cases when the function $g$ is too complicated to solve for its roots? </p></li>
<li><p>Is there a way to argue for the existence of such fixed points starting from proving some Lyapunov-like properties for $L$? </p></li>
</ul>

CC BY-SA 3.0
2017-06-09T16:02:45.890Z
(1) Isn't your question just asking how to show that the given function $g$ has a root $x^*$ in some predetermined ball?  (As $x^*$ is a fixed point of your algorithm if and only if $x^*$ is a root of $g$.)  (2) What is the type of $x^t$?  Is $x^t\in \mathbb{R}$?
Neal Young
CC BY-SA 3.0
2017-06-09T17:02:17.613Z
Yes, you can think of it this way. I want to know if there are ways to use the Lypunaov kind of thinking with $L$ to somehow circumvent the usually hard problem of showing roots of $g$. You can assume $x^t \in \mathbb{R}^n$ for some $n$.
gradstudent
<ds.algorithms><application-of-theory><iterated-rounding>
Iterative algorithms and Lyapunov functions
gradstudent
# Iterative algorithms and Lyapunov functions

(Asked by: username_0 on 2017-06-08)

Consider an iterative algorithm of the form $x^{t+1} = x^t - \eta g(x^t)$. (..if necessary feel free to assume that a function $L$ is explicitly known such that $g = \frac{\partial L}{\partial x}$..). Suppose that now I want to show that there exists a point $x^\*$ within some pre-determined ball which is a fixed point for this iterative algorithm.

* I would like to know what methods are generally known to show such a thing in cases when the function $g$ is too complicated to solve for its roots?
* Is there a way to argue for the existence of such fixed points starting from proving some Lyapunov-like properties for $L$?

**Tags:** ds.algorithms, application-of-theory, iterated-rounding
> **Comments:**
> **username_1**: (1) Isn't your question just asking how to show that the given function $g$ has a root $x^*$ in some predetermined ball?  (As $x^*$ is a fixed point of your algorithm if and only if $x^*$ is a root of $g$.)  (2) What is the type of $x^t$?  Is $x^t\in \mathbb{R}$?  
> **username_0**: Yes, you can think of it this way. I want to know if there are ways to use the Lypunaov kind of thinking with $L$ to somehow circumvent the usually hard problem of showing roots of $g$. You can assume $x^t \in \mathbb{R}^n$ for some $n$.  

---

## 0 answers

