Semidefiniteohjelmoinnissa

Semidefiniteohjelmoinnissa (SDP) tarkastellaan optimointiongelmia, joissa optimoitava funktio on lineaarinen ja rajoitteet koostuvat lineaarisista yhtälöistä ja epäyhtälöistä, jotka koskevat positiivisia semidefiniittejä matriiseja. SDP on yleistys lineaarisesta ohjelmoinnista, ja se kuuluu konveksin optimoinnin piiriin.

SDP-ongelman yleinen muoto on seuraava: minimoi lineaarinen funktio c^T x koevektorille x, siten että matriisi F_0 + x_1 F_1 + ... + x_n F_n on positiivinen semidefiniitti, missä F_i ovat symmetrisiä matriiseja. Positiivinen semidefiniittisyys tarkoittaa, että kaikki matriisin ominaisarvot ovat epänegatiivisia.

SDP-ongelmat ovat laskennallisesti haastavampia kuin lineaariset ohjelmointiongelmat, mutta niitä voidaan ratkaista tehokkaasti sisäpistealgoritmeilla. SDP:llä on laaja sovellusalueita useilla tieteen ja tekniikan aloilla.

Esimerkiksi SDP:tä käytetään kombinatorisessa optimoinnissa, kuten maksimileikkausongelman approksimoinnissa. Sitä sovelletaan myös ohjausteoriassa kvadraattisten määritteiden rajoitteiden käsittelyyn ja koneoppimisessa. Positiivisen semidefiniittisyyden ehto tarjoaa voimakkaan rakenteen, joka mahdollistaa monien monimutkaisten ongelmien mallintamisen ja ratkaisemisen SDP:n avulla. SDP-ratkaisijat, kuten SeDuMi ja SDPT3, ovat laajasti käytettyjä työkaluja näiden ongelmien ratkaisemiseksi.