primaldualtekniikat

Primaldualtekniikat viittaavat optimointimenetelmiin, joissa ratkaistavaa ongelmaa lähestytään sekä primal- että dualmuodossa ja niiden välistä suhdetta hyödyntäen. Keskeinen idea on Lagrangianin ja KKT-ehtojen käyttö sekä tasapainotilan hyödyntäminen: optimaaliset primal- ja dualiratkaisut muodostavat yhdessä hyväksyttävän ja usein todentavan ratkaisun. Näitä tekniikoita sovelletaan erityisesti konveksisissa ja osin konveksissa ongelmissa, joissa rajoitteet voidaan ilmaista Lagrangianin kautta.

Tunnettuja esimerkkejä ovat primal-dual interior-point -menetelmät, joita käytetään lineaaristen ja semidefinite-ohjelmien ratkaisemisessa, sekä primal-dual split -menetelmät kuten Chambolle–Pock -algoritmi, joka hyödyntää proximoperoja nonsmoottien termien käsittelyyn. ADMM (alternating direction method of multipliers) nähdään usein myös primal-dualina, kun ongelma hajotetaan osiin ja päivityksiä tehdään primal- ja dual-tilojen vuorotellen. Näitä menetelmiä sovelletaan laajasti laskennan suurissa skaaloissa sekä rakenteellisesti hajautetuissa ratkaisuissa.

Keskeisiä käsitteitä ovat dualiteetti, dualiteettiväli ja Lagrangian, joiden avulla voidaan muodostaa hakuaikojen minimi–maksimi tai saddle-pisteen kaltaiset muodostelmat. Konvergenssiin vaikuttavat usein konveksisuus ja säännöllisyys; nonsmootteja kohdattaessa proximoperoiden käyttö on tavallista. Primaldualitekniikat mahdollistavat tehokkaan hyödyntämisen ongelmien rakenteesta, tarjoavat usein aikahyötyä ja mahdollistavat rinnakkaisen laskennan.

Sovellusalueita ovat kuvankäsittely, kuvan- ja signaalin rekonstruointi, pakotettujen oppimisongelmien ratkaisut, verkko- ja hallintosovellukset sekä monet muut konveksit optimointitehtävät. Rajoitteina ovat konveksisuuden tarve ja parametrisoinnin herkkä valinta, jotka vaikuttavat konvergenssiin ja lopulliseen ratkaisuun.