6
$\begingroup$

Consider the function $f : \mathbb R \to \mathbb R$, which has a unique fixed point $x^* \in \mathbb R$, such that $x^* = f(x^*)$ and there does not exist another $x \in \mathbb R$ such that $x = f(x)$. If we only knew that $f$ had a unique fixed point, but didn't know the value of $x^*$, could we then compute $x^*$ as the solution of the following optimization problem? $$ \begin{aligned} \max_{x \in \mathcal X} \quad & x \\ \textrm{s.t.} \quad & x \leq f(x) \end{aligned} $$ It seems that the answer is "yes" (but I'd like some feedback on my reasoning): let $x^*$ be the solution to the problem above, such that $$ \begin{align} \forall x \in \mathbb R, x \leq x^* \tag{1} \\ x^* \leq f(x^*) \tag{2} \end{align} $$ Suppose, for the sake of contradiction, that $x^*$ is not the unique fixed point of $f$, such that $x^* \neq f(x^*)$. Then, from $(2)$, $x^* < f(x^*) = v$. However, this contradicts $(1)$, since $v > x^*$. Therefore, $x^* = f(x)$. Does this seem reasonable?


Update

Based on @ConnFus's answer, it must first be proven that there exists one and only one solution $x^*$ to the optimization problem mentioned above. Otherwise, my proof above falls apart, since it rests on the assumption that $x^*$ exists and is unique.

$\endgroup$
4
  • $\begingroup$ If you think for sake of contradiction that x Is a fixed point but not the sole, unique fixed point then you argumentation Is not reasonable. $\endgroup$ Dec 21, 2023 at 20:36
  • $\begingroup$ @marcotognoli I’ve edited my wording so that we assume (for the sake of contradiction) that $x^*$ is “not a fixed point of $f$”. Previously, we assumed (for the sake of contradiction) that $x^*$ is “not the unique fixed point of $f$”. Is this what you meant? $\endgroup$
    – mhdadk
    Dec 22, 2023 at 2:59
  • $\begingroup$ In my experience it's often easier to solve an optimisation problem that has a complicated objective function but simple constraints, than an optimisation problem that has a simple objective function but complicated constraints. In your problem, $x$ is simple, and $f(x)$ is complicated, and you put $f(x)$ in the constraints. Instead you might want to consider the problem $\min |f(x) - x|$ which should also find $x^*$ (and which easily generalises to functions whose domain is not $\mathbb R$) $\endgroup$
    – Stef
    Dec 22, 2023 at 14:15
  • $\begingroup$ @Stef: And the choice of norm to be minimized can be made to make the problem nicer for analysis (square of 2-norm is often used, i.e. minimization of square error) $\endgroup$
    – Ben Voigt
    Dec 22, 2023 at 17:56

3 Answers 3

4
$\begingroup$

If we let $f(x):=e^x-1$, then it has the unique fixed point $x^*=0$.

However for all $x\in\mathbb R$ it holds that $x\le f(x)$, so the the optimization problem \begin{aligned} \max_{x \in \mathcal X} \quad & x \\ \textrm{s.t.} \quad & x \leq f(x) \end{aligned} has no solution.


Addendum:

Let's add the constraint that $f$ is continuous, because otherwise I think this is a lost cause. Now, let $x^*$ be the unique fixed point. Then we have either $$\forall z>x^*:\quad z<f(z)\tag{1}$$ or $$\forall z>x^*:\quad z>f(z)\tag{2}$$In case (2) we are indeed done, but in case (1) the optimization problem misses the fixed point.

So let's look at case (1): In it, we have two subcases: $$\forall z<x^*:\quad z<f(z)\tag{1.1}$$ $$\forall z<x^*:\quad z>f(z)\tag{1.2}$$

In subcase (1.2) we can change the optimization problem to \begin{aligned} \min_{x \in \mathcal X} \quad & x \\ \textrm{s.t.} \quad & x \leq f(x) \end{aligned} and are done.

In subcase (1.1) we have that $\forall z\in\mathbb R:\quad z\le f(z)$ with equality only in $z=x^*$. So we can change the optimization problem to \begin{aligned} \max_{x \in \mathcal X} \quad & x-f(x) \\ \end{aligned} and are done.

So, in the end you have to handle 3 cases, artificially restrict $f$ to be one of those cases, or use a different optimization problem altogether.

