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

МИНОБРНАУКИ РОССИИ

 

Федеральное государственное бюджетное  образовательное учреждение высшего  профессионального образования

 

"РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ  ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ" 

(РГГУ)

 

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И  ПРАВА

ФАКУЛЬТЕТ УПРАВЛЕНИЯ

 

 

 

 

 

 

 

 

 

 

 

Сергеев Станислав Владимирович

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

Контрольная работа по дисциплине Математические модели в управлении студента

1-го курса обучения (заочной дистанционной) формы  обучения

 

 

 

 

 

 

 

 

 

 

Руководитель

Гришина Наталья 

Васильевна

 

 

 

 

 

СОДЕРЖАНИЕ

 

Введение

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

1. Описание метода штрафных функций
2. Сходимость метода

II. Применение метода штрафных функций

Список использованных источников

 

Введение

 

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

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

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

Параметрические методы распадаются на три категории:

1. методы внутренней точки;
2. методы внешней точки;
3. комбинированные методы.

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

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

 

 

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

 

1. Описание метода штрафных функций

 

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

 

J(u)->inf; uÎU (1)

 

к последовательности задач минимизации

 

F_k(u)->inf; uÎ U₀, k=0,1,…, (2)

 

где F_k(u) - некоторая вспомогательная функция, а множество U₀ содержит U.При этом функция F_k(u) подбирается так, чтобы она с ростом номера k мало отличалась от исходной функции J(u) на множестве U и быстро возрастала на множестве U₀\U.Можно ожидать, что быстрый рост функции F_k(u) вне U приведет к тому, что при больших k нижняя грань этой функции на U₀ будет достигаться в точках, близких ко множеству U, и решение задачи (2) будет приближаться к решению задачи (1). Кроме того, как увидим ниже, и меняться достаточно широкий произвол в выборе функций F_k(u) и множества U₀ для задач (2), и можно надеяться на то , что задачи (2) удастся составить более простыми по сравнению с задачей (1) и допускающими применение несложных методов минимизации. Определение 1: Последовательность функций {Р_k(u), k=0,1,..}, определенных и не отрицательных на множестве U₀, содержащем множество U, называют штрафом или штрафной функцией множества U на множестве U₀, если

 

 

Из этого определения видно, что при больших номерах k за нарушение условия u U приходится "платить" большой штраф, в то время как приu

U штрафная функция представляет собой бесконечно малую величину при k-> . Для любого множества U Еⁿ можно указать сколько угодно различных штрафных функций. Например, если {А_k} – какая-либо положительная последовательность, А_k , то можно взять

 

Р_k(u)= А_kr(u,U), u Eⁿ U₀, k=0,1,…

 

(здесь U предполагается замкнутым) или

 

 

здесь r(u,U)= |u-v| - расстояние от точки до множества U, а - какая либо точка из U. Другие примеры штрафных функций будут приведены ниже. Допустим, что некоторое множество U , содержащее U,а также штрафная функция {Р (u)} множества U на U₀ уже выбраны . Предполагая, что функция J(u) определена на U₀, введем функции

 

(u)=J(u)+P (u), u U₀, k=0,1,... (3)

 

и рассмотрим последовательность задач (2) с функциями (3). Будем считать, что = (u)>- , k=0,1,… может и не достигаться. Поэтому будем считать, что при каждом k=0,1,… с помощью какого-либо метода минимизации найдена точка u_k, определяемая условиями:

 

u_k U_0, (u_k) (6),

 

где - некоторая заданная последовательность, , k=0,1,…, (если u_k удовлетворяет условиям (5), то в (6) допускается возможность =0). Отметим, что, вообще говоря, u_k U. Метод штрафных функций описан. Подчеркнем, что дальнейшее изложение не зависит от того, каким конкретным методом будет найдена точка u_k из (6). Поэтому мы здесь можем ограничиться предположением, что имеется достаточно эффективный метод определения такой точки.

 

2. Сходимость метода

 

Перейдем к исследованию сходимости метода штрафных функций. Т.к. при u U₀\U, то можно ожидать, что для широкого класса задача (1) последовательность {u_k}, определяемая условиями (6), будет приближаться ко множеству U и будут справедливы равенства:

 

  )=0

 

Мы здесь ограничимся  рассмотрением задачи (1) для случая, когда множество U имеет вид

 

U= , (7)

 

 

Где U₀- заданное множество из Еⁿ (например, U₀=Eⁿ), функции J(u),g_i(u) (i=1,…s),определены на U₀ . В качестве штрафной функции множества (7) возьмем

 

P_k(u)=A_kP(u),

P(u)= , u U₀ , (8)

 

Где А_k>0 (K=0,1,…), , a p 1 – фиксированное число.

Очевидно, если функции g_i(u) r раз непрерывно дифференцируемы на множестве U₀, то при любом p>r функция (8) также будет rраз непрерывно дифференцируема на U₀. Если в (8) p=1 , то из непрерывности g_i(u) (i=1,…,s) следует непрерывность P_k(u) на U₀ , но гладкости P_k(u) в этом случае ожидать не приходится. Полезно также заметить, что если U₀ – выпуклое множество функции g_i(u) при i=1,…,m выпуклы на U₀ ,g_i(u)=<a_i,u> - bⁱ – линейные функции при i=m+1,..,s, то функция (8) выпукла на U₀.

