Subgradientmetoder är iterativa metoder för att lösa konvexa minimeringsproblem . Subgradientmetoder utvecklade av Naum Zuselevich Shor konvergerar även när de tillämpas på icke -differentiera objektiva funktioner . När funktionen är differentierbar använder subgradientmetoder för obegränsade problem samma sökriktning som den brantaste nedstigningsmetoden .
Subgradientmetoder är långsammare än Newtons metoder , där dubbelt kontinuerligt differentierbara konvexa funktioner används för minimering. Newtons metoder upphör dock att konvergera till problem som har icke-differentierbara kinks.
Under de senaste åren har vissa inre punktmetoder föreslagits för konvexa minimeringsproblem, men både subgradientprojektionsmetoder och relaterade strålnedstigningsmetoder förblir konkurrenskraftiga. För konvexa minimeringsproblem med ett stort antal dimensioner är subgradientprojektionsmetoder acceptabla eftersom de kräver en liten mängd minne.
Subgradientprojektionsmetoder tillämpas ofta på problem med stor storlek med hjälp av nedbrytningstekniker. Sådana nedbrytningsmetoder tillåter ofta en enkel distribuerad uppgiftsmetod.
Låta vara en konvex funktion med domän . Den klassiska subgradientmetoden upprepas
där är någon subdifferential för funktionen vid punkten , och är den k: te iterationen av variabeln . Om den är differentierbar är dess enda undergradient gradienten på . Det kan hända att det inte är en minskande riktning för vid punkten . Därför innehåller vi en lista , som lagrar de hittade minsta värdena för objektivfunktionen, det vill säga
Undergradientmetoder använder ett stort antal olika regler för val av stegstorlek. Här noterar vi fem klassiska regler för vilka konvergensbevis är kända:
För alla fem reglerna bestäms stegstorleken "i förväg", innan metoden startar. Stegstorleken är oberoende av tidigare iterationer. Stegvalsegenskapen "i förväg" för subgradientmetoder skiljer sig från de "pågående" stegvalsreglerna som används i metoder för differentierbara funktioner - många metoder för att minimera differentierbara funktioner uppfyller Wolf-villkoren för konvergens, där stegstorlekarna beror på den aktuella punktens position och den aktuella sökriktningen. En omfattande diskussion av stegvalsreglerna för subgradientmetoder, inklusive inkrementerande versioner, ges i boken av Bertsekas [1] och även i boken av Bertsekas, Nedić och Ozdağlar [2] .
För en konstant steglängd och skalbara subgradienter med en euklidisk norm lika med ett, närmar sig subgradientmetoden godtyckligt minimivärdet, dvs.
enligt Shore [3] .Klassiska subgradientmetoder har dålig konvergens och rekommenderas inte längre för användning [4] [5] . Men de används fortfarande i specialiserade applikationer eftersom de är enkla och lätta att anpassa till speciella strukturer för att dra nytta av deras egenskaper.
Under 1970-talet föreslog Claude Lemérachel och Phil Wolf "kärvemetoder" för nedstigning för konvexa minimeringsproblem [6] . Innebörden av begreppet "strålemetoder" har förändrats mycket sedan dess. Moderna versioner och en fullständig konvergensanalys gavs av Kiel [7] . Moderna strålmetoder använder ofta " nivåkontroll "-regler för val av stegstorlek, som utvecklar tekniker från metoden "subgradientprojektion" av Boris T. Polyak (1969). Det finns dock problem på grund av vilka strålmetoder ofta ger liten fördel jämfört med subgradientprojektionsmetoder [4] [5] .
En förlängning av subgradientmetoder är subgradientprojektionsmetoden , som löser det begränsade optimeringsproblemet
minimera under villkoretvar är en konvex uppsättning . Subgradientprojektionsmetod använder iterationer
var är projektionen på och är någon undergradient vid .
Subgradientmetoden kan utökas för att lösa problemet med begränsningar i form av ojämlikheter
minimera under villkoretdär funktionerna är konvexa. Algoritmen har samma form av fallet utan begränsningar
var är stegstorleken och är undergradienten för målfunktionen eller en av begränsningsfunktionerna vid punkten . Här
där betyder funktionens subdifferential . Om den aktuella punkten är giltig använder algoritmen subgradienten för objektivfunktionen. Om punkten är ogiltig väljer algoritmen en undergradient av alla begränsningar som överträds.
_ | Optimeringsmetoder|
---|---|
En-dimensionell |
|
Noll ordning | |
Första beställning | |
andra beställning | |
Stokastisk | |
Linjära programmeringsmetoder _ | |
Icke -linjära programmeringsmetoder |