В. Н. Кузьменко, Э. И. Ненахов, В. М. Панин - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
В. Н. Кузьменко, Э. И. Ненахов, В. М. Панин - страница №1/1


В.Н.Кузьменко, Э.И.Ненахов, В.М.Панин




РАЗВИТИЕ МЕТОДОВ ГЛАДКОЙ ОПТИМИЗАЦИИ В ИНСТИТУТЕ КИБЕРНЕТИКИ

Ключевые слова: методы оптимизации, численные методы, экстремальные задачи, гладкая оптимизация, метод линеаризации


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

Длительное время в области гладкой оптимизации плодотворно работал академик Б.Н. Пшеничный вместе со своими учениками Ю.М. Данилиным и В.М.Паниным. Основные результаты совместных исследований Б.Н. Пшеничного и Ю.М. Данилина были суммированы в 1975 году в их монографии "Численные методы в экстремальных задачах" [1], переведенной на многие языки мира и являющейся одной из лучших книг в области численных методов оптимизации.

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

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

В работах Б.Н. Пшеничного и Ю.М. Данилина разработаны алгоритмы, удовлетворяющие отмеченным выше требованиям, для минимизации гладких сильно выпуклых функций. Схема их построения такова. Для решения задачи , строится последовательность

(1)

Матрица определяется системой уравнений



,

где – произвольная система линейно независимых векторов, причем при ; . Оказывается, что если ограниченная последовательность и , то для матрицы выполняется условие , . При этом на каждой итерации для построения матрицы требуется вычислять производные функции в двух точках: и . Фактически это означает, что при любом необходимо вычислять один или два градиента (в зависимости от выбора вектора ).



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

(2)

( при любом ).

В одной из работ Б.Н. Пшеничного получена более конкретная по сравнению с (2) оценка, уточняющая характер сверхлинейной сходимости

. (3)

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



. (4)

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

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

Параллельно с методами безусловной оптимизации разрабатывались численные методы решения гладких задач условной оптимизации





(5)

(ограничения-равенства представлены в форме эквивалентной пары соответствующих неравенств). К концу 60-х годов сформировалась основная группа методов условной оптимизации – возможных направлений, условного градиента, проекции градиента, демпфированный метод Ньютона, методы штрафов, методы множителей и модифицированных функций Лагранжа. В случае линейных ограничений они, как правило, сохраняли высокие свойства алгоритмов безусловной оптимизации градиентного и ньютоновского типов – нелокальную сходимость, эффективность реализации, соответствующие локальные оценки скорости сходимости ([2, 3] и другие). Однако, если ограничения в (5) нелинейны, то эти методы теряют указанные качества, поскольку без линейной аппроксимации ограничений ни одна их итерация не может быть точно реализована за конечное и равномерно ограниченное число вычислений. Несоответствие между методами безусловной и условной оптимизации при нелинейных ограничениях было устранено в работах киевской школы оптимизации в Институте кибернетики, возглавляемом В.М.Глушковым.

Общая схема аппроксимирующих методов условной оптимизации была представлена в форме





(6)

где , а решение вспомогательной аппроксимирующей задачи с линейными ограничениями:



(7)


Здесь нормирующее ограничение, параметр, матрица симметрична и для любых



и константы. Предполагается, что если множители Лагранжа задачи (7), относящиеся к линеаризованным ограничениям, .

Тейлоровская аппроксимация (7) задачи (5) охватывает разные типы методов: Гриффита и Стюарта (), линеаризации Б.Н.Пшеничного ( – единичная ()–матрица), Ньютона (– лагранжиан задачи (1)), квазиньютоновские и другие.

Для определения шагового множителя во всех методах предложено использовать релаксацию вдоль вектора спуска недифференцируемой штрафной функции



(8)

где . Коэффициент штрафа является постоянным и мажорирует множители Лагранжа задачи (7) по процессу:

.

(9)


Первым алгоритмом этой схемы стал метод линеаризации Б.Н.Пшеничного () [4], в котором вычисляется как наибольшее из значений , при котором выполняется неравенство

