We have been developing algorithms for detecting "robust" zeros of multidimensional functions $f: X\to\Bbb R^n$ where $X$ is an $m$-dimensional domain in $\Bbb R^m$. More precisely, for a given $f$, we can compute an $r>0$ such that every continuous $g$, $\|g-f\|<r$ has a nonempty zero set in $X$ (under some quite weak conditions). This can be used for proving that the initial map $f$ has a zero even in cases when it is given only approximately, such as a list of function values in a multidimensional grid and a Lipschitz constant.

More involved robust properties of the zero set of $f$ could be analysed. For instance we can find "robust optima" over the zero set with the uncertainty when an additional objective function is given.

Can these algorithms have some natural applications in engineering and/or scientific computations? In some sense, it generalizes solving systems of equations to the case where the input is uncertain.

The mathematics behind the algorithm is nice and nontrivial (and has been the main motivating force for us so far), but the further development makes the best sense if we had specific problems to solve.

  • 1
    $\begingroup$ Does your algorithm compute all zeros, or just a few of them? Your description appears to have natural applications in robust optimization, since an uncertain $f$ could simply be the KKT optimality conditions to an optimization problem with uncertain data. $\endgroup$ – Richard Zhang Nov 3 '15 at 18:36
  • $\begingroup$ @Richard Zhang It computes a region which provably contains zeros not only of $f$ but also of any continuous $g$ such that $\|g-f\|<r$ where $r$ is a parameter. We cannot "compute" all zeros explicitly in general as in case of under-determined systems the zero set is typically a higher-dimensional manifold. But we can still "detect" its nonemptyness (and some further properties) in some isolating neighborhood. Yes, robust optimization is definitely one applications we have in mind. Thanks for the KKT hint.. $\endgroup$ – peter franek Nov 3 '15 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.