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



Скачать 275.41 Kb.
страница1/5
Дата06.07.2013
Размер275.41 Kb.
ТипДокументы
  1   2   3   4   5
УДК 519.8
Н.З.ШОР, Н.Г.ЖУРБЕНКО, А.П.ЛИХОВИД, П.И.СТЕЦЮК
РАЗВИТИЕ АЛГОРИТМОВ НЕДИФФЕРЕНЦИРУЕМОЙ ОПТИМИЗАЦИИ И ИХ ПРИЛОЖЕНИЯ
Работа содержит краткий обзор разработанных в Институте кибернетики методов недифференцируемой оптимизации: обобщенный градиентный спуск; метод с растяжением пространства в направлении субградиента; r-алгоритм. Приведены основные области приложений методов недифференцируемой оптимизации.

Bведение

Обобщенный градиентный спуск

Субградиентные методы с растяжением пространства в направлении субградиента

Приложения алгоритмов недифференцируемой оптимизации

Приложения алгоритмов недифференцируемой оптимизации

Заключение
  1. Bведение



К задачам минимизации выпуклых функций с разрывным градиентом сводится большое число проблем, возникающих при решении сложных задач математического программирования. Владение методами недифференцируемой оптимизации дает возможность гибко использовать различные схемы декомпозиции (по переменным, ограничениям, ресурсам и т. п.), учитывающие специфику задач большой размерности, позволяет эффективно получать двойственные оценки в задачах дискретного и непрерывно- дискретного программирования и для некоторых классов многоэкстремальных задач. Появляется возможность использовать негладкие функции штрафа, позволяющие при конечных значениях штрафных параметров получать задачу безусловной минимизации, полностью эквивалентную первоначальной задаче выпуклого программирования. Кроме того, задачи оптимизации с негладкими функциями возникают непосредственно в результате кусочно-гладкой аппроксимации технико-экономических характеристик оптимизируемых объектов.

Отсутствие эффективных методов негладкой оптимизации затрудняло решение указанных классов задач и заставляло либо изменять постановку задачи в ущерб адекватности модели, либо использовать различные приемы сглаживания. Последнее не всегда приводит к успеху, так как применение сглаживающих функций вызывает плохую обусловленность минимизируемой функции, что ухудшает вычислительную устойчивость таких эффективных методов гладкой минимизации, как квазиньютоновские и методы сопряженных градиентов. Таким образом, область приложений методов негладкой оптимизации весьма широка. Методы негладкой оптимизации оказались вполне конкурентоспособными как по надежности, так и по времени счета и точности результатов с наиболее эффективными методами решения гладких плохо обусловленных задач.

Цель нашего обзора – дать краткое описание разработанных в Институте кибернетики методов недифференцируемой оптимизации и показать их многочисленные приложения. В обзор включены следующие методы субградиентного типа: обобщенный градиентный спуск; методы субградиентного типа с растяжением пространства в направлении субградиента; r-алгоритмы, являющиеся мощным практическим средством решения задач недифференцируемой оптимизации.


Виктор Михайлович Глушков придавал большое значение исследованиям методов негладкой оптимизации. На самом высоком правительственном уровне он способствовал внедрению этих результатов в различных областях народного хозяйства. (В частности, он уделял большое внимание созданию системы автоматизированного планирования производства и распределения заказов в черной металлургии.)


  1. Обобщенный градиентный спуск



Пусть – выпуклая функция, определенная на евклидовом пространстве , – множество минимумов (оно может быть и пустым), – точка минимума; ; – субградиент функции в точке .

Субградиент функции в точке есть вектор такой, что
для всех .
Из определения субградиента следует, что если , то
(1)
Геометрически формула (1) означает, что антисубградиент в точке образует острый угол с произвольным направлением, проведенным из в сторону точки с меньшим значением . Отсюда, если непусто, , то при движении из в направлении с достаточно малым шагом расстояние до убывает. Этот простой факт лежит в основе субградиентного метода или метода обобщенного градиентного спуска (ОГС), впервые предложенного в [1] в связи с решением сетевой транспортной задачи.

Методом обобщенного градиентного спуска (ОГС) называется процедура построения минимизирующей последовательности , где – начальное приближение, а строятся по следующей рекуррентной формуле:
(2)
здесь – произвольный субградиент функции в точке , – шаговый множитель. Если , то – есть точкой минимума функции и процесс останавливается.

В Институте кибернетики, начиная с 1962 года, были разработаны несколько вариантов ОГС, использующих соотношение (2). Эти результаты получены в период с 1962 по 1968 год и наиболее полно отражены в монографии [2], материал которой составила докторская диссертация Н.З.Шора 1970 года.

Наиболее общий результат о сходимости ОГС содержится в следующей теореме (см., например, [2]).
Теорема 1 Пусть – выпуклая функция, определенная на , с ограниченной областью минимумов , – последовательность чисел, обладающая свойствами:

Тогда последовательность , образованная по формуле (2) при произвольном обладает одним из следующих свойств: либо найдется такое , что , либо , .
При определенных дополнительных предположениях удалось получить варианты ОГС, сходящиеся со скоростью геометрической прогрессии.
Теорема 2 Пусть – выпуклая функция, определенная на , и для всех при некотором выполняется неравенство
(3)
где – точка, принадлежащая множеству минимумов функции и лежащая на кратчайшем расстоянии от . Тогда, если при заданном выбрать величину , удовлетворяющую неравенству

