Trust region

I matematisk optimering är en förtroenderegion delmängden av regionen av målfunktionen som approximeras med hjälp av en modellfunktion (ofta en kvadratisk ). Om en adekvat modell av den objektiva funktionen hittas inom förtroenderegionen, så utökas regionen; omvänt, om approximationen är dålig, är regionen kontrakterad.

Passformen utvärderas genom att jämföra förhållandet mellan förväntad förbättring från modellapproximationen med den faktiska förbättring som observerats i objektivfunktionen. Enkel tröskelvärde för förhållandet används som kriterium för expansion och kontraktion – en modellfunktion är "betrodd" endast i den region där den ger en rimlig approximation.

Trust-region-metoder är i någon mening dubbla till linjesökningsmetoder : trust-region-metoder väljer först en stegstorlek (storleken på trustregionen) och sedan en stegriktning, medan linjesökningsmetoder först väljer en stegriktning och sedan en stegstorlek.

Den allmänna idén bakom metoder för förtroenderegioner är känd under många namn; den tidigaste användningen av termen verkar vara av Sorensen (1982). En populär lärobok av Fletcher (1980) kallar dessa algoritmer för begränsade stegmetoder . Dessutom hänvisar Goldfeld , Quandt och Trotter (1966 ) i ett tidigt grundarbete om metoden till den som kvadratisk bergsklättring .

Exempel

Begreppsmässigt, i Levenberg–Marquardt-algoritmen , approximeras objektivfunktionen iterativt av en kvadratisk yta , och sedan med hjälp av en linjär lösare uppdateras uppskattningen. Detta ensamt kanske inte konvergerar bra om den initiala gissningen är för långt från det optimala. Av denna anledning begränsar algoritmen istället varje steg, vilket förhindrar att det går "för långt". Den operationaliserar "för långt" enligt följande. Istället för att lösa $A\,\Delta x=b$ för $\Delta x$ ${\displaystyle {\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b} , där diag$ den ⁡ $displaystyle \operatorname {diag} (A)}$ är diagonal matris med samma diagonal som A och λ är en parameter som styr storleken på förtroenderegionen. Geometriskt lägger detta till en paraboloid centrerad vid $\Delta x=0$ till den kvadratiska formen , vilket resulterar i ett mindre steg.

Tricket är att ändra storleken på förtroenderegionen (λ). Vid varje iteration förutsäger den dämpade kvadratiska passningen en viss minskning av kostnadsfunktionen, ${\displaystyle \Delta f_{\text{pred}}} ,$ som vi skulle förvänta oss vara en mindre minskning än den verkliga minskningen. Givet $\Delta x$ , kan vi utvärdera

\Delta f_{\text{faktisk}}=f(x)-f(x+\Delta x).

Genom att titta på förhållandet ${\displaystyle \Delta f_{\text{pred}}/\Delta f_{\text{faktisk}}} , kan$ vi justera storleken på tillitsregionen. I allmänhet förväntar vi oss att $\Delta f_{\text{pred}}$ är lite mindre än ${\displaystyle \Delta f_{\text{actual}}} ,$ och så förhållandet skulle vara mellan, säg, 0,25 och 0,5. Om förhållandet är mer än 0,5 dämpar vi steget för mycket, så expandera förtroendeområdet (minska λ) och iterera. Om förhållandet är mindre än 0,25, så avviker den sanna funktionen "för mycket" från approximationen av förtroenderegionen, så krymp förtroenderegionen (öka λ) och försök igen.

Dennis, JE, Jr.; Schnabel, Robert B. (1983). "Globalt konvergenta ändringar av Newtons metod". Numeriska metoder för obegränsad optimering och icke-linjära ekvationer . Englewood Cliffs: Prentice-Hall. s. 111–154. ISBN 0-13-627216-9 .
Andrew R. Conn, Nicholas IM Gould, Philippe L. Toint " Trust-Region Methods (MPS-SIAM Series on Optimization)" .
Byrd, R.H., RB Schnabel och GA Schultz. " En förtroenderegionsalgoritm för icke-linjärt begränsad optimering", SIAM J. Numer. Anal., 24 (1987), sid. 1152-1170.
Yuan, Y. " A review of trust region algorithms for optimization " i ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh, 2000 Oxford University Press, USA.
Yuan, Y. " Recent Advances in Trust Region Algorithms ", Math. Program., 2015

externa länkar