Enclosure Methods for Systems of Polynomial Equations and Inequalities

Lade...
Vorschaubild
Dateien
Diss_Smith.pdf
Diss_Smith.pdfGröße: 2.16 MBDownloads: 1250
Datum
2012
Autor:innen
Smith, Andrew Paul
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Angaben zur Forschungsförderung (Freitext)
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
Erschienen in
Zusammenfassung

Many problems in applied mathematics can be formulated as a system of nonlinear equations or inequalities, and a broad subset are those problems consisting either partially or completely of multivariate polynomials. Broadly speaking, an ‘enclosure’ method attempts to solve such a problem over a specified region of interest, commonly a box subset of Rn, where n is the number of unknowns. Subdivision (or branch-and-bound) is a commonlyapplied scheme, wherein a starting box is successively subdivided into sub-boxes; sub-boxes for which a proof of non-existence of a solution can be completed are discarded. As a component of such, a boundary method attempts to exploit the properties of component functions over the boundary of a sub-box, without considering their behaviour within it.

Two main types of non-existence proof are considered for polynomial systems over boxes or sub-boxes. Firstly, the topological degree of a system of equations (considered as a mapping from Rn to Rn) can be computed over a sub-box, which possesses a root-counting property. Together with an enclosure for the determinant of the Jacobian, the existence (or otherwise) of roots in the sub-box can be ascertained. Secondly, and alternatively, a range-enclosing method can be used to compute a guaranteed outer enclosure for the range of a multivariate polynomial over a sub-box; if it does not contain zero, a root is excluded. The Bernstein expansion is used, due to the tightness of the enclosure yielded and its rate of convergence to the true enclosure. In both cases, interval arithmetic is employed to obtain guaranteed enclosures and ensure the rigour of these existence tests.

Advances have been made in four main areas. Firstly, an existing recursive algorithm for the computation of topological degree is investigated in detail, including a complexity analysis, and algorithmic improvements are proposed. Secondly, a simple branch-and-bound method for systems of polynomial equations, utilising Bernstein expansion and an existence test by Miranda, is developed, and alternative subdivision strategies are considered. Thirdly, a major improvement of the Bernstein expansion itself is achieved with the development of the implicit Bernstein form, which exhibits greatly improved performance for many categories of polynomials. Finally, several new methods are developed and compared for the computation of affine lower bounding functions for polynomials, which may be employed in branch-and-bound schemes for problems involving inequalities, such as global optimisation problems. Numerical results and an overview of the developed software are given.

Zusammenfassung in einer weiteren Sprache

Viele Probleme der angewandten Mathematik können als Systeme nichtlinearer Gleichungen oder Ungleichungen formuliert werden. Eine große Teilmenge davon besteht teilweise oder vollständig aus multivariablen Polynomen. Die Idee einer Einschließungsmethode löst ein solches Problem innerhalb einer relevanten Region. Gewöhnlich ist diese Region eine Box-Teilmenge von Rn, wobei n die Anzahl der Unbekannten ist. Subdivision (oder Branch-and-Bound) ist ein oft verwendetes Schema, bei dem eine Anfangsbox sukzessiv in Subboxen unterteilt wird. Subboxen, für die die Nichtexistenz einer Lösung bewiesen werden kann, werden ausgeschlossen. Als Bestandteil dieses Schemas ist die Randmethode, die versucht die Randeigenschaften der Komponentenfunktionen bezüglich der Subbox auszunutzen ohne dabei das Verhalten innerhalb der Subbox zu betrachten.

Die Nichtexistenzbeweise für Systeme polynomer Gleichungen über Boxen oder Subboxen werden durch zwei Haupttypen beschrieben. Der erste Typ kann durch den topologischen Grad eines Gleichungssystems (als eine Abbildung von Rn auf Rn) über eine Subbox beschrieben werden. Diese besitzt die Eigenschaft, die Anzahl der Wurzeln zählen zu können. Dabei kann die Existenz (oder Nichtexistenz) von Wurzeln in dieser Subbox durch die Bestimmung einer Einschließung der Determinanten der Jacobi-Matrix ermittelt werden. Als zweiter Grundtyp bildet die Bereichseinschließungmethode, die eine äußere Einschränkung des Bildbereichs eines multivariablen Polynoms durch eine Subbox garantiert. Enthält dieses Intervall nicht Null, so kann auch das Vorkommen einer Wurzel ausgeschlossen werden. Fokus der Bernstein-Erweiterung ist die Bestimmung präziserer Grenzen für die Einschließung und eine schnellere Konvergenz gegen die exakte Einschließung. Um eine garantierte Einschließung und die Korrektheit dieses Existenz-Tests sicherzustellen, wird in beiden Fällen die Intervallarithmetik angewandt.

