8.3. Метод штрафных функций. Метод штрафов алгоритм


Метод штрафов

Используется штрафная функция вида:

.

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

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

При обеспечивается сходимость метода.

          1. Метод барьерных функций

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

Обычно , а параметр.

При обеспечивается сходимость метода.

          1. Метод Фиакко-Мак-Кормика

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

Начальная точка задается так, чтобы ограничения-неравенства строго выполнялись.

Фиакко и Мак-Кормик предложили . Приобеспечивается сходимость метода.

          1. Метод множителей

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

где и- векторы множителей.

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

Метод обладает сверхлинейной сходимостью, если последовательность неограниченно возрастающая, в противном случае сходимость метода – линейная.

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

        1. Методы возможных направлений

Ненулевой вектор называется возможным направлением в точке, если существует такое, чтодля всех.

Вектор называется возможным направлением спуска в точке, если существует такое, чтоидля всех.

          1. Метод проекции градиента для задач с ограничением типа равенств

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

,

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

, где

где , а.

Вектор определяется по формуле:

,

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

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

Градиентная составляющая не меняет вектор невязки условий связи. Под ее действием точка движется параллельно или по плоскости.

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

.

Под действием этой составляющей осуществляется проекция точки на плоскость.

Расчет заканчивается в точке, в которой выполняются оба условия:

и .

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

Метод имеет линейную скорость сходимости.

studfiles.net

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

Пример

Найти максимальное значение функции

При условиях

В качестве исходного допустимого решения возьмем точку X(0) = (6,7). Шаг вычислений λ возьмем равным 0,1. Найдем частные производные от целевой функции и функции ограничения.

I итерация

Так как точка X(0) =(6,7) принадлежит ОДР, то:

g(X(1)) = 18 - 4,84 - 1,96 = 11,2 > 0

X(1) принадлежит ОДР. Найдем значение целевой функции в этой точке.

F(X(1)) = -54,4

II итерация

g(X(2)) = 18 - 9,9856 - 6,3504 = 1,664 > 0

следовательно, X(2) принадлежит ОДР

F(X(2)) = -34,816

|F(X(1)) - F(X(2))| = |-54,4 + 34,816| > ε = 0,1

следует продолжить итерационный процесс

III итерация

g(X(3)) = 18 - 15,429184 - 11,669056 ≈ -9,0982

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

IV итерация

Выбирать значение α будет таким образом, чтобы точка не слишком далеко удалялась от границы области и вместе с тем лежала внутри области. Этим требованиям, например, удовлетворяет α=1,9.

g(X(4)) = 18 - 9,3025 - 8,037225 ≈ 0,660 > 0

F(X(4)) = -32,95

|F(X(2)) - F(X(4))| = |-34,816 + 32,95| = 1,866 > ε = 0,1

продолжим итерационный процесс

V итерация

g(X(5)) = 18 - 14,7456 - 13,454224 ≈ -10,2 < 0

значит, точка не принадлежит ОДР

VI итерация

g(X(6)) = 18 - 9,078169 - 8,649481 ≈ 0,272 > 0

F(X(6)) = -32,372

|F(X(4)) - F(X(6))| = |32,95 + 32,372| = 0,578 > ε = 0,1

продолжим итерационный процесс

VII итерация

g(X(7)) = 18 - 14,523721 - 14,085009 ≈ -10,609 < 0

точка не принадлежит ОДР

VIII итерация

g(X(8)) = 18 - 9,006001 - 8,856576 ≈ 0,137 < 0

F(X(8)) = -32,185

|F(X(6)) - F(X(8))| = |32,372 + 32,185| = 0,578 > ε = 0,1

продолжаем итерационный процесс

IX итерация

g(X(9)) = 18 - 14,432401 - 14,295961 ≈ -10,728 < 0

следовательно, точка X(9) не принадлежит области допустимых решений.

X итерация

g(X(10)) = 18 - 8,976016 - 8,928144 ≈ 0,096 > 0

|F(X(8)) - F(X(10))| = |32,185 + 32,128| = 0,057 < ε = 0,1

Таким образом, точка X(10) = (4,004; 4,012) является искомым решением рассматриваемой задачи.

studfiles.net

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

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

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

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

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

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

¦(x) ® min ; xÎ X Ì En, (8.17)

gi(x) £ 0 , i = 1:m , (8.18)

в которой все функции ¦ , gi считаются непрерывными на всем пространстве En. Функция P(x), определенная и непрерывная на En, называется штрафной функцией, если выполняются следующие условия:

1.) P(x) = 0 "xÎ X ,

2.) P(x) > 0 "x Ï X .

Введем обобщенную функцию (k = 1,2,…)

¦(x, k ) = ¦(x) + kP(x) , (8.19)

где k – некоторое положительное число, называемое коэффициентом штрафа. В этом методе функции P(x) подбираются так, чтобы при больших k функция ¦(x , k) мало отличалась от ¦(x) при "x Î X и быстро возрастала при удалении точки x Ï X от допустимого множества, т.е. функция P(x) назначает положительный «штраф» за выход за пределы допустимого множества X , тогда как для точек из X «штраф» отсутствует.

