Метод штрафа проекционные методы

Обновлено: 19.05.2024

4.2. Метод штрафных функций
Идея метода заключается в преобразовании
условной задачи минимизации (4.1) – (4.3) в
задачу поиска безусловного минимума
вспомогательной функции
F ( x , rt ) f ( x ) P (rt , g k ( x)) ,
(4.25)
где P(rt , g k ( x)) - штрафная функция,
rt 0 - параметр штрафа, t 0, 1, .
Штрафная функция определяет наказание за
нарушение каждого из ограничений (4.2), (4.3) и таким
образом препятствует выходу точки из допустимой области.

g k ( x) , если
g ( x)
если
0 ,
k
g k ( x) 0 ,
g k ( x) 0 .
(0)
x
За начальную точку поиска
можно принять любую
внешнюю точку, не удовлетворяющую ограничениям.
Для определения минимума вспомогательной функции
F ( x, rt ) решается последовательность задач t 0, 1, с
бесконечно возрастающим параметром штрафа rt .Для
организации итерационного процесса t 0, 1, может
быть использован любой численный метод безусловной
(t )
x
минимизации. Полученная точка
используется в
( 0)
(t )
x
x
качестве начальной точки
на следующей
итерации.

Условие окончания процесса поиска
P(rt , g k ( x ( t ) )) .
Метод штрафных функций относится к методу внешних
штрафных функций.
Пример 4.4. Решить задачу
f ( x) x1 x2 min ,
g1 ( x) x12 x2 0,
g 2 ( x) x1 0.
с точностью 0,01.
Решение. Составим вспомогательную функцию
2
2
(
x
)
2
1 , x1 0
F ( x, rt ) x1 x2 rt ( x 1 x2 )
.
x1 0
0,

Решая задачу безусловной минимизации
методом наискорейшего градиентного спуска для
возрастающей последовательности rt : 1, 2, 4, 16, ,
получим
x* (0,000975; - 0,000976) ,
f ( x * ) 0.

• штраф, задаваемый обратной функцией
m
1
P(rt , g k ( x)) -rt
;
k 1 g ( x )
k
• логарифмический штраф m
P (rt , g k ( x)) -rt ln[ g k ( x)] .
k 1
Обе штрафные функции стремятся к бесконечности
при приближении к границе области изнутри.
x (0)
За начальную точку поиска
можно принять любую
внутреннюю точку, удовлетворяющую ограничениям.

Для поиска минимума вспомогательной функции F ( x, rt )
(4.25) решается последовательность задач t 0, 1,
с монотонно убывающей последовательностью rt . На
практике обычно эта последовательность рассчитывается
по рекуррентному соотношению
rt
rt 1 , t 0, 1, ,
C
где
r0 - начальное значение, обычно
C
выбирается r0 1, 10, 100 ;
- константа. Удачным может быть выбор
C 10, 12, 16.

