ETD system

Electronic theses and dissertations repository


Tesi etd-07022008-181656

Thesis type
Tesi di dottorato di ricerca
email address
Outer Approximation Algorithms for DC Programs and Beyond
Settore scientifico disciplinare
Corso di studi
Relatore Prof. Frangioni, Antonio
Relatore Prof. Bigi, Giancarlo
Parole chiave
  • DC Optimization
Data inizio appello
Riassunto analitico
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.