.

(10)

Отметим, что в отличие от метода проекции градиента вычисление в методе линеаризации осуществляется после операции проектирования, а определение конструктивно и нетрудоемко. В [1, 4] было установлено, что любая точка сгущения последовательности , генерируемой методом линеаризации (6), (7), (10), является стационарной точкой для исходной задачи (5):

.

(11)


Через обозначаются соответствующие множества , . Дальнейшие исследования были направлены на то, чтобы, с одной стороны, показать полную аналогию свойств метода линеаризации классическому методу градиентного спуска безусловной оптимизации (предложенному еще Коши), а с другой стороны – распространить эту аналогию на всю схему методов аппроксимирующего программирования (6), (7).

Принципиально неулучшаемыми локальными оценками скорости сходимости в безусловной оптимизации являются, как известно [3], следующие:

– для методов первого порядка (градиентного типа): а) линейная , если минимизируемая функция сильно выпукла вблизи , б) оценка , если функция выпукла;

– для методов второго порядка (типа Ньютона) – квадратичная или сверхлинейная , если функция сильно выпукла в окрестности решения .

Многие из этих оценок ранее были получены для ряда перечисленных выше методов схемы (6), (7), когда ограничения линейны; в [5] установлен, в частности, соответствующий результат для демпфированного метода Ньютона.

В случае нелинейных ограничений вопрос об оценках скорости сходимости даже «базового» для всей схемы (6), (7) метода линеаризации Б.Н.Пшеничного не был решен; в [1, 6] было лишь установлено, что вблизи по форме он совпадает с методом простой итерации для нелинейной системы с невырожденным якобианом . Кроме того, обременительными условиями реализации метода линеаризации (как и большинства известных методов схемы (6), (7)) являются предположения о разрешимости вспомогательной задачи (7) в любой точке итерационного процесса, а также предположение (9) об ограниченности генерируемых .

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

Алгоритм (6) модифицирован следующим образом:





(12)

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

,

(13)

Ее множители Лагранжа в решении обозначаются .

В отличие от (7) вспомогательная задача (13) разрешима в любой точке , удовлетворяет условию Слейтера, ее условия оптимальности выполняются в регулярной форме. Если , то , т.е. вспомогательные задачи (7) и (13) по существу эквивалентны, а . Как будет видно из последующего, выбор в алгоритмах обоих схем совпадает, поэтому методы схемы (12), (13), получившие название методов конечных штрафов, можно рассматривать как распространение соответствующих алгоритмов аппроксимирующей схемы (6), (7) на все пространство . Более того, оказалось, что в окрестности решения можно гарантировать выполнение условия



,

(14)

если принять коэффициент штрафа достаточно большим, но ограниченным.

Таким образом, методы конечных штрафов (12) со вспомогательной задачей (13) эквивалентны соответствующим алгоритмам аппроксимирующего программирования (6), (7) в окрестности искомого решения, но их уже можно использовать с любого начального приближения и реализовать в любой точке . Вдали от они, вообще говоря, не эквивалентны методам аппроксимирующего программирования (6), (7).



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

Шаг 1. Заменить в задаче (13) индексное множество на и из ее решения найти , полагая для .

Шаг 2. Определить как наибольшее из значений , для которого

.

(15)

Шаг 3. Если одновременно и , то принять ; в противном случае сохранить . Найти . Конец итерации; .

Нелокальную сходимость методов конечных штрафов устанавливает



Теорема 1 [7]. Пусть функция не имеет стационарных точек в области произвольное начальное приближение. Если генерируемая последовательность ограничена, то , при этом число вычислений на каждой итерации процесса равномерно ограничено. Для вспомогательные задачи (13) и (7) эквивалентны, , значение постоянно и удовлетворяет условию

.

(16)

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

Результат теоремы 1 распространяется на невыпуклые задачи оптимизации, при этом характер поведения в произвольной точке функций не играет роли. Можно показать, что если функция имеет в области стационарные точки и последовательность ограничена, то либо при и тогда , либо и тогда .