$\endgroup$
9
  • $\begingroup$ Good point. I think requiring that $f$ also be surjective on $\mathbb R$ in addition to having a unique fixed point should fix this, since the set $\{x \in \mathbb R \mid x \leq f(x)\}$ should always be bounded and non-empty when $f$ is surjective, and so your counterexample would no longer apply. $\endgroup$
    – mhdadk
    Dec 23, 2023 at 5:01
  • $\begingroup$ @mhdadk If you want to add constraints on $f$ such that your statement works, they have to imply (2). Surjectivity doesn't do that, which we can see by looking at an example for case (1.1), e.g. $$f(x)= \begin{cases} e^x-1,&x\ge 0 \\ x/2,& x< 0 \end{cases} $$, which is surjective and has $\{x \in \mathbb R \mid x \leq f(x)\}$ unbounded. $\endgroup$
    – ConnFus
    Dec 23, 2023 at 7:03
  • $\begingroup$ Thanks again! Just a few questions: (1) the reason you are done in case $(2)$ is because, if $x^* = \max\{x \in \mathcal X \mid x \leq f(x)\}$, then case $(2)$ implies that there would not exist another point in the feasible set that is larger than $x^*$, correct? $\endgroup$
    – mhdadk
    Dec 23, 2023 at 7:38
  • 1
    $\begingroup$ (3) Where did you use the assumption that $f$ is continuous in your argument? $\endgroup$
    – mhdadk
    Dec 23, 2023 at 7:42
  • 1
    $\begingroup$ In regards to (1) and (2) of your questions: Yes, that is precisely correct. In regards to (3): Without continuity the case distinction into (1) and (2) doesn't work anymore; Let's assume $f$ were continuous but neither case (1) or (2) would apply (that is, we have some $z_1,z_2>x^*$ with $z_1<f(z_1)$ and $z_2>f(z_2)$). By the intermediate value theorem we then know that at some point $z>x^*$ there has to hold $z=f(z)$, i.e. we have a second fixed point. $$$$ However, if we assume that case (2) holds directly, we indeed don't need that $f$ is continuous. $\endgroup$
    – ConnFus
    Dec 23, 2023 at 7:51
4
$\begingroup$

This is a valid formulation if a global optimizer is used, and it succeeds in finding the global optimum.

A local optimizer might fail to find the global optimum, in which case any solution found might not be a fixed point of the original problem.

Alternatively, you could formulate the optimization problem:

max 0 subject to $x = f(x)$

whose solution, $x$, if found, is the fixed point you seek. It is possible that a local optimizer might fail to find the fixed point, even it it exists, although the local optimizer should not return a solution which is not a fixed point of the original problem.

In summary, your formulation might produce a non-locally optimal solution which is not a fixed point of the original problem. The alternative formulation in my answer should not return a solution which is not a fixed point of the original problem, but if a global optimizer is not used, might fail to find a solution.

Edit: Note that even if $f(x)$ is convex, the constraint $x = f(x)$ is non-convex (unless $f(x)$ is affine (linear)). Optimization solvers would generally have an easier time dealing with the convex constraint, $x \le f(x)$, than the non-convex constraint, $x = f(x)$, even if it is known that $x = f(x)$ is satisfied at the solution.

$\endgroup$
2
  • $\begingroup$ Thanks for the feedback. I'm guessing if $f$ is concave (such that the feasible set $x - f(x) \leq 0$ is convex), then a local optimizer should successfully find the fixed point, right? $\endgroup$
    – mhdadk
    Dec 21, 2023 at 14:07
  • 1
    $\begingroup$ Generally speaking yes, but if the function is numerically poorly behaved or the optimizer is low quality, it might not succeed, even though it probably shouldn't producer a solution which is not globally optimal;. But there are many crummy optimization solvers, so no guarantees on any of that. $\endgroup$ Dec 21, 2023 at 14:18
0
$\begingroup$

Let $f$ be a real function of real variable defined as $f(x)=x$.

Let consider $X_1=[0 , 0.5]$ and $X_2=[0.5 , 1]$.

$f:X_1 \rightarrow X_1$ has as solution of the optimization problem $x_1=0$. $f:X_2 \rightarrow X_2$ has as solution of the optimization problem $x_2=1$ In both cases, $x_1=0.5$ and $x_2=1$ are fixed points: $f(0.5)=0.5$ and $f(1)=1$. These two fixed points solve the optimization problem and are not unique! Now, take $X$ as the Union of $X_1$ with $X_2$ ... It comes out that $x_2=1$ is the unique solution of the optimization problem in which we seek for the maximum fixed point. Actually, the function $f$ has more than one fixed point, so we have showed that the following proposition: If $x^*$ is a solution of the optimal problem then $x^*$ is the unique fixed point for $f$ is false in general. As a consequence, the problem in finding fixed point is not equivalent to solve an optimization problem.

$\endgroup$
5
  • 2
    $\begingroup$ I’m not sure what you mean here, since your example of $f$ does not have a single unique fixed point. This is the main assumption in my question. Could you please elaborate? $\endgroup$
    – mhdadk
    Dec 22, 2023 at 3:00
  • $\begingroup$ This does not appear to answer the question that was asked. The question states "If we only knew that $f$ had a unique fixed point, [...] could we [...]?" Your $f$ does not have a unique fixed point, so it is not relevant to the question that was asked. $\endgroup$
    – D.W.
    Dec 22, 2023 at 4:35
  • $\begingroup$ @mhdadk Question: "If we only knew that $f$ had a unique fixed point, [...] could we [...]?" My answer gives a counterexample. In general, it is not true that one can search a sole fixed point by solving an optimization problem and vice versa. $\endgroup$ Dec 22, 2023 at 6:07
  • $\begingroup$ How is this a counter-example? Your "counterexample" does not have a unique fixed point, so it is immediately not relevant to my question. Your counterexample would need to have a unique fixed point and at the same time show that this fixed point is not computable as the solution of an optimization problem. $\endgroup$
    – mhdadk
    Dec 22, 2023 at 6:17
  • $\begingroup$ How imy counterexample is not relevant to your question? Your question is not well-posed. By the way, have you considered the Union of $X_1$ and $X_2$? How many fixed points do you count? If you can not accept answer you do not like, please avoid to ask question. All the best. $\endgroup$ Dec 22, 2023 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.