Поиск минимума функции
F ( x , при
rt )
заданном параметре
можно
проводить любым
rt
методом безусловной минимизации. Полученная
точка
используется в качестве начальной
(t )
x
точки
на следующей итерации.
( 0)
(t )
x окончания
x
Критерием
поиска служит неравенство
P (rt , g k ( x ( t ) ) .
Рассмотренный подход относят к методам
внутренних штрафных функций.

Пример 4.6. Решить задачу
f ( x) ( x1 4) 2 ( x2 - 4) 2 ,
g1 ( x) x1 x2 5 0.
при 0,01, r 0 100, c 10.
Решение. Составим вспомогательную функцию
F ( x, rt ) ( x1 4) 2 ( x2 4) 2 rt ln(5 x1 x2 ).
Решая задачу методом наискорейшего градиентного
спуска, получим
x* (2,499; 2,499).
F ( x* ; 0,001) 4,5.

Пример 4.5. Используя штрафную функцию
минимизировать функцию f (x) при ограничениях
x 2.
Перепишем ограничения в виде 2 x 0 .
Составим вспомогательную функцию
r
F ( x, rt ) x
.
2
(2 x)
На рис.4.2 изображен график функции F ( x, rt )
и показано положение точек ее минимума для
различных значений

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 01.10.2012
Размер файла 1,4 M

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

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

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

? в исследовании операций: оптимизация технико-экономических систем, транспортные задачи, управление запасами и т.д.;

? в численном анализе: решение линейных и нелинейных систем, численные методы, включая методы конечных элементов и т.д.;

? в автоматике: распознавание образов, оптимальное управление, фильтрация, управление производством, робототехника и т.д.;

? в математической экономике: решение больших макроэкономических моделей, моделей предпринимательства, теория принятия решений и теория игр.

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

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

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

1. Общая постановка задач оптимизации. Основные понятия и определения

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

Математическое программирование в самом общем виде можно определить как задачу оптимизации с ограничениями в пространстве R n :

Функция f(x) называется целевой функцией (функцией качества, критерием оптимальности), а множество условий gk(x), lj(x) и x?D - ограничениями задачи.

Решением задачи (1.1) называют любой вектор x, удовлетворяющий ограничениям, т.е. пара (х * , f(х * )), включающая точку х * и значение целевой функции.

Оптимальным решением или глобальным экстремумом задачи (1.1) называют вектор x*, минимизирующий значение f(x) на множестве всех решений: f (x*) ? f(x) для всех x ?D.

Задача максимизации функции сводится к задаче поиска минимума функции F = - f(x).

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

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

2. Нелинейное программирование

Ряд практических инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск экстремума. На первый взгляд может показаться, что уменьшение размеров области должно упростить процедуру поиска экстремума. Но, напротив, процесс оптимизации становится более сложным, т.к. установленные выше критерии оптимальности нельзя использовать при наличии ограничений. Может нарушаться даже основное условие - равенство нулю первой производной в стационарной точке. Например, безусловный min f (x) = (x ? 2) 2 имеет место при x*= 2 (т.е. ?f (x*) = 0). Но если задача решается с учетом ограничений x ? 4, то условный минимум достигается в точке x* = 4, где f (4) = 4 ? 0.

2.1 Методы последовательной безусловной оптимизации.

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

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

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

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

f (x)>min, xR n , (2.1)

gi(x) ? 0, i = 1, m (2.2)

hl (x)=0, l = 1, p.

Предполагается, что точка x* является решением этой задачи, известно некоторое начальное приближение x 0 , возможно недопустимое, т.е. не удовлетворяющее отношениям (2.2). С помощью рассматриваемых далее алгоритмов в пространстве R n строится конечная последовательность точек x t , t = 0,1,…, k, которая начинается с заданной точки x 0 и заканчивается точкой x k , дающей наилучшее приближение к точке экстремума x* среди всех точек построенной последовательности. В качестве точек последовательности x t > берутся стационарные точки штрафной функции - целевой функции вспомогательной задачи безусловной минимизации.

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

Рисунок 2.1 - Метод внутренних штрафов

Рисунок 2.2 - Метод внешних штрафов

В зависимости от того, являются ли элементы последовательности x t > допустимыми или недопустимыми точками, говорят соответственно о методах внутренней (рис. 2.1) или внешней точки (рис. 2.2) Иногда их называют методами внутреннего или внешнего штрафа. Методы внутренних штрафных функций называют также методами барьерных функций.

Понятие штрафных функций

Штрафная функция определяется выражением:

P (x, R) = f (x) + H (R, g(x), h(x)), (2.3)

где R - набор штрафных параметров,

H - штраф - функции R и ограничений,

H (R, g(x), h (x)) = R? (g(x), h(x)).

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

Методы внутренней точки связаны с такими H, при которых стационарные точки функции P (x, R) оказываются заведомо допустимыми.

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

Методы штрафных функций представляют большой интерес лишь при выполнении следующих требований:

1) решения подзадач должны стремиться к решению задачи нелинейного программирования вида:

lim x t > x*, t >k t + 1 = F(R t ) должно быть простым.

В данной работе мы рассмотрим метод внешней точки (метод внешнего штрафа).

Основные типы внешних штрафов.

Квадратичный штраф используется для учета ограничений-равенств вида:

H = R·(h (x)) 2 . (2.4)

При минимизации этот штраф препятствует отклонению величины h(x) от нуля (как вправо, так и влево). Ниже будет видно, что при увеличении R

