Методы высоких порядков в задачах нелинейной оптимизации Михеев, Сергей Евгеньевич

Введение к работе

Актуальность исследования. Значительная доля задач на оптимизацию какого либо объекта или процесса может быть сведена к задачам нелинейного программирования. Реальность редко дает возможность определить решения последних аналитически. Основной подход к поиску ответа связан с численными методами. Как первые алгоритмы на эту тему, так и большинство ныне активно используемых, состоят в основном из какой-либо модификации градиентного метода. Будучи весьма удобными по своей простоте для реализации, они, вместе с тем, оставляли открытым вопрос об эффективности для ряда задач, например таких, про которых было известно, что их целевая функция близка к квадратичной. С другой стороны, в некотором смысле заменяя исходную задачу на итерации ее линейной аппроксимацией, градиентные методы должны иметь ограничения на область применения этой аппроксимации, т.е. использовать такое понятие как шаг. Интересно, что эти два различных обстоятельства привели к внешне схожим нелинейным методам.

Близкая к квадратичной целевая функция / аппроксимируется квадратичной

~f{x, х^к) = f{x^k) + Vf(x^k)(x - х^к) + (х- x^k)^THj(x^k)(x - х²)/2,

и следующая итеративная точка определяется, как точка минимума функции f(x,x^k) по г. Под названием метод параболоидов (для поиска безусловного экстремума) это можно встретить у Лж. Ортеги и В. Рейнболдта еще до 1970 г. Метод параболоидов имеет свои трудности, в частности при наличии не положительных собственных чисел у матрицы Гесса II он не применим. Исправление ситуации добавлением at(x — х^к)², at > 0 к квадратичной аппроксимации восходит к К. Левепбергу (1944), к С. Гольдфельду, Р. Куранту, Т. Троттеру (1966 г.).

Метод линеаризации Б.Н. Пшеничного и Ю.Н.Данилина -итеративный метод решения нелинейных программ общего вида - обходит вопрос об области действия итеративной аппроксимации введением шага и введением добавки (х — х^к)²/2 в f(x^k)-\-Vf(x^k)(x — х^к) - линейную аппроксимацию целевой функции. Функции-ограничения в нем заменялись на линейные аппроксимации

д(х,х^к) = g(x^k) + Vg(x^k)(x - х^к).

В одной из модификаций метода линеаризации для ускорения сходимости предлагалось использовать квадратичную добавку (х — х^к)^тL_xx(x — х^к) к линейной аппроксимации целевой функции, где L_xx - гессиан соответствующей функции Лагранжа. В случае линейности функций-ограничений L_xr = Hj. Метод линеаризации использовался В.А. Даугавет в задачах чебышевского приближения без ограничений и с линейными ограничениями (1982, 1983 г.)

Минимизация на каждой итерации f(x,x^k) по х при ограничениях д(х,х^к) < 0, именуемая в работе методом квадратичной оптимизации (МКО), как часть метода последовательной оптимизации управления летательным объектом применялась В.М. Пономаревым (с 1970-х). Там целевая функция и функции-ограничения формировались в виде математических ожиданий функционалов на решениях систем дифференциальных уравнений. Поэтому "цена" каждого значения функции была очень высокой и даже существенное усложнение алгоритма минимизации легко окупалось повышением скорости сходимости. Конкретные реализации метода выявили высокую скорость сходимости метода во многих случаях, но теоретическое обоснование сходимости было найдено только для узкого круга. Не исследованным тогда остались скорость сходимости, выбор начальной точки, правило остановки, разобранные в этой работе.

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

Составной элемент МКО - тот или иной способ решения квадратичной программы. Одним из удобных для расширения на случай смешанных ограничений вида Ах < а и Вх = Ь и сочетания переменных ограниченных и неограниченных по знаку является метод Вила. В нем представляет интерес вопрос эффективного построения (по занимаемой алгоритмом памятью) начальной таблицы и проблема предотвращения зацикливания.

В одномерном случае итеративное решение скалярного уравнения д{х) = 0 и минимизация скалярной функции f(x) при помощи экстраполяционных полиномов порядка большего единицы восходит к П.Л. Чебышеву. Интерполяционные поли-

