Точные штрафные функции в задачах условной оптимизации

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

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

1. Штрафные функции в задачах условной оптимизации

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

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

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

Штрафная функция является функцией со штрафными свойствами построенный из целевой функции f (x) и с ограничением c (x). Свойство «Штрафа» P (x)=f (x) требуется для всех допустимых точек x из (1)-(3), и P (x) значительно больше, чем когда ограничение нарушения являются строгими.

Для описания степени нарушения ограничения, мы определяем ограничение нарушение функции следующим образом:

Определяем Очевидно, х допустимая точка, если и только если c (x). Кроме того, Это означает для каждого ограничения, функция нарушение ограничения отлична от ненулевого когда соответствующие ограничение нарушается и нулю, если соответствующее ограничение является возможным.

Нетрудно заметь, что всех мы имеем:

где расстояние (-,-) обозначает расстояние от точки до множества и определяется как Штрафная функция состоит из суммы первоначального целевой функции и термин штрафа, то есть Где — это функция определенная на и удовлетворяет Ранние штрафные функции (функции Куранта) является штрафными функциями, или квадратичными штрафными функциями. Они определяются как

где у> 0 положительная постоянная, которая называется параметром штрафа.

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

Очевидно (12) это частный случай (10), в котором .

По сути, для любой нормы на и любой б > 0 функция удовлетворяет (11). Так, класс штрафных функций может быть определен как:

где у> 0 параметр штрафа, б> 0, и это некоторая норма на .

Типично, (12) часто записывается как и называется квадратичной функцией штрафа, где у> 0 и

Кроме того, (12), общие конкретные формы (14) являются и

которые называются штрафная функция и штрафная функция, соответственно.

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

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

Пусть х * точки ККТ условной оптимизации (1) — (3). Тогда из (12) следует, что ЃЮP (x) = ЃЮf (x). В общем, X * не стационарная точка штрафной функции Куранта, и метод штрафной функции пытается создать локальный минимизатор на х * в lim > ?.

Чтобы преодолеть этот недостаток, мы вводим параметры и i (i = 1,· ··, m) с иi? 0 (i = + 1,· ··, m) для изменения происхождение термина штрафа. Запись. Изменение (12) дает Где

Потому что штрафная функция (21) может быть получена из функции Лагранжа, добавив термин штраф, называется дополненной функции Лагранжа. В качестве альтернативы, (21) может быть получено также от штрафной функции (12), добавив термин множителя? c, (21) также называется множителем штрафных функций. Пусть х * точки ККТ в задаче условной оптимизации, и (i = 1,· ··, m) соответствующих множителей Лагранжа. Тогда функция Лагранжа с (i = 1,· ··, m) удовлетворяет ЃЮP (x) = 0. Кроме того, множитель Лагранжа л заранее не известен, поэтому функция Лагранжа нужно обновить лi (i = 1,· ··, m) успешно. Для равенства с ограниченной задачей (= m), мы определяем

где A (x)=(ЃЮ (x),· ··,ЃЮ (x)) это n Ч m матрица g (x) = ЃЮf (x), A+ обозначает обобщенная обратная A, и множитель л (х) является минимальной нормой решение задачи наименьших квадратов С помощью (23), мы можем дать гладкую функцию точных штрафных Флетчера (или дополненной функции Лагранжа Флетчера) для случая, когда только присутствуют ограничения типа равенств в (1)-(3) следующим образом:

где > 0 (i = 1,· ··, m) являются параметрами штрафа. Пусть х * решение задачи равенства ограничениями.

где D = Diag (, · ··,) и

Лемма 1

пусть H Ѓё симметрична и AЃё. Если

для любого ненулевого вектора d с d = 0, то существует у? 0 такой, что является положительно определенной матрицей.

2. Метод простых штрафных функций

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

Рассмотрим простую функцию штрафа

где у> 0 параметр штрафа, б> 0 положительная константа, и норма на .

Напишем х (у) как решение задачи Далее, мы сначала дадим несколько лемм.

Лемма 2

пусть 0 < у1 < у2, тогда

Лемма 3

пусть. Тогда x (у) также решение задачи

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

Алгоритм 1

Шаг 1. Дано

Шаг 2. Находим решение из Шаг 3. Если

устанавливаем

возвращаемся к шагу 2.

3. Обзор по точным штрафным функциям Постановка задачи.