Хорошо изучены штрафные функции следующих видов

(8.20)

Алгоритм оптимизационного поиска по методу штрафных функций состоит в следующем. Рассматривается некоторая неограниченная, монотонно возрастающая последовательность {k} , k = 1,2 ,… положительных чисел. Для первого числа k1(k = 1) этой последовательности находится точка x(1)*, доставляющая минимум функции (8.19). Найденная точка x(1)*используется как начальное приближение для решения задачи поиска минимума функции ¦(x, k2) , где k2 > k1 и т.д. Таким образом решается последовательность задач минимизации функции ¦(x, k) , k = 1,2….

Поскольку для бесконечно возрастающей последовательности {k} локальные минимумы приближаются к допустимой области, то последовательность {x(k)*} , k = 1,2,…, сходится к локальному оптимуму функции ¦(x) , расположенному внутри или на границе допустимой области.

В качестве критерия достижения требуемой точности решения задачи может служить неравенство ||x(k) – x(k/2)|| £ e , где e - число, характеризующее точность, k – четное число. При его выполнении полагают x*» x(k) , ¦ * = ¦(x(k)).

Для решения задач (8.19) можно использовать методы безусловной минимизации. Если в задаче (8.17) выпуклая квадратичная функция, а ограничения (8.18) линейные функции, то точное решение вспомогательной задачи (8.19) можно найти из системы линейных уравнений ¶¦(x, k)/¶xj = 0, j = 1:n, определяющих стационарную точку функции ¦(x, k). Поскольку точки x(k)* расположены вне допустимой области, поэтому метод штрафных функций называют также методом внешней точки.

Пример 8.4.

¦(x) = x ® min,

-x + 2 £ 0.

Решение. Рассмотрим в качестве штрафной функцию вида (8.20) , т.е. P(x) = (-x +2)2. Тогда

¦(x, k) = x + k (-x +2)2. (8.21)

Для определения минимума функции ¦(x, k) вычисляем ее производную по x и приравниваем ее к нулю :

¦¢(x, k) = 1 – 2k (- x +2) = 1 + 2kx – 4k = 0

Отсюда находим x(k) = .Очевидно, полученная последовательность точек сходится к решению исходной задачи :

x(k) = x*= 2.

Геометрическая иллюстрация примера дана на рис. 8.6. Числовые значения представлены в табл. 8.1.

Y k =3

5 k=2 y = x

4

2

  1. k=1

x(3)

. . .

1 x(1) x(2) 3 4 5 X

Рис. 8.6. Графическая иллюстрация задачи

Таблица 8.1

Значения f(x, k), представленной выражением (8.21)

Коэффициент штрафа

k = 1

k = 2

k = 3

x

f(x, k)

x

f(x, k)

x

f(x, k)

0

4

0

8

0

12

1

2

1

3

1

4

1,5*

1,75

1,5

2

1,5

2,25

-

-

1,75*

1,87

1,83*

1,92

2

2

2

2

2

2

Для минимизации ¦(x, k) на множестве X можно использовать, например, градиентные методы безусловной оптимизации. Нужно лишь дополнительно после каждой итерации градиентного метода, проверять, принадлежит ли очередное приближение множеству X , и в случае выхода за его пределы уменьшать величину шага.

Для контроля достигнутой точности решения можно использовать неравенство ||x(k) – x(k/2)|| £ e.

При использовании метода внутренней точки важен выбор начальных значений вектора x и параметра k. Необходимость задания начальной точки x Î X представляет непростую задачу, что является главным недостатком этого метода. Значение параметра k на первом этапе можно принимать k = 1.

studfiles.net

Метод штрафов — Википедия (с комментариями)

Материал из Википедии — свободной энциклопедии

Методы штрафов (методы штрафных функций) — методы, широко используемые для решения технических и экономических задач оптимизации[1].

Эффективны если штрафная функция естественно вытекает из технического смысла задачи.

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

Довольно часто применяются как в теоретических исследованиях, так и при разработке алгоритмов.

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

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

Указанное выше «мягкое» описание более адекватно описывает практические ситуации в экономике, чем «жесткое», в котором все ограничения должны выполняться строго.

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

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

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

История

Строго математически метод штрафа впервые использовал американский математик Р. Курант в 1943 г. (для изучения движения в ограниченной области)[1].

Методы широко применялись для решения задач локальной минимизации в 60-е годы. Одной из наиболее популярных была программа SUMT (разработчики — американцы Фиакко и Мак Кормик).

Недостатки

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

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

См. также

Напишите отзыв о статье "Метод штрафов"

Примечания

  1. ↑ 1 2 3 Жилинискас А., Шатлянис В. Поиск оптимума: компьютер расширяет возможности. — М.: Наука, 1989, с. 79, ISBN 5-02-006737-7
  2. ↑ Шмелев В. В. Точные штрафные функции в линейном и целочисленном линейном программировании. Автоматика и телемеханика. 1992. № 5. С. 106—115.

