4
$\begingroup$

Let's say I have a multivariate function $$ f:D \to D, D \subset \mathbb R ^n, D \text{ compact}, $$ for which there is no closed form.
That is the only way to evaluate the function is to do it numerically.

For example, the price of some exotic insurance contracts: the rule governing the payout are simple, but have no closed formula.

If I suspect my function $f$ is a contraction, is it possible to prove it numerically?

My first though will be to evaluate numerically $f'$ at 1000 points of $D$.
Is this sufficient?
Probably not, have there been some work on such numerical tests?

My second though will be to assume $f'$ follows a normal distribution, then perform an hypothesis test.
Is this reasonable?

My use case is that, I search for a fixed point of $f$ using dynamic programming.
But the state space becomes too large.
If I can proove $f$ is a contraction, then I avoid the curse of dimensionality.

$\endgroup$
11
  • 1
    $\begingroup$ Why don't you just do many Piquard iterations and see if the convergence is geometric and the last iteration is nearly a fixed point? If it is, who cares why (you just need to find a fixed point, right?) if it isn't, $f$ is certainly not contractive enough and you've got to try something else. $\endgroup$
    – fedja
    Jun 19, 2013 at 16:26
  • 1
    $\begingroup$ Interesting... I do not think anything useful can be said in such generality (obviously, in principle there may be small scale wiggles that no particular finite number of checks can catch) but if you tell exactly how the function is defined, someone may be able to come up with some good idea. $\endgroup$
    – fedja
    Jun 19, 2013 at 18:26
  • 1
    $\begingroup$ Maybe Tischler's "Solving Decidability Problems with Interval Arithmetic" would be of some help? (You can google the paper name to find a free copy.) $\endgroup$ Jun 19, 2013 at 20:01
  • 1
    $\begingroup$ Did you mean to write $f:D \to D$ rather than $f:D \to \mathbb R$? $\endgroup$ Jun 19, 2013 at 20:05
  • 1
    $\begingroup$ You suspect that $f$ is a contraction, so that means you've already selected a metric space...do you want use a specific metric space? $\endgroup$
    – Suvrit
    Sep 30, 2013 at 1:38

0

Your Answer

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