Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)
Uogólnione metody rzutowe Karmarkara dla zadań wypukłej optymalizacji nieróżniczkowalnej (PD-1994-02)
naukowcy
uczniowie
Przedmiotem rozprawy są pewne metody rozwiązywania zadań wypukłej optymalizacji nieróżniczkowalnej z ograniczeniami kostkowymi. Metody takie można rozszerzyć na zadania z ogólnymi ograniczeniami liniowymi i wypukłymi ograniczeniami nieliniowymi. Celem pracy było wprowadzenie kilku algorytmów do rozwiązywania pewnej klasy zadań optymalizacji nieróżniczkowalnej, udowodnienie ich zbieżności, omówienie ich komputerowej implementacji i prezentacja wyników obliczeń testowych. Nie ograniczając się jedynie do teoretycznej analizy zbieżności, w pracy wprowadzono pewne modyfikacje metody z [GHV92], których celem było zwiększenie jej praktycznej skuteczności. W szczególności, ulepszono sposoby eliminacji nieaktywnych nierówności, wprowadzone w pracy [BGVM91] dla zadań programowania geometrycznego, które powinny zmniejszać zajętość pamięci i nakład obliczeń pomocniczych. Ogólnie biorąc, wyniki obliczeń sugerują, że algorytmy z „nieważonymi” środkami analitycznymi, dla których w pracy podano dowody zbieżności, są w praktyce co najmniej tak samo efektywne jak metody ze środkami ważonymi, które dowodów takich nie posiadają. Pracochłonność pojedynczej iteracji metod badanych w niniejszej pracy jest zdominowana przez koszt wyznaczania przybliżonego ważonego środka analitycznego wielościanu lokalizacji. Aby zmniejszyć ten koszt, w pracy niniejszej zaproponowano pewną modyfikację algorytmu z [GoV93], oraz wprowadzono szereg technik ułatwiających „gorący” start algorytmu po dodaniu lub usunięciu nierówności subgradientowych.
studenci
Instytut Badań Systemowych PAN w Warszawie
nondifferentiable convex optimization
nierozróżniczkowalna optymalizacja wypukła
optymalizacja subgradientowa
subgradient optimization