ETD system

Electronic theses and dissertations repository

 

Tesi etd-07022008-181656


Thesis type
Tesi di dottorato di ricerca
Author
ZHANG, QINGHUA
email address
zhang@di.unipi.it
URN
etd-07022008-181656
Title
Outer Approximation Algorithms for DC Programs and Beyond
Settore scientifico disciplinare
MAT/09
Corso di studi
MATEMATICA
Commissione
Relatore Prof. Frangioni, Antonio
Relatore Prof. Bigi, Giancarlo
Parole chiave
  • DC Optimization
Data inizio appello
23/06/2008;
Consultabilità
completa
Riassunto analitico
We consider the well-known Canonical DC (CDC)<br>optimization problem, relying on an alternative equivalent formulation based on a polar characterization of the constraint, and<br>a novel generalization of this problem, which we name Single Reverse Polar problem (SRP). We study the theoretical properties of the new class of (SRP) problems, and contrast them with those of (CDC)problems.<br><br>We introduce of the concept of ``approximate oracle&#39;&#39; for the optimality conditions of (CDC) and (SRP), and make a thorough study of the impact of approximations in the optimality conditions onto<br>the quality of the approximate optimal solutions, that is the feasible solutions which satisfy them. Afterwards, we develop very general hierarchies of convergence conditions, similar but not identical for (CDC) and (SRP), starting from very abstract ones and moving towards more readily implementable ones. Six and three different sets of conditions are proposed for (CDC) and (SRP), respectively.<br><br>As a result, we propose very general algorithmic schemes, based on approximate oracles and the developed hierarchies, giving rise to many different implementable algorithms, which can be<br>proven to generate an approximate optimal value in a finite number of steps, where the error can be managed and controlled. Among them, six different implementable algorithms for (CDC) problems, four of which are new and can&#39;t be reduced to the original cutting plane algorithm for (CDC) and its modifications; the connections of our<br>results with the existing algorithms in the literature are outlined. Also, three cutting plane algorithms for solving (SRP) problems are proposed, which seem to be new and cannot be reduced to each other.
File