Convexe optimalisatie

Convexe optimalisatie is een deelgebied van de wiskundige optimalisatie dat het probleem bestudeert van het minimaliseren van convexe functies over convexe verzamelingen (of, op equivalente wijze, het maximaliseren van concave functies over convexe verzamelingen). Veel klassen van convexe optimalisatieproblemen laten polynomiale tijdalgoritmen toe, terwijl wiskundige optimalisatie over het algemeen NP-moeilijk is.

Definitie

Abstracte vorm

Een convex optimalisatieprobleem wordt gedefinieerd door twee ingrediënten:

• De doelfunctie, een convexe functie met reële waarde van n variabelen, $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$;
• Het toegelaten gebied, dat een convexe deelverzameling is van $C\subseteq \mathbb {R} ^{n}$.

Het doel van het probleem is om een $\mathbf {x^{\ast }} \in C$ te vinden dat het infimum bereikt:

$\inf\{f(\mathbf {x} ):\mathbf {x} \in C\}$

Over het algemeen zijn er drie opties met betrekking tot het bestaan van een oplossing:

• Als een dergelijk punt x* bestaat, dan wordt dit een optimaal punt of optimale oplossing genoemd. De verzameling van alle optimale punten wordt de optimale verzameling genoemd. Het optimalisatieprobleem heet oplosbaar.
• Als $f$ onbegrensd is beneden $C$, of het infimum wordt niet bereikt, dan heet het optimalisatieprobleem grenzeloos.
• Anders, als $C$ is de lege verzameling, dan wordt gezegd dat het optimalisatieprobleem onhaalbaar is.

Eigenschappen

De volgende zijn een aantal nuttige eigenschappen van convexe optimalisatieproblemen:

• elk lokaal minimum is een globaal minimum;
• de optimale verzameling is convex;
• als de doelfunctie strikt convex is, da heeft het probleem hoogstens één optimaal punt.

Deze resultaten worden gebruikt door de theorie van convexe minimalisatie, samen met meetkundige begrippen uit de functionaalanalyse (in hilbertruimten) zoals de hilbertprojectiestelling, de scheidende hypervlakstelling en het lemma van Farkas.