номы можно встретить в методе Мюллера и интерполяционном методе высокого порядка поиска одномерного минимума Н.Е.Кирина (1968 г.). Однако разнообразие методов на основе интерполяции, перспективных для исследования, этим далеко не исчерпывается.

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

Ряд задач на оптимизацию сводится к минимизации сепа-рабельных функций /(6^...,6) = 53/«'(^')> когда ]Г)6, = В, 6,- > 0, і — 1,п. Таковы, например, многие модели в экономике. Оптимизация разбиения памяти в базах данных при раз-делышом хешировании приводит к минимизации математических ожиданий Л/і = ^2рі/2^ь' (при спецификации одного поля в запросе), либо Мі — 2'S2(1 + Qi/2^h'), (когда специфицируется несколько полей) с дополнительным требованием целочисленности &!,...,&„. Задачи минимизации Mi и Mi без требования целочисленности можно рассматривать как непрерывные нелинейные аппроксимации исходных, имеющие простые алгоритмы решения в случае выпуклости /i,...,/_n. Использование таких аппроксимаций для итеративной минимизации при спецификации одного поля предлагалось Иж. Ритчи и Т. Лозано, при спецификации нескольких - А. Ахо и Дж. Ульманом. Неясной оставалась ситуация, когда налагается требование лишь целочисленности 2^Ъ\

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

Несколько снижаются вычислительные затраты на определение значений целевой функции, если в упомянутой последовательности от комбинации к комбинации происходит минимальное изменение состава элементов. Коды Грея позволяют созда-

вать алгоритмы минимального изменения, но даже в простейших случаях целевой функции вида f(x) = l^^t — -В| минуют вопрос об отсечениях. Для решения задач минимизации на пространствах с большим числом элементов за разумное время необходимо изыскивать новые алгоритмы, допускающие включение отсечений.

Цель исследования- дать теоретическое обоснование применения нелинейных аппроксимаций в задачах оптимизации. Произвести полный анализ сходимости метода квадратичной оптимизации. Произвести необходимые для применения в МКО модификации алгоритма решения квадратичной программы. Дать анализ сходимости методов на основе интерполяции полиномами высоких степеней с возможным учетом погрешности измерений. Разработать алгоритмы решения нелинейных программ на дискретных и комбинаторных пространствах. Методы исследования. Используются основные факты и методы теории функций, теории меры, алгебры, выпуклого анализа, нелинейного программирования.

Научная новизна состоит в следующем.

1. Установлены предельно широкие условия, когда решение не
линейной программы f(x) — min есть часть решения системы

д(х)<0

Vf(x) + \Vg{x) = 0 & А > 0 к \д{х) = О к д(х) < О

и обратно.

2. Установлены область сходимости и произведена оценка ско
рости сходимости метода квадратичной оптимизации (МКО),
строящего последующую итерацию х^к+1 по итерации х^к как
решение квадратичной программы

Vf(x^k)(x-x^k) + (x-x^k)^TH(x^k)(x-x^k)/2-+ min

3. Установлены критерии выбора начальной точки для МКО.

1. Установлены оценки вида ||a;^t+1 — х\\ < а\\х^к+1 — х^к\\ для МКО.

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

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

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

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

9. Приведен и обоснован алгоритм решения задач вида

где щ, ...u_n, и - неубывающие функции, возможно разрывные.

10. Для задач вида 2 fifti) ~> ^m>ⁿ> ^гД^е D - множество неотри-

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

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

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

Апробация материалов исследования проходила на семинаре кафедры информационных систем, на семинаре по теории управления под руководством В.И.Зубова в Санкт-Петербургском университете, на семинаре по дифференциальным уравнениям под руководством Н.М.Матвеева в Педагогическом университете им. А. Герцена, на семинаре в ВЦ РАН, на семинаре в UMIST (University of Manchester Institute of Science and Technology), на международных конференциях: CDE'IV (Руссе, Болгария, 1987), SICDE (Болгария, 1991), CSAM'93 (С.-Пб.), Interval 94 (С.-Пб.), ICI&C97 (С.-Пб.). По теме диссертации опубликовано 20 работ общим объемом 250 стр., из них одно учебное пособие (6 печатных листов).