Если для краткости ввести обозначения

 

max{g_i(u);0} i=1,…,m,

g (u)= (9)

|g_i(u)|, i=m+1,…,s.

 

то функцию (8) можно записать в виде

 

P_k(u)=A_kP(u), P(u)= , u U₀.

 

Функцию P(u) мы иногда также будем называть штрафной функцией множества (7), подразумевая при этом, что после умножения на A_k>0, , она превратится в штрафную функцию в смысле определения 1.

Величины А_k из (8) будем называть штрафными коэффициентами.

Заметим, что существуют и другие штрафные функции множества (7). Например, вместо (8) можно взять

 

P_k(u)= ⁱ, u U₀, k=0,1,…,

 

где p_{i ,} A_ki>0, (i=1,…,s); здесь каждое ограничение из (7) имеет свой штрафной коэффициент. Весьма широкий класс штрафных функций множества (7) дает следующая конструкция:

 

P_k(u)= ⁱ, u U₀, k=0,1,…,

 

Где - произвольная функция, определенная при g 0 такая, что при g>0, i=1,…,s. При необходимости можно выбрать функции так, чтобы штрафная функция P_k(u) обладала различными полезными свойствами, такими, как, например, непрерывность, гладкость, выпуклость, простота вычисления значения функции и нужных производных и т. п. Возможны и другие конструкции штрафных функций множества (7). Приведем еще два конкретных примера штрафной функции

штрафной функция  программирование нелинейный

P_k(u)=(1+ )^A -1, p_{i ,}

P_k(u)=A ( ),

где A_k>0, (k=0,1,…), .

 

 

Теорема 1.

Пусть функции J(u), g_i(u) (I=1,…,s), определены на множестве U₀ , а последовательность {u_k} определена условиями (3), (6), (8). Тогда

 

J(u_k) Ф_k(u_k)= Ф_k*(u_k) J_*. (10)

 

Если, кроме того , J_**= ,то

 

P(u_k)= =О(А ), k=0,1,…, (11)

g_i(u_k) 0, i=1,…,m; g_i(u_k)=0, i=m+1,…,s. (12)

 

Доказательство. Так как P(u) ,то из (3), (6), (8) имеем

 

J(u_k) J(u_k)+A_k P (u_k)= (u_k) (u) =J(u_k)+A_k P (u_k) , "u U₀, k=0,1,...

 

Отсюда, переходя к нижней грани по u U и учитывая, что P(u)=0, uÎU,получим

 

J(u_k) (u_k) J_* , k=0,1,... (13)

 

При k из (13) вытекает (10)

Пусть теперь J_**>- .Так как J_* J_**,то J_*>- .С учетом (13) имеем

 

0 P (u_k)= (u_k)- J(u_k) J_* -J_** k=0,1,... ,или

0 P (u_k)=(J_* -J_** )А k=0,1,...

 

Оценка (11) доказана. Из нее следует, что P (u_k)=0 или g (u_k)=0 (i=1,…,s). Вспоминая определение (9) для g (u_k), отсюда получим соотношения (12). В общем случае неравенства в (10) могут быть строгими.

Теорема 2.

Пусть U₀- замкнутое множество из Еⁿ, функции J(u), g₁(u),…,g_m(u),|g_m+1(u),…,|g_s(u)| полунепрерывны снизу на U₀, J_**= . Пусть последовательность {u_k} , определяемая условиями (3), (6), (8), имеет хотя бы одну предельную точку. Тогда все предельные точки принадлежат множеству точек минимума задачи (1), (7). Если, кроме того, множество

 

U = , (14)

 

Ограничено хотя бы при  одном значении , то

 

Ф_k(u_k) Ф_k*= J(u_k)=J_*, (u_k,U_*)=0 (15)

 

Доказательство.

При сделанных предположениях для последовательности {u_k} соотношения (10)-(12) сохраняют силу. Пусть v_*–какая-либо предельная точка последовательности {u_k} , пусть {u_k } v_* . Заметим, что v_* в силу замкнутости U₀. Тогда с учетом полунепрерывности снизу указанных в условии теоремы функций из соотношений(12) получим

 

g_i(v_*) g_i(u_k ) g_i(u_k) , i=1,…,m

|g_i(v_*)| |g_i(u_k )|= |g_i(u_k)|=0, i=m+1,…,s

 

Следовательно, v_* .Тогда с учетом (10) имеем

 

J_* J(v_*) J(u_k ) J(u_k) , т.е. J(u_k )=J(v_*) =J_* или u_*

 

Наконец, пусть множество (14) ограничено при некоторых  .Из соотношений(12) следует, что {u_k} для всех k k₀.Это означает что {u_k}имеет хотя бы одну предельную точку. Тогда, как было выше показано все предельные точки {u_k} принадлежат . Следовательно, (u_k,U_*)=0.Из тех же рассуждений и неравенств (10)вытекают остальные равенства(15). Теорема 2 доказана.

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

Определение 2. Скажем, что задача (1), (7) имеет согласованную постановку на множестве U₀, если для любой последовательности {u_k} U₀, для которой g (u_k)=0 , i=1,…,s, (16) имеет место соотношение