Локальные оценки скорости сходимости методов конечных штрафов зависят от характера задачи (5) в окрестности решения.

Задача (5) называется локально выпуклой, если вблизи множества ее решений функции выпуклы. Задача (5) называется локально сильно выпуклой, если она локально выпукла и для любых



.

(17)

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

Теорема 2 [8, 9]. Пусть выполнены условия теоремы 1, сильно положительно определенная симметричная матрица с константой (методы последовательного квадратичного программирования). Тогда справедливы следующие оценки скорости сходимости:

1) если исходная задача (5) локально выпукла, то при фиксированной матрице последовательность сходится к одному из решений задачи (5): ;

2) если исходная задача (5) локально сильно выпукла, то с линейной скоростью сходимости.

3) если искомое решение лежит в вершине допустимого множества и для всех , то со сверхлинейной (квадратичной) скоростью сходимости.

Теоремы 1,2 позволяют утверждать, что по своим свойствам метод линеаризации в форме метода конечных штрафов является полным аналогом классического метода градиентного спуска в безусловной оптимизации. Следует учесть, однако, что “платой” за его нелокальную сходимость является увеличение на единицу размерности аргумента в (13) по сравнению с (7), что приводит к вырождению (по ) квадратичной формы в (13) даже при .

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



.

Здесь - функция Лагранжа задачи (1), - вектор с компонентами .



Теорема 3 [10]. Пусть выполняются условия теоремы 1, значения произвольны. Тогда для ЛМКШ - справедливы все утверждения теоремы 1 и утверждения теоремы 2 об оценках скорости сходимости.

На основании теорем 2,3 можно заключить об аналогии свойств методов линеаризации и ЛМКШ - . Численные эксперименты показали сравнительно одинаковую их эффективность. Подтвердилось давно существовавшее предположение об асимптотической эквивалентности методов последовательного линейного и квадратичного программирования первого порядка.

Что касается метода второго порядка – метода Ньютона (), то для большинства даже выпуклых задач оптимизации (5) неравенство (15) не выполняется при в точках , сколь угодно близких к (так называемый эффект Маратоса), и сверхлинейная скорость сходимости в демпфированном методе Ньютона не достигается. Причины этого явления указаны в [11]. Были созданы “гибридные” алгоритмы, обладающие нелокальной и сверхлинейной сходимостью. Таким является, в частности, ускоренный метод линеаризации [1], представляющий комбинацию метода линеаризации и “чистого” () метода Ньютона для системы необходимых условий экстремума задачи (5). В то же время не прекращались попытки (например, [12]) построения полного аналога демпфированному методу Ньютона в безусловной оптимизации. Окончательно эта проблема в случае нелинейных ограничений была решена для задач выпуклой оптимизации в работе В.М.Панина и В.В.Скопецкого [13]. Она основана на использовании для выбора релаксации новой штрафной функции , учитывающей более тонко, чем условие (9) у функции , роль множителей Лагранжа и “не страдающей” эффектом Маратоса:

,

где .Функция недифференцируема по и является точной штрафной функцией для задачи (5) при любом . Поэтому играет не столько роль коэффициента штрафа, сколько роль параметра релаксации функции в точке вдоль вектора ньютоновского направления , определяемого решением задачи (7) при . А именно существует “пороговое” такое, что для всех точек ограниченной области при имеет место





(18)

где - производная по направлению .

ая итерация демпфированного метода Ньютона . состоит в определении:

  1. вектора спуска вспомогательной задачи (7),

  2. значения путем удвоения единицы () до момента выполнения неравенства (18),

  3. значения путем дробления единицы () до момента выполнения неравенства

.

Теорема 4. Если функции выпуклы и условие (17) выполняется в любой точке , то при произвольном начальном приближении предельная точка последовательности , генерируемой описанным демпфированным методом Ньютона, является точкой Куна-Такера исходной задачи (5), . При имеет место с квадратичной скоростью.

