αΒΒ

"Alpha BB" omdirigerar hit. För annan användning, se ABB (disambiguation) .

αΒΒ är en andra ordningens deterministisk global optimeringsalgoritm för att hitta optima för allmänna, två gånger kontinuerligt differentierbara funktioner. Algoritmen bygger på att skapa en relaxation för icke-linjära funktioner av allmän form genom att överlagra dem med en kvadratisk av tillräcklig magnitud, kallad α, så att den resulterande superpositionen är tillräcklig för att övervinna det värsta scenariot med icke-konvexitet hos den ursprungliga funktionen. Eftersom en kvadratisk har en diagonal hessisk matris , lägger denna överlagring i huvudsak ett nummer till alla diagonala element i den ursprungliga hessiska, så att den resulterande hessiska är positiv-semidefinite . Således är den resulterande avslappningen en konvex funktion .

Teori

Låt en funktion ${f({\boldsymbol {x}})\in C^{2}}$ vara en funktion av allmän icke-linjär icke-konvex struktur, definierad i en finit ruta $X=\{{\boldsymbol {x}}\in \mathbb {R} ^{n}:{\boldsymbol {x}} ^{L}\leq {\boldsymbol {x}}\leq {\boldsymbol {x}}^{U}\}$ . Sedan kan en konvex underskattning (avslappning) $L({\boldsymbol {x}})$ av denna funktion konstrueras över $X$ genom att överlagra en summa av univariata kvadrater, var och en av tillräcklig magnitud för att övervinna icke-konvexiteten hos ${f({\boldsymbol {x}})}$ överallt i $X$ , enligt följande:

$L({\boldsymbol {x}})=f ({\boldsymbol {x}})+\summa _{i=1}^{i=n}\alpha _{i}(x_{i}^{L}-x_{i})(x_{i} ^{U}-x_{i})$

$L({\boldsymbol {x}})$ kallas $\alpha {\text{BB}}$ underskattare för allmänna funktionella former. Om alla $\alpha _{i}$ är tillräckligt stora är den nya funktionen $L({\boldsymbol {x}})$ konvex överallt i $X$ . Lokal minimering av $L({\boldsymbol {x}})$ ger alltså en strikt nedre gräns för värdet av ${f({\boldsymbol {x}}) }$ i den domänen.

Beräkning av ${\boldsymbol {\alpha }}$

Det finns många metoder för att beräkna värdena för vektorn ${\displaystyle {\boldsymbol {\alpha }}}.$ Det är bevisat att när $\alpha _{i}=\max\{0,-{\frac {1}{2}}\lambda _{i }^{\min }\}$ , där $\lambda _{i}^{\min }$ är en giltig nedre gräns på i { $displaystyle i}$ -e egenvärdet för den hessiska matrisen för ${f({\boldsymbol {x}})}$ , ${\displaystyle L({\boldsymbol {x}})}-$ underskattaren är garanterat konvex.

En av de mest populära metoderna för att få dessa giltiga gränser för egenvärden är att använda den skalade Gerschgorin-satsen. Låt $H(X)$ vara intervallet Hessian matris för ${f(X)}$ över intervallet $X$ . Sedan $\forall d_{i}>0$ en giltig nedre gräns för egenvärdet $\lambda _{i}$ härledas från den $i$ -th raden av $H(X)$ enligt följande:

$\lambda _{i}^{\min }={ \underline {h_{ii}}}-\sum _{i\neq j}(\max(|{\underline {h_{ij}}}|,|{\overline {h_{ij}}}|{\ frac {d_{j}}{d_{i}}})$