An Unconstrained Minimization Method for Solving Low Rank SDP Relaxations of the Max Cut Problem
5,00 €
3,00 €
     
SINTESI
In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of the max cut problem. Using the Gramian representation of a positive semide¯nite matrix, the LRSDP problem is transformed into the non-convex nonlinear programming problem of minimizing a quadratic functionwith quadratic equality constraints. First, we establish some new relationships among these two formulations and we give necessary and sufficient conditions of global optimality. Then we propose a continuously differentiable exact merit function that exploits the special structure of the constraints and we use this function to define an efficient and globally convergent algorithm for the solution of the LRSDP problem. Finally, we test our code on an extended set of instances of the max cut problem and we report comparisons with other existing codes.
pagine: 48
formato: 17 x 24
ISBN: 978-88-548-1276-5
data pubblicazione: Luglio 2007
editore: Aracne
collana: Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2007/7
SINTESI
Informativa      Aracneeditrice.it si avvale di cookie, anche di terze parti, per offrirti il migliore servizio possibile. Cliccando 'Accetto' o continuando la navigazione ne acconsenti l'utilizzo. Per saperne di più
Accetto