Relaxarea semidefinită în optimizarea pătratică cu variabile binare

Abstract

Lucrarea de faţă abordează cu ajutorul funcţiei Lagrange şi a programării semidefinite problema de programare pătratică cu restricţii pătratice în variabile binare. Problema de programare pătratică cu restricţii pătratice se reduce la o inegalitate matriceală în spaţiul matricelor semidefinite, care poate fi rezolvată cu ajutorul metodelor de punct interior.