Alexandre Goldsztejn

Alexandre Goldsztejn

Uniform polynomial approximation, also called minimax approximation or Chebyshev approximation, consists in searching polynomial approximation that minimizes the worst case error. Optimality conditions for the uniform approximation of univariate functions defined in an interval are governed by the equioscillation theorem, which is also a key ingredient in algorithms for computing best uniform approximation, like Remez's algorithm and the two phase method. Multivariate polynomial approximation is more complicated, and several optimality conditions for uniform multivariate polynomial approximation generalize the equioscillation theorem. We review these conditions, including, from oldest to newest, Kirchberger's kernel condition, Kolmogorov criteria, Rivlin and Shapiro's annihilating measures. An emphasis is given to conditions for strong optimality, which has some strong theoretical and practical importance, including Bartelt's and Smarzewsky's conditions. Optimality conditions related to more general relative Chebyshev centers are also presented, including Tanimoto's and Levis et al.'s conditions. In a second step, conditions obtained by standard convex analysis, subdifferential and directional derivative, applied to uniform approximation are formulated. Their relationship to previous conditions is investigated, providing sometimes enlightening interpretations of the laters, e.g., relating Kolmogorov criterion with directional derivative, and strong uniqueness with sharp minimizers. Finally, numerical applications of the two-step approach to three uniform approximation problems are presented, namely the approximation of the multidimensional Runge function, the approximation of the two dimensional inverse model of the DexTAR parallel robot, and the approximation problem consisting in minimizing the sum of both the polynomial approximation error and the polynomial evaluation error in Horner form.

Alexandre Goldsztejn, Yahia Lebbah, Claude Michel et al.

Finding feasible points for which the proof succeeds is a critical issue in safe Branch and Bound algorithms which handle continuous problems. In this paper, we introduce a new strategy to compute very accurate approximations of feasible points. This strategy takes advantage of the Newton method for under-constrained systems of equations and inequalities. More precisely, it exploits the optimal solution of a linear relaxation of the problem to compute efficiently a promising upper bound. First experiments on the Coconuts benchmarks demonstrate that this approach is very effective.

Alexandre Goldsztejn, Claude Michel, Michel Rueher

This paper introduces a new algorithm for solving a sub-class of quantified constraint satisfaction problems (QCSP) where existential quantifiers precede universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and design. We propose here a new generic branch and prune algorithm for solving such continuous QCSPs. Standard pruning operators and solution identification operators are specialized for universally quantified inequalities. Special rules are also proposed for handling the parameters of the constraints. First experimentation show that our algorithm outperforms the state of the art methods.

Alexandre Goldsztejn

A new continuity for set-valued functions is introduced, and an existence theorem is proved for such continuous set-valued functions.

Frédéric Goualard, Alexandre Goldsztejn

Numerical methods based on interval arithmetic are efficient means to reliably solve nonlinear systems of equations. Algorithm bc3revise is an interval method that tightens variables' domains by enforcing a property called box consistency. It has been successfully used on difficult problems whose solving eluded traditional numerical methods. We present a new algorithm to enforce box consistency that is simpler than bc3revise, faster, and easily data parallelizable. A parallel implementation with Intel SSE2 SIMD instructions shows that an increase in performance of up to an order of magnitude and more is achievable.

Alexandre Goldsztejn

Proving the existence of a solution to a system of real equations is a central issue in numerical analysis. In many situations, the system of equations depend on parameters which are not exactly known. It is then natural to aim proving the existence of a solution for all values of these parameters in some given domains. This is the aim of the parametrization of existence tests. A new parametric existence test based on the Hansen-Sengupta operator is presented and compared to a similar one based on the Krawczyk operator. It is used as a basis of a fixed point iteration dedicated to rigorous sensibility analysis of parametric systems of equations.

Daisuke Ishii, Naoki Yonezaki, Alexandre Goldsztejn

Verification of temporal logic properties plays a crucial role in proving the desired behaviors of hybrid systems. In this paper, we propose an interval method for verifying the properties described by a bounded linear temporal logic. We relax the problem to allow outputting an inconclusive result when verification process cannot succeed with a prescribed precision, and present an efficient and rigorous monitoring algorithm that demonstrates that the problem is decidable. This algorithm performs a forward simulation of a hybrid automaton, detects a set of time intervals in which the atomic propositions hold, and validates the property by propagating the time intervals. A continuous state at a certain time computed in each step is enclosed by an interval vector that is proven to contain a unique solution. In the experiments, we show that the proposed method provides a useful tool for formal analysis of nonlinear and complex hybrid systems.

Alexandre Goldsztejn

The numerical computation of the exponentiation of a real matrix has been intensively studied. The main objective of a good numerical method is to deal with round-off errors and computational cost. The situation is more complicated when dealing with interval matrices exponentiation: Indeed, the main problem will now be the dependency loss of the different occurrences of the variables due to interval evaluation, which may lead to so wide enclosures that they are useless. In this paper, the problem of computing a sharp enclosure of the interval matrix exponential is proved to be NP-hard. Then the scaling and squaring method is adapted to interval matrices and shown to drastically reduce the dependency loss w.r.t. the interval evaluation of the Taylor series.