ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Multivariate Polynomial Computations and Polynomial Systems

Mon 16:30–17:00, Room AV 91.12
Efficient matricial methods for the computation of the Bernstein coefficients over a box and a simplex
Jihad Titi (University of Konstanz)
Joint work with J├╝rgen Garloff (Department of Mathematics and Statistics, University of Konstanz, Germany and Institute for Applied Research, University of Applied Sciences/ HTWG Konstanz, Germany)

The underlying problems of our talk are unconstrained and constrained global polynomial optimization problems over boxes and simplices. One approach for their solution is based on the expansion of a (multivariate) polynomial into Bernstein polynomials of the objective function and the constraints polynomials. This approach has the advantage that it does not require function evaluations which might be costly if the degree of the polynomials involved is high.

The coefficients of this expansion are called the Bernstein coefficients. These coefficients can be rearranged in a multi-dimensional array, the so-called Bernstein patch. From these coefficients we get bounds for the range of the objective function and the constraints over a box or a simplex, see [1], [2]. We can improve the enclosure for the range of the polynomial under consideration by elevating the degree of its Bernstein expansion or by subdivision of the region. Subdivision is more efficient than degree elevation. The complexity of the traditional approach for the computation of these coefficients is exponential in the number of the variables.

In [1] Garloff proposed a method for computing the Bernstein coefficients of a bivariate polynomial over the unit box and the unit triangle by using a forward difference operator. We propose two efficient matricial methods that involve only matrix operations such as multiplication, transposition, and reshaping as Ray and Nataraj's method, see [3]. Our methods are superior over Garloff's and Ray and Nataraj's method for the computation of the Bernstein coefficients over the unit and a general box and the standard simplex. We also propose a matricial method for the computation of the Bernstein coefficients over subboxes and subsimplices when the original box and simplex are subdivided, respectively.

  1. J. Garloff, Convergent bounds for the range of multivariate polynomials, Interval Mathematics 1985, K. Nickel, Ed., Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, New York, vol. 212 (1986), pp. 37–56.
  2. R. Leroy, Convergence under subdivision and complexity of polynomial minimization in the simplicial Bernstein basis, Reliab. Comput., 17 (2012), pp. 11–21.
  3. S. Ray and P.S.V. Nataraj, A Matrix method for efficient computation of Bernstein coefficients, Reliab. Comput., 17(1) (2012), pp. 40–71.