Новосибирск, Россия, 30 мая – 4 июня 2011 г.

Международная конференция
«Современные проблемы прикладной математики и механики: теория, эксперимент и практика», посвященная 90-летию со дня рождения академика Н.Н. Яненко
№ гос. регистрации 0321101160, ISBN 978-5-905569-01-2

Стецюк П.И.  

Субградиентные методы с преобразованием пространства для минимизации овражных выпуклых функций

     В докладе обсуждаются два семейства субградиентных методов оптимизации с преобразованием пространства, имеющих ускоренную сходимость при минимизации выпуклых (не обязательно гладких) функций с овражной структурой поверхностей уровня. Целевые функции такого типа часто встречаются в различных задачах интервального анализа, как следствие кусочной гладкости интервальных арифметических операций.
     Первое семейство методов оптимизации известно как r-алгоритмы Н.З.Шора. Они базируются на процедуре наискорейшего спуска в преобразованном пространстве переменных и обеспечивают монотонность (или почти монотонность) по значениям минимизируемой функции. r-Алгоритмы используют операцию растяжения пространства в направлении разности двух последовательных субградиентов, которая улучшает свойства овражной функции в преобразованном пространстве переменных. Второе семейство методов оптимизации базируется на релаксацинном шаге (известен как шаг Поляка или шаг Агмона-Моцкина) и использует априорное знание минимального значения функции. Здесь применяется антиовражная техника, подобно тому, как это сделано в r-алгоритмах Шора. Но преобразование пространства реализуется с помощью линейного оператора, который позволяет обеспечить уменьшение расстояния до точки минимума в очередном преобразованном пространстве переменных.
     В докладе даются вычислительные схемы метода ralgb5 (вариант r-алгоритмов с адаптивной регулировкой шага и постоянным коэффициентом растяжения пространства) и метода amsg2p (вариант второго семейства методов, где преобразование пространства реализуется на основе двух последовательных субградиентов и агрегатного вектора, являющегося выпуклой комбинацией вычисленных ранее субградиентов). Обсуждаются результаты тестовых экспериментов для обоих методов при минимизации существенно овражных кусочно-квадратичных функций, овражных квадратичных и кусочно-линейных функций. Одна из тестовых кусочно-линейных функций связана с разрешимостью интервальной линейной задачи о допусках.

Файл тезисов: Stetsyuk-Abstract.doc
Файл с полным текстом: Stetsyuk.pdf


К списку докладов
© 1996-2019, Институт вычислительных технологий СО РАН, Новосибирск