Лекция №11. Метод штрафных функций



Скачать 63.19 Kb.
Дата12.11.2016
Размер63.19 Kb.
Лекция № 11.

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

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

Для метода штрафных функций семейство вспомогательных функций (семейство штрафных функций) имеет вид:

,

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



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



при .

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

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

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



Теорема 1. При приведенных выше условиях существуют конечные пределы и выполнены соотношения:

, (1)

. (2)

Доказательство. Пусть . Из определения минимального значения справедливо неравенство , которое вместе с соотношением определяет справедливость цепочки неравенств:

. (3)

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

Пусть опять зафиксированы числа . Из неравенств

и следует, что

и .

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

Далее, так как по определению, то . Отсюда, в частности, следует, что все , а если найдется при некотором , то эта точка является решением исходной задачи. Кроме того, ограничена сверху, что означает существование конечного предела . Следовательно, в силу (1) справедливо . 

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



Теорема 2 (сходимости). Пусть существует такое замкнутое ограниченное множество , что для всех , то

.

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

. (4)

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

В силу (2) и непрерывности функции . Следовательно, . Таким образом, неравенство переходит в равенство , однако этот факт противоречит сделанному предположению. 

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

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



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


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

Теорема 3 (о способе аппроксимации). Пусть функция выпукла и удовлетворяет на условию Липшица с константой , функция сильно выпукла с постоянной и . Тогда для всех .

Доказательство. Предположим, что существует такое, что точка такова, что . Следовательно, принадлежит внутренности множества , причем точка этой внутренности не принадлежит как точка минимума функции а множестве , т.е. . Таким образом, , но , , причем - множество выпуклое, а следовательно, должно содержать точку . Таким образом,

.

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



. 

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

Теорема 4 (о штрафном коэффициенте). Пусть функция -регулярна с параметрами и удовлетворяет на условию Липшица с константой , функция выпукла и удовлетворяет на условию Липшица с константой . Тогда при для выполняется .

Доказательство. Пусть (случай неинтересен и очевиден). Возьмем любое . Так как , то . . Последнее неравенство выполняется и для той точки , в которой достигается . Таким образом, . Известно (Сухарев, Тимохов, Федоров), что . Следовательно, . Таким образом, , или , т.е. . 

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


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

    Главная страница