Programmazione semidefinita e rappresentazioni determinantali di polinomi omogenei

Abstract

La programmazione matematica, o ottimizzazione, è una branca della ricerca operativa il cui obiettivo è trovare i punti di massimo e minimo di una funzione matematica soggetta ad alcuni vincoli. Recentemente è cresciuto l’interesse verso la programmazione semidefinita, una generalizzazione della programmazione lineare. Il vincolo di un problema di programmazione semidefinita, espresso mediante una disuguaglianza matriciale, identifica uno spettraedro. Esiste uno stretto legame tra uno spettraedro e un interno algebrico, ovvero un insieme descritto mediante un polinomio. Assume quindi notevole importanza capire quando un polinomio, che descrive il dominio dei vincoli, può essere espresso mediante il determinante di una matrice di polinomi di primo grado. Quando un polinomio di grado r in n variabili a coefficienti complessi è il determinante di una matrice r × r? Questa domanda, in un certo senso classica e di semplice formulazione, ha radici profonde. Una risposta esauriente è storicamente attribuita a Dickson; i suoi risultati implicano che dato un polinomio omogeneo in tre variabili allora è possibile rappresentare tale polinomio come il determinante di una matrice. La tesi è suddivisa in tre capitoli: il primo è una raccolta di definizioni e risultati utili alla comprensione dell’elaborato; il secondo è dedicato alla programmazione semidefinita; il terzo è concentrato sui risultati di Dickson.

Mathematical programming, or optimization, is a branch of operations research that aims to find the maximum and minimum points of a mathematical function subject to certain constraints. Recently, there has been growing interest in semidefinite programming, a generalization of linear programming. The constraint of a problem of semidefinite programming, expressed through a matrix inequality, identifies a spectrahedron. There exists a close relationship between a spectrahedron and an algebraic interior, which is a set described by a polynomial. Understanding when a polynomial, describing the domain of constraints, can be expressed as the determinant of a matrix of first-degree polynomials is quite importance. When is a polynomial of degree r in n variables with complex coefficients the determinant of an r × r matrix? This question, somewhat classical and straightforward in its formulation, has deep roots. A comprehensive answer is historically attributed to Dickson; his results imply that a homogeneous polynomial in three variables can be represented as the determinant of a matrix. The thesis is divided into three chapters: the first is a collection of definitions and results useful for understanding the elaboration; the second is dedicated to semidefinite programming, and the third focuses on Dickson's results.