Рассмотрим задачу математического программирования Предполагается, что — произвольные конечные функции заданные на Rⁿ, Обозначим через? множество допустимых планов задачи, обозначим также и

Пусть на Rⁿ задана произвольная неотрицательная функция ц такая, что ц (x) = 0 тогда и только тогда, когда точка x удовлетворяет ограничениям и Функция.

называется штрафной функцией для задачи, в частности, сели ц (x) = r (x), то соответствующая функция называется Б₁ штрафной функцией.

Напомним, что штрафная функция называется точной в точке x* локального минимума в задаче, если существует такое, что для любого точка х* является точкой локального минимума штрафной функции, Штрафная функция называется точной на множестве, если существует такое, что

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

Рисунок 1. Точная штрафная функция

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

Введём необходимые определения. Напомним, что функция f определённая на открытом множестве U из Rⁿ и принимающая вещественные значения называется аналитической, если для каждой точки из множества U существует окрестность, в которой функция f представима в виде сходящегося степенного ряда.

Множество называется полуаналитическим, если для каждой точки существуют окрестность U точки у и конечное семейство множеств, представимых в виде для некоторых вещественных аналитических функций fij, такое, что Другими словами, множество X является полуаналитическим, если оно локально представимо в виде объединения множеств решений систем равенств и строгих неравенств с аналитическими левыми частями. Подмножество называется субаналитическим, если для каждой точки существует окрестность U точки у такая, что множество представимо в виде проекции некоторого ограниченного полуаналитического множества на пространство для некоторого, Наконец, вектор-функция F называется полуаналитической (субаналитической), сели её график является полуаналитическим (субаналитическим) множеством. Теория полуаналитичееких и субаналитических функций восходит к работам М. С. Лояеевича.

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

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

где — евклидова норма, является субаналитической функцией. Таким образом, субаналитические функций вовсе не обязаны быть гладкими.

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

Теорема 1.

Пусть — компактное субаналитическое множество, функция f удовлетворяет условию Липшица на множестве X, а, функции и являются, непрерывными и субаналитическими на этом, множестве, Тогда существует такое, что для, любого штрафная, функция

является, точной на множестве X.

Следствие 1.

Пусть х* — точка локального минимума в задаче (52)-(54). Предположим, что функция f удовлетворяет условию Липшица в некоторой окрестности, точки х*, а функции и являются, непрерывными и субаналитическим, в некоторой окрестности, этой точки,. Тогда, существует такое, что для, любого штрафная, функция является, точной в точке х*.

5. Стационарные точки штрафной функции

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

Напомним, что величина

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

Предположим, что все функции f, непрерывно дифференцируемы на Rⁿ, Для любого введём множество

Будем говорить, что в точке x Е Rⁿ выполнено условие регулярности, если градиенты, линейно независимы.

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

Теорема 2.

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

Замечание 2.1, Пусть выполнены условия предыдущей теоремы. Предположим также, что функция f удовлетворяет условию Липшица на множестве X? с константой L > 0, и существует, а > 0 такое, что

.

(существование таких констант L > 0 и, а > 0 можно вывести из компактности множества X), Тогда можно показать, что утверждение теоремы выполняется при .

6. Точные барьерные функции

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

Зафиксируем, и определим штрафную функцию

при таких, что и

если. Напомним, что ц — это произвольная неотрицательная функция такая, что ц (x)= 0 тогда и только тогда, когда точка ж удовлетворяет ограничениям. Отметим, что введённую таким образом штрафную функцию достаточно рассматривать лишь на множестве

.

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

Приведём некоторые результаты о взаимосвязи штрафной функции с классической штрафной функцией, рассмотренной выше,

Предложение 1.

Пусть x* является точкой локального минимума, в задаче, и предположим, что функция ц непрерывна в точке x*. Тогда, функция является точной в точке x* тогда, и только тогда, когда, штрафная, функция F точна в этой точке.

Доказательство, Справедливость данного утверждения непосредственно вытекает из следующих очевидных неравенств

выполняющихся для любых x таких, что ,

Аналогичным образом доказываются следующие утверждения.

Предложение 2.

Пусть функция является точной барьерной функцией. Тогда, штрафная, функция является, точной на, множестве .

Предложение 3.

Пусть штрафная функция является точной на множестве. Тогда функция является, точной барьерной функцией для, любого .

Теорема 3.