Es wurden Fortschritte in vier Bereichen erzielt. Erstens wurde ein existierender rekursiver Algorithmus für die Berechnung des topologischen Grads detailiert untersucht. Dabei liegt die Betonung auf die Komplexitätsanalyse und algorithmische Verbesserung und Erweiterungen. Der zweite Bereich beschäftigt sich zunächst mit einer einfachen Branch-and-Bound-Methode für polynome Gleichungssysteme. Dafür wurden die Bernstein-Erweiterung und der Existenz-Test von Miranda verwendet. Weiterhin wurden alternative Strategien zur Subdivision in Betracht gezogen. Drittens wurde eine wesentliche Verbesserung der Bernstein-Erweiterung durch die Entwicklung der impliziten Bernstein-Form erzielt. Es zeigt sich eine starke Verbesserung der Leistung für viele Arten von Polynomen. Abschließend wurden mehrere neue Verfahren für die Berechnung von unteren affinen Grenzfunktionen für Polynome entwickelt und miteinander verglichen. Diese neue Verfahren können für Branch-and-Bound-Verfahren bei Problemen mit Ungleichungen, wie z.B. globale Optimierungsprobleme, eingesetzt werden. Numerische Ergebnisse und eine Übersicht der entwickelten Software liegen vor.

Fachgebiet (DDC)
510 Mathematik
Schlagwörter
interval arithmetic, Bernstein expansion, polynomial approximation, topological degree
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690SMITH, Andrew Paul, 2012. Enclosure Methods for Systems of Polynomial Equations and Inequalities [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Smith2012Enclo-20898,
  year={2012},
  title={Enclosure Methods for Systems of Polynomial Equations and Inequalities},
  author={Smith, Andrew Paul},
  address={Konstanz},
  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#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/20898">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20898/1/Diss_Smith.pdf"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20898/1/Diss_Smith.pdf"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Smith, Andrew Paul</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-11-21T10:43:53Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/39"/>
    <dc:language>eng</dc:language>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/20898"/>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:title>Enclosure Methods for Systems of Polynomial Equations and Inequalities</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Smith, Andrew Paul</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-11-21T10:43:53Z</dc:date>
    <dcterms:issued>2012</dcterms:issued>
    <dcterms:abstract xml:lang="eng">Many problems in applied mathematics can be formulated as a system of nonlinear equations or inequalities, and a broad subset are those problems consisting either partially or completely of multivariate polynomials. Broadly speaking, an ‘enclosure’ method attempts to solve such a problem over a specified region of interest, commonly a box subset of R&lt;sup&gt;n&lt;/sup&gt;, where n is the number of unknowns. Subdivision (or branch-and-bound) is a commonlyapplied scheme, wherein a starting box is successively subdivided into sub-boxes; sub-boxes for which a proof of non-existence of a solution can be completed are discarded. As a component of such, a boundary method attempts to exploit the properties of component functions over the boundary of a sub-box, without considering their behaviour within it.&lt;br /&gt;&lt;br /&gt;Two main types of non-existence proof are considered for polynomial systems over boxes or sub-boxes. Firstly, the topological degree of a system of equations (considered as a mapping from R&lt;sup&gt;n&lt;/sup&gt; to R&lt;sup&gt;n&lt;/sup&gt;) can be computed over a sub-box, which possesses a root-counting property. Together with an enclosure for the determinant of the Jacobian, the existence (or otherwise) of roots in the sub-box can be ascertained. Secondly, and alternatively, a range-enclosing method can be used to compute a guaranteed outer enclosure for the range of a multivariate polynomial over a sub-box; if it does not contain zero, a root is excluded. The Bernstein expansion is used, due to the tightness of the enclosure yielded and its rate of convergence to the true enclosure. In both cases, interval arithmetic is employed to obtain guaranteed enclosures and ensure the rigour of these existence tests.&lt;br /&gt;&lt;br /&gt;Advances have been made in four main areas. Firstly, an existing recursive algorithm for the computation of topological degree is investigated in detail, including a complexity analysis, and algorithmic improvements are proposed. Secondly, a simple branch-and-bound method for systems of polynomial equations, utilising Bernstein expansion and an existence test by Miranda, is developed, and alternative subdivision strategies are considered. Thirdly, a major improvement of the Bernstein expansion itself is achieved with the development of the implicit Bernstein form, which exhibits greatly improved performance for many categories of polynomials. Finally, several new methods are developed and compared for the computation of affine lower bounding functions for polynomials, which may be employed in branch-and-bound schemes for problems involving inequalities, such as global optimisation problems. Numerical results and an overview of the developed software are given.</dcterms:abstract>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
October 5, 2012
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Begutachtet
Diese Publikation teilen