Литература

  • Ерёмин И. И., Костина М. А. Метод штрафов в линейном программировании и его реализация на ЭВМ, Ж. вычисл. матем. и матем. физ., 1967, том 7, номер 6, 1358—1366
  • Смуров С. И., Сокольская Т. В., Бобкова В. А. [dit.isuct.ru/ivt/sitanov/Literatura/M171/Pages/Glava3_2.htm Методы оптимизации]: Методические указания и задания к практическим занятиям и лабораторным работам / Иванов. хим.-технол. ин-т; Иваново, 1990. 72 с.

Ссылки

  • [www.machinelearning.ru/wiki/index.php?title=Метод_штрафных_функций Метод штрафных функций]
  • Потапов М. М. [www.riskstatistic.ru/Stati/potapov_m.m-lekcii_po_metodam_optimizacii_2003.pdf Методы оптимизации. Конспект лекций], МГУ, 2003

Отрывок, характеризующий Метод штрафов

– Бунапарте стоит! ишь врет, дура! Чего не знает! Теперь пруссак бунтует. Австрияк его, значит, усмиряет. Как он замирится, тогда и с Бунапартом война откроется. А то, говорит, в Брунове Бунапарте стоит! То то и видно, что дурак. Ты слушай больше. – Вишь черти квартирьеры! Пятая рота, гляди, уже в деревню заворачивает, они кашу сварят, а мы еще до места не дойдем. – Дай сухарика то, чорт. – А табаку то вчера дал? То то, брат. Ну, на, Бог с тобой. – Хоть бы привал сделали, а то еще верст пять пропрем не емши. – То то любо было, как немцы нам коляски подавали. Едешь, знай: важно! – А здесь, братец, народ вовсе оголтелый пошел. Там всё как будто поляк был, всё русской короны; а нынче, брат, сплошной немец пошел. – Песенники вперед! – послышался крик капитана. И перед роту с разных рядов выбежало человек двадцать. Барабанщик запевало обернулся лицом к песенникам, и, махнув рукой, затянул протяжную солдатскую песню, начинавшуюся: «Не заря ли, солнышко занималося…» и кончавшуюся словами: «То то, братцы, будет слава нам с Каменскиим отцом…» Песня эта была сложена в Турции и пелась теперь в Австрии, только с тем изменением, что на место «Каменскиим отцом» вставляли слова: «Кутузовым отцом». Оторвав по солдатски эти последние слова и махнув руками, как будто он бросал что то на землю, барабанщик, сухой и красивый солдат лет сорока, строго оглянул солдат песенников и зажмурился. Потом, убедившись, что все глаза устремлены на него, он как будто осторожно приподнял обеими руками какую то невидимую, драгоценную вещь над головой, подержал ее так несколько секунд и вдруг отчаянно бросил ее: Ах, вы, сени мои, сени! «Сени новые мои…», подхватили двадцать голосов, и ложечник, несмотря на тяжесть амуниции, резво выскочил вперед и пошел задом перед ротой, пошевеливая плечами и угрожая кому то ложками. Солдаты, в такт песни размахивая руками, шли просторным шагом, невольно попадая в ногу. Сзади роты послышались звуки колес, похрускиванье рессор и топот лошадей. Кутузов со свитой возвращался в город. Главнокомандующий дал знак, чтобы люди продолжали итти вольно, и на его лице и на всех лицах его свиты выразилось удовольствие при звуках песни, при виде пляшущего солдата и весело и бойко идущих солдат роты. Во втором ряду, с правого фланга, с которого коляска обгоняла роты, невольно бросался в глаза голубоглазый солдат, Долохов, который особенно бойко и грациозно шел в такт песни и глядел на лица проезжающих с таким выражением, как будто он жалел всех, кто не шел в это время с ротой. Гусарский корнет из свиты Кутузова, передразнивавший полкового командира, отстал от коляски и подъехал к Долохову. Гусарский корнет Жерков одно время в Петербурге принадлежал к тому буйному обществу, которым руководил Долохов. За границей Жерков встретил Долохова солдатом, но не счел нужным узнать его. Теперь, после разговора Кутузова с разжалованным, он с радостью старого друга обратился к нему: – Друг сердечный, ты как? – сказал он при звуках песни, ровняя шаг своей лошади с шагом роты. – Я как? – отвечал холодно Долохов, – как видишь. Бойкая песня придавала особенное значение тону развязной веселости, с которой говорил Жерков, и умышленной холодности ответов Долохова. – Ну, как ладишь с начальством? – спросил Жерков. – Ничего, хорошие люди. Ты как в штаб затесался? – Прикомандирован, дежурю. Они помолчали. «Выпускала сокола да из правого рукава», говорила песня, невольно возбуждая бодрое, веселое чувство. Разговор их, вероятно, был бы другой, ежели бы они говорили не при звуках песни. – Что правда, австрийцев побили? – спросил Долохов. – А чорт их знает, говорят. – Я рад, – отвечал Долохов коротко и ясно, как того требовала песня. – Что ж, приходи к нам когда вечерком, фараон заложишь, – сказал Жерков.

wiki-org.ru


Смотрите также