Теорема 4 является частным случаем соответствующего результата, установленного в [13] для конечномерных вариационных неравенств. Последние являются обобщением задач оптимизации, нелинейной дополнительности, отыскания седловых точек и широко используются в настоящее время для описания моделей экономического равновесия. В [14] для решения вариационных неравенств предложен эффективный метод проекционного типа первого порядка с линеаризацией ограничений. В случае сильно монотонного оператора метод [14] играет для вариационных неравенств с нелинейными ограничениями такую же роль, какую метод линеаризации играет в условной оптимизации. В частности, он эффективнее всех известных методов проекционного типа, не использующих линейной аппроксимации ограничений. Асимптотические свойства метода и его модификаций установлены в [15], ускоренные алгоритмы ньютоновского типа (так называемые методы оптимизационного подхода) для вариационных неравенств, разработанные учеными кибернетического центра, описаны в обзоре [16].

В последние годы особое внимание уделялось распространению идей метода линеаризации на задачи, которые не вкладываются в первоначальную схему этого метода. Одной из таких задач является общая задача обратно-выпуклого программирования:

,

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


Литература





  1. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. – М.: Наука, 1975. –320с.

  2. Васильев Ф.П. Численные методы решения экстремальных задач. – М.: Наука, 1983. –518с.

  3. Поляк Б.Т. Введение в оптимизацию.– М.: Наука, 1983. –384с.

  4. Пшеничный Б.Н. Алгоритм для общей задачи математического программирования // Кибернетика. –1970. – №5. – С. 120-125.

  5. Данилин Ю.М. Методы минимизации, основанные на аппроксимации исходного функционала выпуклым // Журн. вычисл. математики и матем. физики. –1970. – 10, №5. – С. 1067-1080.

  6. Пшеничный Б.Н. Метод линеаризации. – М.: Наука, 1983. –136с.

  7. Панин В. М. Методы конечных штрафов с линейной аппроксимацией ограничений. I // Кибернетика. –1984. – №2. – С. 44-50; II // Там же. – №4. – С. 73-81.

  8. Панин В. М. Оценки сходимости двух методов линеаризации. // Докл. АН УССР, Сер. А, –1984. – №5. – С. 77-79.

  9. Панин В.М., Соболенко Л.А. Сходимость одного метода линеаризации. // Методы решения сложных задач математического программирования, Киев: Ин-т кибернетики им В.М. Глушкова, 1985, С.11-16.

  10. Панин В. М. Линейный метод конечных штрафов с регулируемым вектором спуска. // Кибернетика и системный анализ. –1988. – №5. – С. 50-55.

  11. Панин В. М., Пшеничный Б.Н., Лаврина Т.В. Методы аппроксимирующего программирования в условной оптимизации // Журнал обчислювальної та прикладної математики. – 2001, №1 (86). – С.61-70.

  12. Pang G.S. A B-differentiable equation – based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems // Math. Progr. – 1991. –51, №1. – P. 101-131.

  13. Панин В.М., Скопецкий В.В. Нелокальный метод Ньютона для задач выпуклой оптимизации и монотонных вариационных неравенств // Кибернетика и системный анализ. –2002. – №5. – С. 43-64.

  14. Пшеничный Б.Н., Калжанов М.У. Метод решения вариационных неравенств // Там же. –1992. – №6. – С. 48-55.

  15. Панин В.М., Лаврина Т.В. Проекционные методы решения нелинейных вариационных неравенств // Системні дослідження та інформаційні технології. –2002. – №2. – С. 103-117.

  16. Панин В.М., Скопецкий В.В., Лаврина Т.В. Модели и методы конечномерных вариационных неравенств. // Кибернетика и системный анализ. –2000. – №6. – С. 47-64.

  17. Пшеничный Б.Н., Соболенко Л.А. Метод обратно-выпуклого программирования и укладка параллелепипедов // Кибернетика и системный анализ. –1996. – №3. – С. 16-26.