Demystifying the characterization of SDP matrices in mathematical programming

EasyChair Preprint 2530

Abstract

This communication presents a 100 pages introduction to SDP programming. This manuscript was written because I found no other introduction to SDP programming  that targets the same public. This work is intended to be accessible to anybody who does not hate maths, who knows what is a derivative and accepts (or has a proof of) results like det(AB)=det(A)det(B). If you know this, I think you can understand most of this introduction to SDP without needing other books; the goal of this manuscript is not to remind/enumerate a list of results but to (try to) make the reader examine (the proofs of) these results so as to get full insight into them. A important step to understand SDP programming is to get full insight into the (proofs of) the eigen-decomposition. There are many other published introductions to SDP programming that merit all our consideration, but the way they address this eigen-decomposition suffices to show how their target audience is simply different.

A difference compared to most other introductions to SDP  is that this work comes out of a mind that was itself struggling to understand and not from (the heights of) a long established expert. This may seem to be only a weakness, but, paradoxically, it is both a weakness and a strength. One strength comes from the fact that many established experts tend to forget the difficulties of beginners, which, I hope, did not happen to me. Other experts try to make all proofs as short as possible and to dismiss as unimportant certain key results they have seen thousands of time in their career. I also avoided this as well. There is a further reason for not adopting the formal style of a well established expert: I do not want to transform the relationship between the author and the reader into a (dry and) formal professor$\to$student relationship; on the contrary, I try to actually minimize the distance between the author and the reader, even hoping to achieve a certain level of mutual empathy.

Keyphrases: Optimisation combinatoire, décompositions de matrices, optimisation SDP

@booklet{EasyChair:2530,
  author    = {Daniel Porumbel},
  title     = {Demystifying the characterization of SDP matrices in mathematical programming},
  howpublished = {EasyChair Preprint 2530},
  year      = {EasyChair, 2020}}