стационарная точка соответствующей штрафной функции P (x, R) приближается к точке x*, т.к. в пределе h(x k ) = 0. Поскольку допустимая область S определяется ограничением h(x) = 0, то в допустимой области значение штрафа H = 0, а вне допустимой области H > 0 и тем больше, чем дальше точка x t выйдет за пределы допустимой области и чем больше R.

Рис. 2.3 - Квадратичный штраф

Штраф типа квадрата срезки

Отметим, что H - внешний штраф, и стационарные точки функции P (x, R) могут оказаться недопустимыми. С другой стороны, недопустимые точки не создают в данном случае дополнительных сложностей по сравнению с допустимыми. Различие между ними состоит лишь в том, что в допустимых и граничных точках H = 0.

Достоинства: функция P (x, R) определена и непрерывна всюду. Вычисления проводятся с положительными R; после решения очередной задачи безусловной минимизации R увеличивается.

Выбор штрафного параметра

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

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

При этом необходимо установить, как именно будет изменяться R при переходе от одной подзадачи к другой. Например, для обычного квадратичного штрафа, учитывающего ограничения равенства, целесообразно начинать с R = 0, т.е. безусловной минимизации функции, а затем последовательно увеличивать R на некоторое ДR. Вычислительные эксперименты показывают, что точно найденная стационарная точка x t (R) перемещается вдоль некоторой гладкой кривой к точке x*.

С другой стороны, пересчет параметра R, имеющий целью обеспечить сходимость метода, автоматически приводит к ухудшению обусловленности вспомогательных задач (появление овражной структуры штрафной функции). Во многих методах безусловной оптимизации используется матрица Гессе - ? 2 P (x, R). Показано, что часть собственных значений этой матрицы зависит от величины R. При этом обусловленность матрицы Гессе ? 2 P (x, R) неограниченно ухудшается, когда R>?. Тем самым усложняется процесс решения вспомогательных задач безусловной оптимизации.

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

Шаг 1: задать значения n, m, p, е1, е2, е3, x 0 , R 0 ,

где n - размерность вектора x;

m - число ограничений-неравенств;

p - число ограничений-равенств;

е1 - параметр окончания одномерного поиска;

е2 - параметр окончания процедуры безусловной минимизации;

е3 ? параметр окончания работы алгоритма;

x 0 - начальное приближение для x*;

R 0 - начальный вектор штрафных параметров.

Шаг 2: Построить P (x, R) = f (x) + H (R, g(x), h(x)).

Шаг 3: Найти значение x t + 1 , доставляющее минимум функции P(x t + 1 , R t )

при фиксированном R t . В качестве начальной точки использовать x t , в качестве параметра окончания шага - константу е2.

Шаг 4: Проверка выполнения условия:

|P (x t + 1 , R t )? P (x t , R t ? 1 )| ? е3.

Да: положить x k = x t + 1 > конец.

Шаг 5: Положить R t + 1 = R t + ДR t в соответствии с используемым правилом пересчета n > Шаг 2.

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

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

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

Функция Лагранжа в условиях оптимальности выглядит следующим образом:

где R - постоянный весовой (нормирующий) коэффициент (в принципе, R может зависеть от номера ограничения i, но не от номера итерации t);

- символ, обозначающий оператор срезки.

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

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

Начальная точка x0 не обязательно должна быть допустимой, а начальные значения у и ф удобно (но не обязательно) выбирать нулевыми.

Формулы пересчета у и ф

Обозначим: x t - точка минимума штрафной функции на t - ой итерации,

т.е. функции P (x, у, ф).

При переходе к (t +1) - ой итерации множители пересчитываются по формулам:

Вектор у не имеет положительных компонент из-за наличия в формуле оператора срезки (gi (x) ? 0). Компоненты ф могут иметь любой знак.

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

Для контроля сходимости метода используют последовательности

x t ,у t , ф t , f (x t ), g (x t ), h (x t ).

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

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

Связь параметров уi, фi с множителями Лагранжа.

Рассмотрим величины у k , gi(x k ), ф k , hl(x k ), предполагая, что они являются пределами соответствующих последовательностей. Из (2.10) видно, что ф k может существовать, если только hl(x k ) = 0.

Аналогично, в силу (2.9) для существования предельных значений

у k и gi(x k ) необходимо выполнение одного из следующих условий: либо

С учетом этого запишем выражение для градиента штрафной функции (2.8) в точке x k :