Пусть выполнены следующие условия:

1) существуют такие, что

2) функция f удовлетворяет условию Липшица на множестве

3) функции f и ц полунепрерывны снизу на множестве

Тогда, функция является, точной барьерной функцией, для, любого .

7. Гладкие точные штрафные функции

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

Предположим, что функции f и, непрерывно дифференцируемы на Rⁿ. Зафиксируем ненулевой вектор. Для любых .

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

Введение

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

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

Теорема 4.

Пусть x* является точкой локального минимума, в задаче (56)-(57), причём ограничения регулярны в этой точке. Тогда штрафная, функция является, точной в точке (x*, 0), то есть существует такое, что для, любого точка (x*, 0) является, точкой локального минимума функции .

Теорема 5.

Пусть — открытое ограниченное множество, и предположим, что условие регулярности выполнено в каждой точке множества X. Тогда существует такое, что дм, любого справедливы следующие утверждения:

1) если (x*) — точка локального минимума штраф ной функции и, то е*=0 то есть x* — точка локального минимума в задаче (56)-(57).

2) если, x* G X — точка локального минимума в задаче (56)-(57), то точка (x*, 0) является, точкой локального минимума штрафной функции .

Схема алгоритма минимизации штрафной функции. Зафиксируем д₀ > 0, и положим k := 0. Также зададим точность ??> 0,

Шаг 1. Найдём точку () такую, что

Шаг 2. Если е_к = 0, то Стоп. Иначе перейдём на Шаг 3.

Шаг 3. Определим

где p > 1 — константа.

Шаг 4. Положим k := k + 1 и перейдём на Шаг 1,

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

Рисунок 2. Точная гладкая штрафная функция

Заключение

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

штрафной функция субаналитический

1. Евтушенко Ю. Г. Оптимизация и исследование операций [Текст] / Ю. Г. Евтушенко, под ред Н. Н. Моисеева; 1982. — 419 с.

2. Зангвилл У. И. Нелинейное программирование [Текст] / У. И. Зангвилл, под ред. Е. Г. Гольштейна 1969. — 306с.

3. Долгополик М. Точные штрафные функции в негладкой оптимизации / Семинар «CNSA & NDO»

4. WENYU SUN & YA-XIANG YUAN Optimization theory and methods [Text] / WENYU SUN & YA-XIANG YUAN. Springer Optimization and Its Applications, 2006;653с.

5. Малозёмов В.H. Теорема Куна-Таккера в дифференциальной форме // Семинар «DHA & CAGD»

6. Демьянов В. Ф. Условия экстремума и вариационное исчисление. М: Выеш. шк., 2004. 335 с.

7. Dedieu J.P. Penalty Functions in Subanalytic Optimization j j Optim, 1992, vol. 26. pp. 27−32

8. Luo Z.-Q, Pang J.-S., Ralph D., Wu S.-Q. Exact Penalization and Stationarity Conditions of Mathematical Programs with Equilibrium Constraints // Math, Program., 1996. vol. 75. pp. 19−76.

9. Lojasiewiez M.S. Sur le promleme de la division // Studia Mathematica, 1959. vol. 18. pp. 87−136.

10. Varga J. A necessary and sufficient condition for a constrained minimum // SIAM Journal on Optimization, 1992, vol, 2, pp, 665−667.

11. Lojasiewiez M.S. Ensembles semi-analytiques. Institut des Hautes Etudes Seientifiques, Bures-sur-Yvette, 1964.

12. Демьянов В. Ф. Условия экстремума и вариационное исчисление. М: Выеш. шк., 2004. 335 с.

13. Di Pillo, G., Grippo L. On the Exactness of a Class of Nondifferentiable Penalty Functions // J. Optim. Theory Appl., 1988. vol. 57. pp. 399−410.

14. Ye J, J, The Exact Penalty Principle Nonlinear Anal, 2012, vol, 75, pp. 1642−1654.

15. Малозёмов В.H. Теорема Куна-Таккера в дифференциальной форме // Семинар «DHA & CAGD»

16. Huver W., Neumaier A, A New Exact Penalty function j j SIAM, J. Optim, 2003. vol. 13. pp. 1141−1158.

17. Wang С., Ma, C., Zhou J. A New Class of Exact Penalty Functions and Penalty Algorith’ms // J. Glob. Optim., 2014. vol. 58. pp. 51−73.

