Novosibirsk, Russia, May, 30 – June, 4, 2011

International Conference
"Modern Problems of Applied Mathematics and Mechanics: Theory, Experiment and Applications", devoted to the 90th anniversary of professor Nikolai N. Yanenko

Стецюк П.И.  

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

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

Abstracts file: Stetsyuk-Abstract.doc
Full text file: Stetsyuk.pdf


To reports list
© 1996-2017, Institute of computational technologies of SB RAS, Novosibirsk