Первые три ограничения следуют из (2.12).

Отсюда мы видим, что соотношения (2.13) - (2.16) - это условия Куна-Таккера для точки x k . Таким образом, полученная предельная точка является точкой Куна-Таккера. Из (2.12) видно, что соответствующие значения множителей Лагранжа могут быть найдены по формулам:

то есть, по существу, без каких-либо дополнительных вычислений.

Недостатки: Элементы итерационной последовательности x t приближаются к x*, находясь почти всегда вне допустимой области отсутствие правила выбора R.

3. Решение задач методом штрафов

Найти минимум в задаче:

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

P (x, R) = (x1 - 4) 2 + (x2 - 4) 2 + R·(x1 + x2 - 5) 2

Запишем уравнения, определяющие стационарную точку функции P (x, R):

Выразим x1 и x2 через R: вместо x2 подставим в первое выражение x1 (и сократим на 2):

Переходя к пределу, получим:

Таким образом, метод сходится к точке x* = [2,5; 2,5], тогда f (x*) = 2,25 + 2,25 = 4,5.

В таблице 1 приведены результаты расчетов при R = 0,0.1, 1, 10,100,1000 …и т.д. Подсчитаем первую строчку этой табл иц ы .

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

f(X) ® min


(3.5.1)

А именно, вместо задачи (3.5.1) рассмотрим задачу безусловной минимизации

F(X, rs)=f(X)+P(X, rs) ® min, (3.5.2)


P(X, rs)= ,

=max = ,

rs - так называемый параметр штрафа. Функция P(X, rs) называется штрафной функцией.

3.5.1. Пусть X * - локально единственное решение задачи (3.5.1) (то есть существует окрестность точки X * , в которой X * является единственным решением задачи), функции f(X) и непрерывно дифференцируемы в окрестности точки X * . Тогда для достаточно больших rs найдётся точка X * (rs) локального минимума функции F(X, rs) в окрестности X * и X * (rs)=X * .

Таким образом, для решения задачи (3.5.1) достаточно:

1. Составить функцию F(X, rs)=f(X)+P(X, rs).


2. Найти частные производные , j=1, 2, …, n.


3. Решить систему =0, j=1, 2, …, n. Пусть X * (rs) - её решение.

4. Исследовать на знакоопределённость матрицу Гессе H(X * (rs), rs) функции F(X, rs), и если достаточное условие минимума выполняется, то выполняем остальные пункты:

5. Найти пределы xj(rs)= . Тогда X * =( , , …, ) - решение задачи (3.5.1).

6. Найти значения функции f(X) в точках X * локального минимума.

Пример I. Исследовать на условный экстремум функцию:


f(X)= ® min

3x1-2x2-5=0.

Решение. 1. Составим функцию F(X, rs):

F(X, rs)= + (3x1-2x2-5) 2 .

2. Найдём частные производные , :

=4x1+3rs(3x1-2x2-5), =8x2-2rs(3x1-2x2-5)


3. Решаем систему =0, j=1, 2:

Û

Первое уравнение, умноженное на 2, прибавим ко второму, умноженному на 3: 8x1+24x2=0, откуда получаем x1=-3x2. Теперь подставляем это выражение для x1, например, в первое уравнение системы: -12x2-33rsx2-15rs=0, откуда x2(rs)=- и x1(rs)=-3 = .

4. Исследуем на знакоопределённость матрицу Гессе H(X * (rs), rs) функции F(X, rs). Имеем

=4+9rs, =8+4rs, = =-6rs, H(X * (rs), rs)= ,


то есть D1>0, D2>0, и матрица Гессе H(X, rs)= - положительно определённая. Это означает, что достаточные условного минимума выполнены.

5. Найдём пределы xj(rs)= , j=1, 2. Имеем

x1(rs)= = , x2(rs)= =- .

Поэтому X * =( , - ) - решение задачи.

6. Найдём значения функции f(X) в точке X * =( , - ) локального минимума: fmin(X)=f(X * )=2 +4 = = .

Ответ: X=( , - ) - точка условного локального минимума, fmin(X)= .

Пример II. Исследовать на условный экстремум функцию:


f(X)= ® min


Решение. 1. Составим функцию F(X, rs):

F(X, rs)= + =


=

2. Найдём частные производные , :

