ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-07022008-181656


Tipo di tesi
Tesi di dottorato di ricerca
Autore
ZHANG, QINGHUA
Indirizzo email
zhang@di.unipi.it
URN
etd-07022008-181656
Titolo
Outer Approximation Algorithms for DC Programs and Beyond
Settore scientifico disciplinare
MAT/09
Corso di studi
MATEMATICA
Relatori
Relatore Prof. Frangioni, Antonio
Relatore Prof. Bigi, Giancarlo
Parole chiave
  • DC Optimization
Data inizio appello
23/06/2008
Consultabilità
Completa
Riassunto
We consider the well-known Canonical DC (CDC)
optimization problem, relying on an alternative equivalent formulation based on a polar characterization of the constraint, and
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.

We introduce of the concept of ``approximate oracle'' for the optimality conditions of (CDC) and (SRP), and make a thorough study of the impact of approximations in the optimality conditions onto
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.

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
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't be reduced to the original cutting plane algorithm for (CDC) and its modifications; the connections of our
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