Kvadratisk optimering

I matematisk optimering er et kvadratisk optimeringsproblem et optimeringsproblem, hvor vi minimerer (eller maksimerer) en kvadratisk funktion på en konveks polyhedron . De begrænsninger kan derfor beskrives ved lineære funktioner (en bør sige affine ). Den kvadratiske optimering er den disciplin, der studerer problemerne. Den lineære optimering kan ses som et specielt tilfælde af kvadratisk optimering.

Dette problem er i almindelighed NP-hårdt . I det særlige tilfælde af minimering af en konveks objektiv funktion er problemet polynomisk, og vi taler om konveks kvadratisk optimering ; en allerede meget rig disciplin med bedre kendte egenskaber.

Når kriteriet og begrænsningerne er kvadratisk optimeringsproblem, taler vi om enhver kvadratisk optimering (en) . Denne klasse af problemer indeholder al den polynomiale optimering og er derfor meget mere generel end den kvadratiske optimering.

Formulering af problemet

Et kvadratisk optimeringsproblem består i at minimere en kvadratisk funktion , ikke nødvendigvis konveks, på en konveks polyhedron . $q: \ mathbb {R} ^ {n} \ til \ mathbb {R}$

Kriterium skal minimeres

Funktionen $q$ er defineret i par $x = (x_ {1}, \ ldots, x_ {n}) \ i \ mathbb {R} ^ {n}$

${\ displaystyle q (x) = g ^ {\ mathsf {T}} x + {\ frac {1} {2}} \, x ^ {\ mathsf {T}} Hx = \ sum _ {i = 1} ^ {n} g_ {i} x_ {i} + {\ frac {1} {2}} \, \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {n} H_ {ij} x_ {i} x_ {j}.}$

I det første udtryk for $q ( x )$ er udtrykket i matrixform en vektor og er en symmetrisk reel matrix (denne antages generelt at være symmetrisk , fordi $q$ ikke ser den mulige antisymmetriske del af $H$ ). Der er ingen mening i at holde udtrykket konstant i $q$ , fordi det ikke påvirker løsningen af minimeringsproblemet. $g \ in \ mathbb {R} ^ {n}$ $H \ in \ mathbb {R} ^ {n \ gange n}$

Husk, at en sådan kvadratisk funktion $q$ er

konveks hvis og kun hvis matrixen $H$ er positiv semidefinit ,
strengt konveks, hvis og kun hvis matrixen $H$ er positiv bestemt .

Begrænsninger

Vi pålægger også den søgte vektor $x$ at tilhøre en konveks polyhedron , hvilket svarer til at sige, at $x$ skal tilfredsstille et endeligt antal affine begrænsninger. Disse kan tage forskellige former, såsom

${\ begin {array} {ll} l_ {B} \ leqslant x \ leqslant u_ {B} & {\ mbox {(bundne begrænsninger)}} \\ l_ {I} \ leqslant A_ {I} x \ leqslant u_ { I} og {\ mbox {(affine-ligestillingsbegrænsninger)}} \\ A_ {E} x = b_ {E} & {\ mbox {(affine-ligestillingsbegrænsninger),}} \ end {array}}$

udtryk, hvor vi har bemærket

$l B-$ og $u B-$ vektorer af kan derfor tage uendelige værdier og verificere $l$ $B$ $<$ $u$ $B$ , ${\ bar {\ mathbb {R}}} ^ {n}$
$A_ {I} \ in \ mathbb {R} ^ {m_ {I} \ gange n}$ en reel matrix af typen $m I \times n$ ( $A I x$ betegner produktet af matrixen $A I$ med vektoren $x$ ),
$l I$ og $l I$ vektorer af kan derfor tage uendelige værdier og verificere $l$ $I$ $<$ $u$ $I$ , ${\ bar {\ mathbb {R}}} ^ {m_ {I}}$
$A_ {E} \ in \ mathbb {R} ^ {m_ {E} \ times n}$ en reel matrix af typen $m E \times n$ ,
$b_ {E} \ in \ mathbb {R} ^ {m_ {E}}$ en ægte vektor.

Det vil være interessant at bruge den kompakte notation

$[l_ {B}, u_ {B}]: = \ {x \ in \ mathbb {R} ^ {n}: l_ {B} \ leqslant x \ leqslant u_ {B} \}$

og en lignende definition for $[ l I , u I ]$ . Vi betegner ved $X Q$ det tilladte sæt defineret af alle ovennævnte begrænsninger, nemlig

${\ displaystyle X_ {Q}: = \ {x \ in \ mathbb {R} ^ {n}: x \ in [l_ {B}, u_ {B}], ~ A_ {I} x \ in [l_ { I}, u_ {I}], ~ A_ {E} x = b_ {E} \}.}$

