Zhadan_lektsii_6_semestr

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

на R .Параметр p у первой функции можно полагать также равным +∞.

Беря внешнюю свертывающую функцию B(g), получаем внешний штраф ψ(x) =

Обозначим через X (t) множество точек,доставляющих минимум функции P (x, t) на Rn при фиксированном значении коэффициента штрафа t, т . е . множество

X (t) = Arg minn P (x, t).

x R

Определение16. Функция P (x, t) называется точной внешней штрафной функцией для задачи(109),если существует такое множество T значений коэффициента штрафа t, что X (t) = X при t T .

Как следует из утверждения теоремы ??,если у функции Лагранжа существует седловая точка [x , u ], то точка x является решением задачи(109).При этом f =

L(x , u ).

61

Доказательство. Имеем из правого неравенства в определении(115)седловой точки

Воспользуемся неравенством Минковского-Малера( ??),чтобы оценить скалярное произведение в правой части(116).Тогда

f ≤ f(x) + g(x), u ≤ f(x) + B(g(x))B0(u ).

Так как функция B(g(x)) неотрицательна на Rn, то беря t ≥ t = B0(u ) получаем f ≤ f(x) + B(g(x))B0(u ) ≤ f(x) + tB(g(x)) = P (x, t).

Таким образом, P (x, t) ≥ f для всех x Rn и любого t ≥ t .

Но B(g(x )) = 0, так как x X. В этом случае ,P (x , t) = f(x ) = f . Отсюда заключаем,что x X (t) и,стало быть, X X (t) для любого t ≥ t .Это в частности означает,что

Покажем,что при t > t множества X и X (t) совпадают.Доказательство проведем от противного:предположим,что существует t1 > t и x¯ X (t1) такие,что x¯ / X . Точка x¯ не может принадлежать допустимому множеству X, так как иначе из(117)следовало бы,что f(¯x) = f .Поэтому обязательно x¯ / X.Но тогда

причем B(g(¯x)) > 0.