18. Li B., Yu C.J., Teo K.L., Duan G.R. An Exact Penalty Function Method for Continuous Inequality Constrained Optimal Control Problem // J. Optim. Theory Appl., 2011. vol. 151. pp. 260−291.

19. Jiang C., Lin Q., Yu C., Teo K.L., Duan G.-R. An Exact Penalty Method for Free Terminal Time Optimal Control Problem with Continuous Inequality Constraints // J. Optim. Theory Appl., 2012. vol. 154. pp. 30−53.

20. Lin Q., Loxton R., Teo K.L., Wu Y.H. Optimal Feedback Control for DynamicSystems with State Constraints: An Exact Penalty Approach //Optim. Lett., 2014. vol. 8. pp. 1535−1551.

21. D.P. Bertsekas, Necessary and sufficient conditions for a penalty method to be exact, Mathematical Programming 9, 1975. pp. 87−99.

22. C. Charalambous, A lower bound for the controlling parameters of the exact penalty functions", Mathematical Programming 15, 1978. pp. 278−290.

23. J.P. Evans, F.J. Gould and J.W. Tolle, Exact penalty functions in nonlinear programming, Mathematical Programming 4, 1973. pp. 72−97.

24. S.-P. Han, A global convergent method for nonlinear programming, Journal of Optimization Theory and Applications 22, 1977. pp. 297−309.

25. S.P. Howe, New conditions for exactness of a simple penalty function, SIAM Journal on Control 11, 1973. pp. 378−381.

26. Bandler J.W. and Charalambous C. (1972), «Practical least /7-th optimization of networks», IEEE Trans. Microwave Theo. Tech. (1972 Symposium Issue), 20, pp. 834— 840.

27. Fletcher R., An exact penalty function for nonlinear programming with inequalities, Math. Progr. 5, 1973. pp. 129−150.

28. Fletcher R., An ideal penalty function for constrained optimization, J. Inst. Maths. Applns., 7, 1975. pp.76−91.

29. Fletcher R., Practical Methods of Optimization, Vol. 2, Constrained Optimization, John Wiley, Chichester, 1981(a).

30. Fletcher R., Numerical experiments with an exact 1_г penalty function method, in Nonlinear Programming 4, eds. O.L. Mangasarian, R.R. Meyer and S. M. Robinson, Academic Press, New York, 1981(b).

31. Васильев О. В., Аргунчинцев, А. В. Методы оптимизации в задачах и упражнениях. — М.: ФИЗМАТЛИТ, 1999.-208 с.-ISBN 5−9221−006−8.

32. Fletcher R., Second order corrections for nondifferentiable optimization", in «Numerical Analysis Proceedings, Dundee 1981, ed. G.A. Watson, Lecture Notes in Mathematics 912, Springer Verlag, Berlin. 1982.

33. Jorge Nocedal, Stephen J. Wright, Numerical Optimization .- Springer Optimization and Its Applications, 1999. 634 с.

34. P.T. Boggs, R.H. Byrd, and R.B. Schnabel, Nonlinear programming, exact penalty functions and projection techniques for nonsmooth functions,, eds., Numerical Optimization 1984, Society for Industrial and Applied Mathematics, Philadelphia, 1984, pp. 3−25.

35. S.P. Han and, O.L. Mangasarian, Exact penalty functions in nonlinear programming, Math. Programming, 17, 1979. pp. 251−269

36. S. Lucidi, New results on a class of exact augmented Lagrangians, J. Optim. Theory Appl., 58, 1988. pp. 259−282.

37. Черняк А. А., Новиков В. А., Мельников О. И., Кузнецов А. В. Математика для экономистои на базе Mathcad. — СПб.: БХВ-Петербург, 2003. — 496 с: ил. ISBN 5−94 157−282−4.

38. C. Vinante and S. Pintos, On differentiable exact penalty functions, J. Optim. Theory Appl., 50, 1986. pp. 479−493.

39. O.L. Mangasarian, Nonlinear Programming, Prentice-Hall, Englewood Cliffs, NJ, 1969.

40. D Q. Mayne and E. Polak, A superlinearly convergent algorithm for constrained optimization problems, Math. Programming Stud., 16, 1982. pp. 45−61.

41. W.I. Zangwill, Nonlinear programming via penalty functions, Management Sci., 13, 1967. pp. 344−358.