Julien Ugon

Jean-Pierre Crouzeix, Nadezda Sukhorukova, Julien Ugon

One of the purposes in this paper is to provide a better understanding of the alternance property which occurs in Chebyshev polynomial approximation and piecewise polynomial approximation problems. In the first part of this paper, we propose an original approach to obtain new proofs of the well known necessary and sufficient optimality conditions. There are two main advantages of this approach. First of all, the proofs are much simpler and easier to understand than the existing proofs. Second, these proofs are constructive and therefore they lead to alternative-based algorithms that can be considered as Remez-type approximation algorithms. In the second part of this paper, we develop new local optimality conditions for free knot polynomial spline approximation. The proofs for free knot approximation are relying on the techniques developed in the first part of this paper.

Vinesha Peiris, Reinier Diaz Millan, Nadezda Sukhorukova et al.

Rational and neural network based approximations are efficient tools in modern approximation. These approaches are able to produce accurate approximations to nonsmooth and non-Lipschitz functions, including multivariate domain functions. In this paper we compare the efficiency of function approximation using rational approximation, neural network and their combinations. It was found that rational approximation is superior to neural network based approaches with the same number of decision variables. Our numerical experiments demonstrate the efficiency of rational approximation, even when the number of approximation parameters (that is, the dimension of the corresponding optimisation problems) is small. Another important contribution of this paper lies in the improvement of rational approximation algorithms. Namely, the optimisation based algorithms for rational approximation can be adjusted to in such a way that the conditioning number of the constraint matrices are controlled. This simple adjustment enables us to work with high dimension optimisation problems and improve the design of the neural network. The main strength of neural networks is in their ability to handle models with a large number of variables: complex models are decomposed in several simple optimisation problems. Therefore the the large number of decision variables is in the nature of neural networks.

Nadezda Sukhorukova, Julien Ugon

In this paper we propose a new approach to least squares approximation problems. This approach is based on partitioning and Schur function. The nature of this approach is combinatorial, while most existing approaches are based on algebra and algebraic geometry. This problem has several practical applications. One of them is curve clustering. We use this application to illustrate the results.

Nadezda Sukhorukova, Julien Ugon, David Yost

The theory of Chebyshev (uniform) approximation for univariate polynomial and piecewise polynomial functions has been studied for decades. The optimality conditions are based on the notion of alternating sequence. However, the extension the notion of alternating sequence to the case of multivariate functions is not trivial. The contribution of this paper is two-fold. First of all, we give a geometrical interpretation of the necessary and sufficient optimality condition for multivariate approximation. These optimality conditions are not limited to the case polynomial approximation, where the basis functions are monomials. Second, we develop an algorithm for fast necessary optimality conditions verifications (polynomial case only). Although, this procedure only verifies the necessity, it is much faster than the necessary and sufficient conditions verification. This procedure is based on a point reduction procedure and resembles the univariate alternating sequence based optimality conditions. In the case of univariate approximation, however, these conditions are both necessary and sufficient. Third, we propose a procedure for necessary and sufficient optimality conditions verification that is based on a generalisation of the notion of alternating sequence to the case of multivariate polynomials.

Nadezda Sukhorukova, Julien Ugon

In this paper, we derive a necessary condition for a best approximation by piecewise polynomial functions. We apply nonsmooth nonconvex analysis to obtain this result, which is also a necessary and sufficient condition for inf-stationarity in the sense of Demyanov-Rubinov. We start from identifying a special property of the knots. Then, using this property, we construct a characterization theorem for best free knots polynomial spline approximation, which is stronger than the existing characterisation results when only continuity is required.