Возьмем теперь t < t2 < t1. Так как t1 > t , то такое t2 всегда найдется.Тогда на основании(118

P (¯x, t2) = f(¯x) + t2B(g(¯x)) < f(¯x) + t1B(g(¯x)) = f ,

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

Если внешняя штрафная функция P (x, t) имеет вид

P (x, t) = f(x) + t g+(x) p, 1 ≤ 1 < ∞,

то B(g) = g+ p. Тогда , как следует из (16),B0(u ) = u p , где числа p и p связаны соотношением p−1 + p−1 = 1. Таким образом ,P (x, t) является точной внешней

штрафной функцией при t > B0(u ).

Отметим также,что для того,чтобы внешняя штрафная функция P (x, t) вида (114)была бы точной для задачи(109),в общем случае требуется,чтобы она была негладкой.

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

62

Алгоритм метода внешних штрафных функций. Задаем монотонно возрастаю -

щую последовательность коэффициентов штрафа tk → +∞ и полагаем k = 1. Шаг 1. Решая задачу безусловной минимизации

находим точку xk X (tk).

Шаг 2.Полагаем k := k + 1 и идем на шаг 1.

Если все задачи безусловной минимизации(119)имеют решения,то в результате работы алгоритма получается последовательность точек {xk}. Желательно , чтобы эта последовательность имела предельные точки и чтобы каждая предельная точка x была бы решением задачи(109).

Рассмотрим вопрос о сходимости метода внешних штрафных функций.Предположим,что все множества X (t) при t ≥ 0 принадлежат ограниченному множеству W . Данное условие заведомо будет выполняться,если существует такая точка x¯ Rn, что множество L(¯x) = {x Rn : f(x) ≤ f(¯x)} ограничено.Тогда последовательность {xk} принадлежит W и,следовательно,имеет предельные точки.

Теорема11. Пусть x предельная точка последовательности {xk}. Тогда

63

Но это противоречит неравенству(121).

Наконец,из неотрицательности функции ψ(x) и непрерывности f(x) следует

Таким образом,

f ≥ lim P (xk, tk) ≥ f(x ).

k→∞

Но x X. Отсюда , посколькуf(x ) ≥ f , заключаем , чтоf(x ) = f и имеет место предельное равенство(120).

Предположим,что в задаче(109)имеется седловая точка.Тогда,используя функцию,сопряженную к функции B(g), получаем с помощью неравенства Юнга - Фенхеля

Здесь (B t)(u) функция B (u), умноженная справа на константу t > 0.По определению такой операции (B t)(u) = tB (u/t).

Обозначим правую часть этого неравенства через q(t). Так как она не зависит от x, то из(123)получаем

64

а оценка q(t) с учетом того , чтоp = 2 при p = 2, становится равной

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

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

где h : Rn → Rl.Для этой задачи квадратичная штрафная функция принимает вид

Заметим также,что если в задаче дополнительно присутствуют ограничения простого вида x Π, например , допустимое множествоX задается следующим образом:

X = {x Π : g(x) ≤ 0m, h(x) = 0l},

то целесообразно не включать это ограничение в число общих функциональных ограничений,а вспомогательную задачу минимизации функции P (x, tk) на всем пространстве Rn заменить на задачу ее минимизации на множестве Π, т . е . вместо (119) решать задачу

min P (x, tk).

x Π

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

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

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

X0 = {x Rn : g(x) < 0m} .

Считаем,что множество X0 не пусто и что X0 = intX.Из этого предположения следует,чтоcl X0 = X.

Относительно последовательности функций {δk(x|X)} теперь будем предполагать,что каждая функция δk(x|X) является непрерывной и определена на Rn, но конечные значения принимает только на X0. Таким образом ,

65

1.δk(x|X) < +∞ для всех x X0;

2.δk(x|X) = +∞ для всех x / X0;

Кроме того,наложим на {δk(x|X)} следующие требования:

3. limk→∞ |δk(x|X)| = 0 для всех x X0;

4. если {δk(x)} последовательность неотрицательных на X0 функций,то δk(x|X) > δk+1(x|X) для любого x X0.

Согласно этим условиям δk(¯x|X) = +∞ для всех x¯ ∂X,причем выполняется предельное равенство

lim δk(x|X) = +∞.

x→x,¯ x X0

Поэтому аппроксимация функции δ(x|X) последовательностью функций {δk(x|X)} осуществляется только с точностью до границы,так как

lim δk(x|X) = δ(x|X), x X \ X0.

k→∞

Определение17. Внутренним штрафом или барьером будем называть непрерывную функцию ψ(x) такую,что ψ(x) < +∞ тогда и только тогда,когда x X0

и limx→x,¯ x X0 ψ(x) = +∞, если x¯ ∂X.

Используя барьер,можно построить внутреннюю штрафную функцию(барьерную функцию) в виде

P (x, t) = f(x) + tψ(x),

где t > 0 коэффициент внутреннего штрафа . Обозначим теперь

X (t) = Arg min P (x, t).

x X0

Алгоритм метода внутренних штрафных функций(метода барьерных функ-

ций).Задаем монотонно убывающую последовательность коэффициентов tk → +0 и полагаем k = 1.

Шаг 1.

Решаем вспомогательную задачу

и находим точку xk X (tk).

Шаг 2.Полагаем k := k + 1 и идем на шаг 1.

В результате работы алгоритма получаем последовательность точек {xk} X0. Если она ограничена,то имеет предельные точки x X.

66

Далее будем предполагать,что X компактное множество . Тогда точкиxk X (tk) существуют и xk X0.Считаем также для простоты,что ψ(x) ≥ 0 для всех

x X0.

Теорема12. Любая предельная точка x последовательности {xk} есть решение задачи(109)и

lim P (xk, tk) = f(x ) = f .

k→∞

Доказательство. Не ограничивая общности,считаем,что последовательность {xk} является сходящейся.Тогда xk → x . Так как X замкнутое множество,то x

X.

Если x / X , то из предположения clX0 = X следует,что найдется y X0 такое, что f(y) < f(x ) и,стало быть,

что противоречит определению точки xk X (tk), поскольку y X0. Таким образом ,

x X .

Далее,опять же в силу определения точек xk X (tk)

P (xk+1, tk+1) = f(xk+1) + tk+1ψ(xk+1) ≤

≤f(xk) + tk+1ψ(xk) ≤

≤f(xk) + tkψ(xk) = P (xk, tk),

т.е.последовательность {P (xk, tk)} является монотонно невозрастающей.Но она ограничена снизу,поэтому существует предел

lim P (xk, tk) = P ≥ f .

k→∞

67

Покажем,что строгое неравенство P > f невозможно и на самом деле имеет место равенство P = f .Действительно,иначе нашлись бы такие ε > 0 и δ > 0, что

y ∆ε(X ) ∩ X0 и

P (xk, tk) > f(y) + δ

для k достаточно больших.Но согласно(128)

δ

P (y, tk) = f(y) + tkψ(y) ≤ f(y) + 2,

если k достаточно большое.Отсюда и из(129)

δ

P (xk, tk) > P (y, tk) + 2

для этих k, что невозможно в силу определения точек xk.

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

Пусть Rm−− обозначает внутренность ортанта Rm− .Пусть,кроме того, Rø обозначает расширенную прямую,т.е.прямую R, пополненную элементами ±∞.

Определение18. Функция B(g) : Rm → Rø называется внутренней свертываю-

щей функцией,если она непрерывна на Rm и B(g) < +∞ при g Rm−− и B(g) = +∞ при g / Rm−−.

В качестве примера внутренних свертывающих функций приведем следующую функцию

где −∞ < p < 0 и g− отрицательная срезка вектора g Rm, т . еgi. = min[gi, 0]

−

для всех 1 ≤ i ≤ m.Когда g / Rm−−, полагаем :B(g) = +∞. Разумеется функция g p при p < 0 уже нормой не является,однако для однообразия обозначений знак нормы здесь сохранен.

Если воспользоваться функцией g 0, определенной как

то приходим к внутренней свертывающей функции,дополняющей семейство функции(130)при значении параметра p = 0:

B(g) = −ln ( g− 0) − 12, g Rm−−.

Здесь опять же считается,что B(g) = +∞ при g / Rm−−.

68

Использую внутренние свертывающие функции,строим внутренние штрафные функции в виде

P (x, t) = f(x) + tB(g(x)).

В частном случае,беря внутреннюю свертывающую функцию(130)при значении параметра p = −1, приходим к внутренней штрафной функции

которая носит название обратной барьерной функции.

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

Если опустить константы,которые не влияют на решение вспомогательных задач мининимизации(126),то функция(132)перепишется как

в задаче минимизации (126) в предположении , что в задаче нелинейного программи - рования(109)существует седловая точка [x , u ] функции Лагранжа.Вновь применяя неравенство Юнга-Фенхеля,как и в(122)приходим к оценке

где p−1 + p−1 = 1. Так как p < 0, то 0 < p < 1.Поэтому,в силу(134),нижняя оценка превышает f и стремится к f при p → 0. В частном случае при p = −1 для обратной барьерной функции P (x, t) получаем,что

i=1

В случае , когдаp = 0, для общей логарифмической барьерной функции (132)

69

имеем соответственно

и,следовательно,нижняя оценка q(t) опять стремится к f при t → +0. Оценка (136) в отличие от (135) справедлива только если u > 0m, т . е . если в решении задачи (109)

точке x все ограничения активны.

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

1.6.2.Метод параметризации целевой функции

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

Считаем,что задача имеет решение и обозначим через X множество ее решений. Пусть η оценка снизу оптимального значения целевой функции f .Если η < f ,

то система неравенств

f(x) − η ≤ 0, g(x) ≤ 0m

не имеет решения.Поэтому,беря произвольный внешний штраф ψ(x), например , ψ(x) = B(g(x)), где B(g) внешняя свертывающая функция,а также квадратичный внешний штраф для первого неравенства (f(x) −η)2+, приходим к тому , что функция

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

M2(x,η ) = (f(x) − η)2+ + B+2 (g(x)) > 0.

где x Rn и η R.Для данной вспомогательной функции поставим задачу без-

70