=

=


3. Решаем систему =0, j=1, 2:


Случай 1. . Тогда

Û

Первое уравнение, умноженное на 2, прибавляем ко второму, умноженному на 3: 8x1+24x2+rs(x1-1)=0, откуда получаем x2=- x1- . Теперь подставляем это выражение для x2, например, в первое уравнение системы, последовательно получим:


, Û

Û Û ,


откуда x1(rs)= и

x2=- x1- = = + =

× + = ,


то есть x2(rs)= .

3 -2 -5= .


Это выражение отрицательно, что вступает в противоречие с условием . Значит, этот случай невозможен.


Случай 2. . Тогда

Û


откуда x2(rs)=0 и x1(rs)= .

4. Исследуем на знакоопределённость матрицу Гессе H(X * (rs), rs) функции F(X, rs). Имеем

=4+rs, =8, = =0,


H(X * (rs), rs)= , D1=4+rs>0, D2=(4+rs)8>0,


и матрица Гессе H(X * (rs), rs)= - положительно определённая. Это означает, что достаточные условного минимума выполнены.

5. Найдём пределы xj(rs)= , j=1, 2. Имеем

x1(rs)= =1, x2(rs)= 0=0.

Поэтому X * =(1, 0) - решение задачи.


6. Найдём значения функции f(X) в точке X * =(1, 0) локального минимума: fmin(X)=f(X * )=2× +4×0 2 =2.

Ответ: X=(1, 0) - точка условного локального минимума, fmin(X)=2.

Пример III. Исследовать на условный экстремум функцию:


f(X)= ® min


Решение. 1. Составим функцию F(X, rs):

F(X, rs)= + ,

=

=

так что функция F(X, rs) зависит от того, отрицательны или неотрицательны функции и . Поэтому рассмотрим отдельно четыре случая

Случай 1. £0 и £0. Тогда

F(X, rs)= , = , = ,

Û Û


Но это противоречит условию £0 Û x1³1.

Случай 2. £0 и >0. Тогда

F(X, rs)= + ,

= , = ,

Û

откуда x1(rs)= и x2(rs)=- (см. решение Примера I). Но при этом имеем

=3 -2 -5=- 0 и £0. Тогда

F(X, rs)= + , = , = ,

Û


откуда x2(rs)=0 и x1(rs)= . При этом оба неравенства выполняются:

(rs)=1- = >0,

=3 -2×0-5=- .

Как мы уже видели, (см. решение Примера II), X * =(1, 0) - точка локального минимума: fmin(X)=f(X * )=2.

Случай 4. >0 и >0. Тогда

F(X, rs)= + ,

= , = ,

Û

откуда x1(rs)= и x2(rs)= (см. решение Примера II). Но мы уже видели (см. там же), что тогда , что противоречит условию случая.




Ответ: X=(1, 0) - точка условного локального минимума, fmin(X)=2.

3.6. Упражнения. Исследовать функции на условный экстремум:

1) а) ® extr б) ® extr

; ;


в) ® extr

x1+x2+6=0.

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

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

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

12.1. ОСНОВЫ МЕТОДОВ ШТРАФНЫХ ФУНКЦИЙ И БАРЬЕРОВ

Методы штрафных функций и барьеров используются для решения задачи НЛП

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

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

Рис. 12.1. Бесконечно большой штраф.

В качестве иллюстрации этого подхода рассмотрим функцию

где — допустимое множество.

Комбинируя составляем функцию

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

Таким образом, задача (12.1) преобразована в эквивалентную задачу без ограничений.

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

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

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

Рис. 12.2. Представление функции

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

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

При этом, если то функция аппроксимирует функцию при (рис. 12.2).

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

Определим как точку , максимизирующую

(мы полагаем, что эти существуют). Тогда

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

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

Показаны точки и оптимальная точка х. Ясно, что

Таким образом, вырабатывается последовательность Как будет доказано, предел любой сходящейся подпоследовательности будет решением задачи (12.1) (рис. 12.3).

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

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

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

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

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

и последовательность такую, что

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

Рис. 12.4. Метод барьеров.

что максимизирует на Дальше мы докажем, что любая предельная точка этой последовательности является оптимальной для задачи (12.1) (рис. 12.4).

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

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

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

Читайте также: