## Matrix Methods for the Tensorial and Simplicial Bernstein Forms with Application to Global Optimization

2019
Dissertation
Published
##### Abstract
Many real-world and scientific problems encountered in, e.g., graph theory, signal and image processing, chemical engineering, to name only a few, require the solution of polynomial optimization problems, which have a polynomial objective function and polynomial constraints. Moreover, numerous problems in design and analysis of control systems can be formulated as a system of inequalities involving multivariate polynomials. The branch and bound method is known as one of the most powerful and commonly employed methods for solving global optimization problems. The methodology of this method is summarized as successively splitting (branching) of the search region into smaller parts and adopting a bounding approach to decide whether it is worthwhile to explore any or all of the newly created subregions. Indeed, the bounding approach is a means to discard subregions that cannot contain a global minimizer and to determine the optimal value of the problem under consideration (within a prescribed tolerance of accuracy). Therefore, the ability to compute tight enclosures for the range of the objective function and the constraints polynomials over the considered search region is required. In the case of polynomial global optimization problems, where the search regions are boxes or simplices, one can make use of the expansion of the objective function and constraints polynomials into Bernstein polynomials. The coefficients of these expansions, the so-called tensorial and simplicial Bernstein coefficients, exhibit remarkable properties, in particular, the capability to provide an enclosure for the range of the underlying polynomial over the box or simplex. This property makes the Bernstein approach especially suited for the solution of polynomial global optimization problems and systems of equations and inequalities compared to the other approaches like the use of interval methods.

In this work, efficient matrix methods for the calculation of the tensorial and simplicial Bernstein coefficients over the unit box or a general box, and the standard simplex, respectively, are developed. In the tensorial case, the proposed methods are superior to the existing methods. For the calculation of the Bernstein coefficients over subboxes and subsimplicies that are generated by subdivision, two new matrix methods are presented and compared with the de Casteljau algorithm; which algorithm is preferable depends on the number of variables, the polynomial degree, and over which subbox or subsimplex the Bernstein coefficients are required to be computed. Matrix methods for the computation of the Bernstein coefficients of a multivariate polynomial from those of its partial derivatives, and for the product of two polynomials are given. For the evaluation of a polynomial in the tensorial and simplicial Bernstein representation, matrix methods are presented as well. In the case that the coefficients of the polynomial are due to uncertainties and can be represented in the form of intervals, it is shown that the new tensorial methods can be extended to compute the set of the Bernstein coefficients of all members of the polynomial family.

The minimum and the maximum tensorial and simplicial Bernstein coefficients constitute the so-called tensorial and simplicial Bernstein forms, respectively. Moreover, for a given rational function, the tensorial and simplicial Bernstein expansions of the numerator and denominator polynomials are used to build the tensorial and simplicial rational Bernstein forms, which provide enclosures for the range of the rational function over a box and a simplex. The convergence behaviour of these enclosures to the range of the given polynomial or rational function when the degree of the corresponding Bernstein expansion is elevated and when the underlying box or simplex is subdivided is investigated as well.

The problems of obtaining an upper bound for the maximum of the modulus and bounding the range of complex polynomials over a complex interval or a complex box are addressed. For the first problem, the Bernstein coefficients of the two multivariate real polynomials, one for the real part and the other for the imaginary part of the given complex polynomial, are employed. For the latter problem, the convex hull of the Bernstein coefficients of the polynomial over the four line segments and faces bordering the interval and the box forms an enclosure for the range of the polynomial over the considered interval and box, respectively. Matrix methods are proposed for computing the Bernstein coefficients thereupon, which are extended to the case of a rational complex function. In addition, the convergence of the resulting upper bounds to the maximum modulus of a multivariate complex polynomial over a complex box as well as the convergence of the convex hull of the Bernstein coefficients to the range of the polynomial over the box with respect to degree elevation and subdivision are investigated. Moreover, the inclusion isotonicity property of the Bernstein enclosures of a multivariate complex polynomial and a rational complex function over a complex box is stated. A matrix method for the calculation of the Bernstein coefficients of a degree elevated expansion of a given complex polynomial over a complex box from those of the lower degree expansion of the real or imaginary part polynomials is also derived.

Tests for speeding up the determination of the simplicial polynomial and rational Bernstein forms are presented. For the fast computation of the tensorial Bernstein form, existing tests and one of the proposed matrix methods are combined. If they are also combined with the implicit Bernstein representation, the resulting procedure leads to a significant reduction of the number of the required arithmetic operations.

Finally, applications of the Bernstein approach to the solution of polynomial global minimization problems are discussed.
510 Mathematics
##### Keywords
Bernstein Polynomials, Bernstein Coefficents, Range Enclosure, Optimization, Complex Polynomial, Matrix Methods, De Casteljau Algorithm, Simplex, Box, Polynomial Global Minimization Problems
##### Cite This
ISO 690TITI, Jihad, 2019. Matrix Methods for the Tensorial and Simplicial Bernstein Forms with Application to Global Optimization [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Titi2019Matri-46468,
year={2019},
title={Matrix Methods for the Tensorial and Simplicial Bernstein Forms with Application to Global Optimization},
school={Universität Konstanz}
}

RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<dcterms:issued>2019</dcterms:issued>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-07-19T11:02:26Z</dcterms:available>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/46468/3/Titi_2-k106crqmste71.pdf"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-07-19T11:02:26Z</dc:date>
<dcterms:title>Matrix Methods for the Tensorial and Simplicial Bernstein Forms with Application to Global Optimization</dcterms:title>
<dc:rights>terms-of-use</dc:rights>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
<dc:language>eng</dc:language>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:abstract xml:lang="eng">Many real-world and scientific problems encountered in, e.g., graph theory, signal and image processing, chemical engineering, to name only a few, require the solution of polynomial optimization problems, which have a polynomial objective function and polynomial constraints. Moreover, numerous problems in design and analysis of control systems can be formulated as a system of inequalities involving multivariate polynomials. The branch and bound method is known as one of the most powerful and commonly employed methods for solving global optimization problems. The methodology of this method is summarized as successively splitting (branching) of the search region into smaller parts and adopting a bounding approach to decide whether it is worthwhile to explore any or all of the newly created subregions. Indeed, the bounding approach is a means to discard subregions that cannot contain a global minimizer and to determine the optimal value of the problem under consideration (within a prescribed tolerance of accuracy). Therefore, the ability to compute tight enclosures for the range of the objective function and the constraints polynomials over the considered search region is required. In the case of polynomial global optimization problems, where the search regions are boxes or simplices, one can make use of the expansion of the objective function and constraints polynomials into Bernstein polynomials. The coefficients of these expansions, the so-called tensorial and simplicial Bernstein coefficients, exhibit remarkable properties, in particular, the capability to provide an enclosure for the range of the underlying polynomial over the box or simplex. This property makes the Bernstein approach especially suited for the solution of polynomial global optimization problems and systems of equations and inequalities compared to the other approaches like the use of interval methods.&lt;br /&gt;&lt;br /&gt;In this work, efficient matrix methods for the calculation of the tensorial and simplicial Bernstein coefficients over the unit box or a general box, and the standard simplex, respectively, are developed. In the tensorial case, the proposed methods are superior to the existing methods. For the calculation of the Bernstein coefficients over subboxes and subsimplicies that are generated by subdivision, two new matrix methods are presented and compared with the de Casteljau algorithm; which algorithm is preferable depends on the number of variables, the polynomial degree, and over which subbox or subsimplex the Bernstein coefficients are required to be computed. Matrix methods for the computation of the Bernstein coefficients of a multivariate polynomial from those of its partial derivatives, and for the product of two polynomials are given. For the evaluation of a polynomial in the tensorial and simplicial Bernstein representation, matrix methods are presented as well. In the case that the coefficients of the polynomial are due to uncertainties and can be represented in the form of intervals, it is shown that the new tensorial methods can be extended to compute the set of the Bernstein coefficients of all members of the polynomial family.&lt;br /&gt;&lt;br /&gt;The minimum and the maximum tensorial and simplicial Bernstein coefficients constitute the so-called tensorial and simplicial Bernstein forms, respectively. Moreover, for a given rational function, the tensorial and simplicial Bernstein expansions of the numerator and denominator polynomials are used to build the tensorial and simplicial rational Bernstein forms, which provide enclosures for the range of the rational function over a box and a simplex. The convergence behaviour of these enclosures to the range of the given polynomial or rational function when the degree of the corresponding Bernstein expansion is elevated and when the underlying box or simplex is subdivided is investigated as well.&lt;br /&gt;&lt;br /&gt;The problems of obtaining an upper bound for the maximum of the modulus and bounding the range of complex polynomials over a complex interval or a complex box are addressed. For the first problem, the Bernstein coefficients of the two multivariate real polynomials, one for the real part and the other for the imaginary part of the given complex polynomial, are employed. For the latter problem, the convex hull of the Bernstein coefficients of the polynomial over the four line segments and faces bordering the interval and the box forms an enclosure for the range of the polynomial over the considered interval and box, respectively. Matrix methods are proposed for computing the Bernstein coefficients thereupon, which are extended to the case of a rational complex function. In addition, the convergence of the resulting upper bounds to the maximum modulus of a multivariate complex polynomial over a complex box as well as the convergence of the convex hull of the Bernstein coefficients to the range of the polynomial over the box with respect to degree elevation and subdivision are investigated. Moreover, the inclusion isotonicity property of the Bernstein enclosures of a multivariate complex polynomial and a rational complex function over a complex box is stated. A matrix method for the calculation of the Bernstein coefficients of a degree elevated expansion of a given complex polynomial over a complex box from those of the lower degree expansion of the real or imaginary part polynomials is also derived.&lt;br /&gt;&lt;br /&gt;Tests for speeding up the determination of the simplicial polynomial and rational Bernstein forms are presented. For the fast computation of the tensorial Bernstein form, existing tests and one of the proposed matrix methods are combined. If they are also combined with the implicit Bernstein representation, the resulting procedure leads to a significant reduction of the number of the required arithmetic operations.&lt;br /&gt;&lt;br /&gt;Finally, applications of the Bernstein approach to the solution of polynomial global minimization problems are discussed.</dcterms:abstract>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46468"/>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/46468/3/Titi_2-k106crqmste71.pdf"/>
</rdf:Description>
</rdf:RDF>

June 27, 2019
##### University note
Konstanz, Univ., Doctoral dissertation, 2019