Kompakt formulering

På en kompakt måde kan vi derfor skrive det kvadratiske optimeringsproblem som følger

$(P_ {Q}) \ quad \ inf _ {x \ i X_ {Q}} \, q (x).$

Vi siger, at dette problem er konveks, hvis kriteriet $q$ er konveks , hvilket er tilfældet, hvis, og kun hvis, $H$ er positiv semidefinit.

Problemanalyse

Eksistensen af løsningen

Det grundlæggende resultat skyldes Frank og Wolfe (1956). Det er af samme type som den, der kendes i lineær optimering . lad os huske det

et optimeringsproblem siges at være gennemførligt, hvis det tilladte sæt er ikke-frit (hvilket svarer til at sige, at dets optimale værdi ikke er lig med $+ \infty$ ),
et mulig optimeringsproblem siges at være afgrænset, hvis dets optimale værdi ikke er værd $-\infty$ (man kan ikke finde en række tilladte punkter, der stræber efter kriteriet mod $-\infty$ ).

Eksistens af løsning - For et kvadratisk optimeringsproblem (ikke nødvendigvis konveks) er følgende egenskaber ækvivalente:

problemet har en løsning,
problemet er gennemførligt og begrænset,
den optimale værdi af problemet er endelig.

Det unikke ved løsningen vil helt sikkert forekomme, hvis $q$ er strengt konveks , men kan forekomme uden den. Dette er f.eks. Tilfældet med problemet med en enkelt variabel $inf { x : x \geq 0}$ , hvis kriterium er lineært (derfor ikke strengt konveks).

Fødselsdato

Her er en karakterisering af den afgrænsede (eller ubegrænsede) karakter af et gennemførligt konveks kvadratisk problem (det vil sige, hvoraf det tilladte sæt er ufordelagtigt) med hensyn til eksistensen af en retning, der har teoretiske interesser og digital. Det noterede $X \infty$ den asymptotiske kegle af sættet $X$ .

Fødselsgrad for et konveks kvadratisk problem - For et gennemførligt konveks kvadratisk optimeringsproblem , hvis tilladte polyhedrale sæt er angivet med $X$ , er følgende egenskaber ækvivalente:

problemet er ubegrænset,
der findes en retning $d$ sådan , og . $g ^ {\ top} d <0$ $Hd = 0$ $d \ i X ^ {\ infty}$

Den asymptotiske kegle i det tilladte sæt $X Q$ defineret ovenfor (antages ikke tom) er skrevet

$X_ {Q} ^ {\ infty} = \ {d \ in \ mathbb {R} ^ {n}: d \ in [l_ {B}, u_ {B}] ^ {\ infty}, ~ A_ {I} d \ i [l_ {I}, u_ {I}] ^ {\ infty}, ~ A_ {E} d = 0 \}.$

Udtrykket af $[ l , u ] \infty$ gives på siden på den asymptotiske kegle .

Opløsningsmetoder

Hvis der kun er begrænsninger for lighed, kommer problemet ned til at løse et lineært system. I nærvær af ulighedskrævninger er problemet generelt NP-hårdt og kan løses ved hjælp af følgende tilgange:

Aktiveringsalgoritme ,
Konjugeret gradientalgoritme (udvidelser),
Algoritme for den projicerede gradient ,
Augmented Lagrangian algoritme ,
Nelder-Mead-metode (udvidelser).
Indvendige punktalgoritmer (for konveks problem).

Tillæg

Bemærk

Se appendiks (i) til artiklen.
Se for eksempel Lemma 2.2 i artiklen af Chiche og Gilbert (2014).
Mange bidrag om dette emne. Artiklen af Delbos og Gilbert (2005) analyserer dens globale lineære konvergens, når problemet har en løsning; den fra Chiche og Gilbert (2014) analyserer adfærd, når problemet ikke er gennemførligt.

Relaterede artikler

Eksternt link

Operations Research Models and Methods (Paul A. Jensen og Jonathan F. Bard) [1]

Bibliografi

(en) A. Chiche, J. Ch. Gilbert (2016). Hvordan den udvidede Lagrangian-algoritme kan håndtere et umuligt konveks kvadratisk optimeringsproblem. Journal of Convex Analysis , 23: 2, 425-459.
(en) F. Delbos, J. Ch. Gilbert (2005). Global lineær konvergens af en udvidet Lagrangian-algoritme til løsning af konvekse kvadratiske optimeringsproblemer. Journal of Convex Analysis , 12, 45–69. [2]
(en) M. Frank, P. Wolfe (1956). En algoritme til kvadratisk programmering. Naval Research Logistics Quarterly , 3, 95-110.