Методы оптимизации: дополнительные главы
Автор: профессор, д. т.н.
Лекция 1. Введение. Классификация задач оптимизации. Условия экстремума. Градиенты и вторые производные, градиентный метод.
Семинар 1. Задача о "центральной" точке на прямой. Метод главных компонент (PCA) в простейшем варианте.
Лекция 2. Модификации градиентного метода. Метод сопряженных градиентов.
Семинар 2. Производные функций от матриц, пример нестандартного поведения градиентного метода.
Лекция 3. Метод Ньютона. Самосогласованные функции.
Семинар 3. Пример нестандартного поведения метода Ньютона. Примеры самосогласованных функций.
Лекция 4. Сведения из выпуклого анализа. Минимизация негладких функций.
Семинар 4. Субградиенты. Явный вид проекций на некоторые области.
Лекция 5. Негладкая безусловная минимизация. Субградиентный метод.
Семинар 5. Вычисление субградиентов, частные случаи субградиентного метода.
Лекция 6. Минимизация негладких выпуклых функций. Метод эллипсоидов, метод центра тяжести, метод Келли.
Семинар 6. Разбор домашнего задания, Prox-метод и регуляризация метода Ньютона.
Лекция 7. Задачи на условный экстремум. Правило множителей Лагранжа для задач с ограничениями типа равенств и неравенств. Теорема Куна-Таккера.
Семинар 7. Решение простой задачи на безусловный экстремум. Примеры задач, решаемых с помощью множителей Лагранжа.
Лекция 8. Двойственные задачи.
Лекция 9. Применение двойственности.
Лекция 10. Метод внутренней точки (отслеживание центра).
Лекция 11. Задачи регрессии.
Семинар 11. Квазиньютоновские методы.
Лекция 12. Применение к классификации.
Семинар 12. Disciplined convex programming. Субградиент длины проекции на множество полуопределенных матриц.
Лекция 13. Compressed sensing.
Семинар 13. Проекции на конусы.
Литература
1. Линейная алгебра
1.1. Введение в теорию матриц. М.: Наука, 1976.
1.2. Гантмахер A. H., Теория матриц. М.: Наука, 1966. 
1.3. Матричный анализ.
2. Нелинейный анализ
2.1. , , Элементы теории функций и функционального анализа. М.: Наука, 1976.
2.2. , Акилов анализ. М.: Наука, 1974.
2.3. Ортега Дж., терационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975.
2.4. Трауб Дж., Итерационные методы решения уравнений. М.: Мир, 1984.
3. Выпуклый анализ
3.1. Рокафеллар Р, Выпуклый анализ. М.: Мир, 1973.
3.2. , Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.
3.3. , Лекции по математической теории экстремальных задач. МГУ, 1970.
4. Оптимизация
4.1. , Введение в оптимизацию. М.: Наука, 1983.
4.2. S. Boyd, L. Vanderberghe, Convex optimization, Cambridge, Cambridge Univ. Press, 2004.
4.3 , , Оптимизация: теория, примеры, задачи. М.: УРСС, 2000.
4.4. , , Численные методы оптимизации. М.: Физматлит, 2005.
4.5 Нестеров в выпуклую оптимизацию. М.: МЦНМО, 2010.
5. Линейные матричные неравенства
5.1. S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan. Linear matrix inequalities is system and control theory. SIAM: Philadelphia.
6. PageRank
6.1 A. Lanville, C. Meyer Google's PageRank and Beyond: The Science of Search Engine Rankings. 2006, by Princeton University Press.
6.2. S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein Foundations and Trends in Machine Learning Vol. 3, No. 1 (2010) 1–122.