определить в соответствии с рекуррентной формулой

где

и вычислить по формуле (2), то либо при некотором и принадлежит области минимумов, либо при всех выполняется неравенство

Таким образом, если угол заранее известен, то, регулируя шаг по формулам теоремы 2 можно получить сходимость к минимуму со скоростью геометрической прогрессии со знаменателем .

В формуле (3) характеризует степень вытянутости поверхностей уровня функции . Если в некоторой окрестности минимума функции не существует такого, что для любого из этой окрестности выполняется (3), то такую функцию будем называть существенно овражной. При минимизации существенно овражных функций приведенный в теореме 2 способ регулировки шаговых множителей неприменим. В этом случае следует использовать универсальный способ выбора шаговых множителей, указанный в теореме 1.

Сформулируем теорему, аналогичную теореме 2, непосредственно в терминах, характеризующих степень "вытянутости" поверхностей уровня.
Теорема 3 Пусть выпуклая функция определена на , – единственная точка минимума и заданы начальное приближение и числа и , причем , . Рассмотрим множество . Если для любой пары точек , такой, что , выполняется условие

то последовательность , образованная с помощью рекуррентных формул (2), где , сходится к со скоростью геометрической прогрессии:

за исключением случая, когда для некоторого , т. е. .
Рассмотрим еще один вариант метода обобщенного градиентного спуска, когда шаговый множитель остается в течение определенного числа шагов постоянным, а затем уменьшается в два раза [2].
Теорема 4 Пусть для выпуклой функции выполняются условия теоремы 1, . Рассмотрим при заданном итеративный процесс (2), где . Здесь – целая часть числа . При достаточно большом и выполняется неравенство

Регулировка шага, согласно теореме 4, была использована в методе ОГС, который был предложен в 1962 году в связи с решением транспортной задачи в сетевой форме [1]. Работа [1] была первым примером использования субградиентного процесса для минимизации выпуклых недифференцируемых функций.

Методы ОГС дали возможность решить большое число задач производственно-транспортного планирования с применением схем декомпозиции для задач большой размерности. Подробную информацию об этих задачах можно найти в [3]. Метод ОГС также послужил основой для создания стохастического аналога обобщенного градиентного спуска [4], который имеет большое практическое применение, в частности, при решении многоэтапных задач стохастического программирования. В [3] описано применение метода обобщенного стохастического градиента к решению двухэтапной стохастической транспортной задачи, связанной с определением объемов складов однородной продукции при случайном спросе.

Результаты по методам ОГС, полученные в Институте кибернетики, получили развитие в работах И.И.Еремина [5] и Б.Т.Поляка [6] для решения задач выпуклого программирования с ограничениями.

До 1974 года работы по ОГС были малоизвестны за рубежом, так как были опубликованы на русском языке в малодоступных изданиях. Они получили известность после публикации в [7] подробного обзора результатов и библиографии работ по недифференцируемой оптимизации, выполненных в СССР.
  1   2   3   4   5

Похожие:

П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconРазвитие и современное состояние контроллинга в Германии
Данная статья содержит краткий обзор понимания контроллинга в Германии так называемые концепции контрол
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconРабота №1 «методы одномерной оптимизации» Дисциплина «Методы оптимизации»
...
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconПоследние достижения эволюционной и исторической мысли. Вести с передовых рубежей. Краткий обзор. Вып.№1
А краткий обзор передач – лекций, прочитанных на тк «Культура» в рамках передачи «Академия»
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconВопросы для экзамена по патрологии для 4 курса сзо (2010-2011)
Золотой век святоотеческой письменности. Арианство в IV веке: краткий историко-концептуальный обзор. Свв отцы-Каппадокийцы. Краткий...
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconПравила Парусных Гонок 2005-2008 Содержание Приложения
Первый раздел, Части 1-7, содержит правила, затрагивающие всех спортсменов. Второй раздел содержит Приложения а-р, которые излагают:...
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconКраткий обзор электронных библиотек Рунета 1 Формальный взгляд 1 Субьективный взгляд 3 Неформальные выводы 5 Приложения 6
Первая десятка результатов поиска слова “Библиотека” в четырех наиболее популярных поисковых машинах Рунета представленны в Приложениях...
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconКраткий обзор влияния наркотиков на развитие плода
Какова вероятность рождения здорового ребенка женщиной, употребляв-шей наркотики до и во время беременности?
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconМетодические указания и задания к выполнению лабораторных работ по дисциплине «Методы оптимизации»
Тимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Много внимания уделено...
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconС. Ф. Чекмарев 1 курс магистратуры, 10 семестр, 32 часа, экзамен I. Введение Кластеры, наночастицы и наноматериалы примеры и области применения. Краткий обзор
Кластеры, наночастицы и наноматериалы – примеры и области применения. Краткий обзор методов исследования (теория, моделирование и...
П. И. Стецюк развитие алгоритмов недифференцируемой оптимизации и их приложения работа содержит краткий обзор iconИсследование адаптивных методов оптимизации sql-запросов
Рассмотрено использование адаптивных алгоритмов оптимизации для запросов на языке sql c целью уточнения оценок селективности, и,...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org