close

Вход

Забыли?

вход по аккаунту

?

Применение удовлетворительной аппроксимации допустимого множества при решении задач оптимизации.

код для вставкиСкачать
Том 154, кн. 3
УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОО УНИВЕСИТЕТА
Физико-математические науки
2012
УДК 519.853+519.68
ПИМЕНЕНИЕ УДОВЛЕТВОИТЕЛЬНОЙ
АППОКСИМАЦИИ ДОПУСТИМОО МНОЖЕСТВА
ПИ ЕШЕНИИ ЗАДАЧ ОПТИМИЗАЦИИ
А.А. Андрианова
Аннотация
абота посвящена исследованию свойств и принципов построения удовлетворительной
аппроксимации множества допустимых решений задачи условной оптимизации. Замена
в ходе решения исходного допустимого множества на его удовлетворительную аппроксимацию позволяет построить конечные алгоритмы методов внутренней и внешней точек
(методов штраных ункций или методов центров) с критерием остановки, гарантирующим выполнение заданной точности полученного решения. Доказаны необходимые и достаточные условия для построения внешней и внутренней удовлетворительных аппроксимаций допустимого множества. Сормулирован один из реализуемых способов задания
множества, являющегося удовлетворительной аппроксимацией допустимого множества,
которое можно использовать при построении алгоритмов, гарантирующих получение заданной точности за конечное число итераций.
Ключевые слова: методы последовательной безусловной минимизации, метод
штраных ункций, метод центров, решение задачи оптимизации с заданной точностью,
удовлетворительная аппроксимация допустимого множества, реализуемые критерии остановки.
Введение
Практическое применение методов непрерывной минимизации связано не столько с получением точного решения задачи, сколько с нахождением приближенного
решения с заданной точностью ? > 0 . Поскольку большинство известных методов обеспечивает сходимость к точному решению задачи, остановку вычислений
производят на основании критериев близости к оптимуму. Однако довольно часто
эти критерии оказываются эвристическими и их применение может привести к выбору точки, далекой от точного решения. Поэтому актуальной задачей является
разработка алгоритмов, которые имеют простые критерии проверки достижения
заданной точности, гарантировано выполняющиеся после конечного числа итераций применяемого метода.
Один из подходов к разработке таких алгоритмов заключался в аппроксимации допустимого множества решений. Он был применен по отдельности в методах
последовательной безусловной минимизации [13? в методе штраных ункций
[4, 5? и в методе центров (параметризации целевой ункции) [68?. Данный подход
заключался в замене исходного допустимого множества задачи на его аппроксимацию (вложенное или окаймляющее множество) и в решении построенной таким
образом вспомогательной задачи одним из указанных выше методов. Способ получения аппроксимации в этом случае сильно зависел от применяемого метода
оптимизации. Было доказано, что за конечное число итераций гарантируется получение точки из разности исходного допустимого множества и его аппроксимации,
УДОВЛЕТВОИТЕЛЬНАЯ АППОКСИМАЦИЯ. . .
191
что является критерием остановки вычислений и гарантией заданной точности полученного решения.
В настоящей работе производится обобщение данного подхода путем введения
понятия ? -удовлетворительной аппроксимации допустимого множества для задачи
математического программирования, получения необходимых и достаточных условий задания таких множеств и ормулировки обобщенной схемы применения аппроксимаций в методах последовательной безусловной минимизации (внутренней
и внешней точки) с целью получения ? -решения задачи оптимизации за конечное
число шагов. Вводные положения для случая применения метода внешней точки
при таком подходе были рассмотрены в [9?.
При построении практических алгоритмов на базе данной схемы предполагается использовать априорные знания о целевой ункции и ункциях-ограничениях
задачи оптимизации констант Липшица, сильной выпуклости, (?, ?, ?) -аппроксимируемости или сильной квазивыпуклости. Такие константы нередко используются для оценки скорости сходимости того или иного метода оптимизации (см.,
например, в [13, 10?). Полученные таким образом оценки могут быть применены
для ормулировки критерия остановки вычислений. Обычно такие оценки существенно зависят от управляющих параметров применяемого метода оптимизации,
что позволяет их использовать только непосредственно в алгоритмах на базе этого
метода. Отличительной особенностью схем, предлагаемых в настоящей статье, является универсальный для методов последовательной безусловной минимизации
способ применения априорно заданных констант для построения практических
алгоритмов решения задач условной минимизации с гарантией достижения требуемого уровня точности.
1. Постановка задачи
Пусть решается следующая задача оптимизации:
min{f (x), x ? D},
(1)
где D = {x ? Rn : fi (x) ? 0, i = 1, . . . , m} , целевая ункция f и ункции-ограничения fi , i = 1, . . . , m , определены и непрерывны в n -мерном евклидовом
пространстве Rn и принадлежат классу ункций, каждый локальный минимум
которых является абсолютным, множество D регулярно по Слейтеру, то есть существует точка y ? D , для которой выполняются неравенства fi (y) < 0 для всех
i = 1, . . . , m .
Пусть требуется найти решение задачи 1 с заданной точностью ? > 0 . Введем
следующие обозначения:
f ? = min{f (x), x ? D},
X?? = {x ? D : f (x) ? f ? + ?},
?
X ? = {x ? Rn : |f (x) ? f ? | ? ?}.
?
Множество X?? является множеством ? -решений задачи (1), а в множество X ?
входят и те точки, которые не являются допустимыми. Это множество принято
называть множеством ? -псевдорешений задачи (1). Будем считать далее, что
f ? > ?? , минимум достигается и множество X?? является ограниченным. Будем
также полагать, что абсолютный минимум целевой ункции достигается за пределами множества D , откуда, в частности, следует, что точка оптимума лежит на
границе множества D . Случай принадлежности оптимума внутренности множества D рассматривался, например, для метода центров в [11?; при определенных
условиях он может быть сведен к задаче минимизации специальным образом построенной вспомогательной ункции.
?
Требуется получить точку z из множества X?? либо из множества X ? .
192
А.А. АНДИАНОВА
2. Понятие ? -удовлетворительной внутренней аппроксимации
допустимого множества
Определение 1. Внутренней аппроксимацией множества допустимых реше-
ний D задачи (1) назовем множество G1 вида {x ? Rn : ?i (x) ? 0, i = 1, . . . , r} ,
для которого выполняются условия G1 6= ? и G1 ? D . Здесь ?i , i = 1, . . . , r , непрерывные в Rn ункции, отличные от fi , i = 1, . . . , m , каждый локальный
минимум которых является абсолютным.
Заменим исходную задачу (1) на следующую вспомогательную задачу
(2)
min{f (x), x ? G1 },
где G1 внутренняя аппроксимация множества D задачи (1). Для задачи (2)
введем следующие обозначения для точки минимума и множества точек, которые
входят в ѕполоскуї, образованную разностью исходного множества D и внутренней
аппроксимации G1 :
x? (G1 ) = argmin{f (x), x ? G1 },
Qin (G1 ) = {x ? D : f (x) ? f (x? (G1 ))}.
Определение 2. Назовем ? -удовлетворительной внутренней аппроксимацией
допустимого множества для задачи (1) внутреннюю аппроксимацию G1 множества D , для которой Qin (G1 ) ? X?? .
Следующая теорема определяет необходимые и достаточные условия для того,
чтобы множество G1 являлось внутренней ? -удовлетворительной аппроксимацией
множества D задачи (1).
Теорема 1.
ной
Множество
G1 ? D
D
аппроксимацией множества
является внутренней
задачи
(1)
тогда
? -удовлетворитель-
и только
тогда,
когда
G1 ? X?? 6= ? .
Доказательство. Необходимость. Пусть G1 является внутренней ? -удовлетворительной аппроксимацией множества D для задачи (1). Согласно определению 2 Qin (G1 ) ? X?? . Для решения x? (G1 ) вспомогательной задачи (2) справедливы включения x? (G1 ) ? G1 , x? (G1 ) ? Qin (G1 ) . Отсюда, поскольку Qin (G1 ) ? X?? ,
следует, что x? (G1 ) ? G1 ? X?? , то есть G1 ? X?? 6= ? . Необходимость доказана.
Достаточность. Пусть G1 некоторая внутренняя аппроксимация множества D и имеет место G1 ? X?? 6= ? . Заиксируем произвольно точку y ? G1 ? X?? .
Так как y ? G1 , то f (x? (G1 )) ? f (y) , поскольку x? (G1 ) решение задачи (2).
С другой стороны, y ? X?? , что означает продолжение последнего неравенства:
f (x? (G1 )) ? f (y) ? f ? + ? . Таким образом, для любого x ? Qin (G1 ) будет справедлива цепочка неравенств f (x) ? f (x? (G1 )) ? f ? + ? , то есть Qin (G1 ) ? X?? .
Опишем общую схему использования ? -удовлетворительной внутренней аппроксимации при построении конечных алгоритмов решения задачи (1) точностью ? > 0 .
Пусть в качестве метода решения вспомогательной задачи (2) выбран некоторый метод внешней точки из класса методов последовательной безусловной минимизации (метод центров, метод штраных ункций или метод параметризации
целевой ункции). С помощью этих методов строится итерационная последовательность точек, не принадлежащих G1 , каждая из которых является точкой абсолютного минимума специальным образом построенной свертывающей ункции,
зависящей от целевой ункции и ункций-ограничений задачи (2).
УДОВЛЕТВОИТЕЛЬНАЯ АППОКСИМАЦИЯ. . .
193
Общая схема метода внешней точки с аппроксимацией допустимого
множества.
Пусть выбраны множество G1 ? -удовлетворительная внутренняя аппроксимация множества D , а также метод внешней точки A со свертывающей ункцией
F (x, f, ?(G1 ), ?) , где ?(G1 ) способ учета в свертывающей ункции допустимого множества (обычно задается в виде ункции-свертки ограничений), ? набор управляющих параметров метода внешней точки. Зададим способ выбора
управляющих параметров B , зависящий от выбранного метода внешней точки A .
Полагаем k = 0 .
Если получена точка xk ( k ? 0 ), то получение точки xk+1 производится следующим образом.
1. По способу B определяется очередной набор управляющих параметров ?k .
2. Строится ункция F (x, f, ?(G1 ), ?k ) , соответствующая методу A .
3. Выбирается xk+1 ? Argmin{F (x, f, ?(G1 ), ?k ), x ? Rn } .
4. Если xk+1 ? D , то xk+1 ? X?? . Останов. Задача (1) решена.
5. Полагается k = k + 1 . Переход к шагу 1.
В качестве метода A может быть выбран метод штраных ункций, метод
внешних центров или метод параметризации целевой ункции. Каждый из указанных методов имеет несколько разных способов задания свертывающей ункции
F (x, f, ?(G1 ), ?) и ункции ?(G1 ) и соответствующих им правил выбора новых
значений управляющих параметров ? (см., например, в [13?). Приведем далее
некоторые из них.
Метод штраных ункций. Управляющим параметром для метода штраных ункций является штраной коэициент ? > 0 . Традиционный способ выбора значений параметров (способ B общей схемы) для метода штраных ункций
заключается в следующем: ?k+1 > ?k ?k ? 0 , ?k ? ? при k ? ? . В качестве
свертывающих ункций метода штраных ункций при способе учета ограничений (?(G1 )) ?(x) = max{?i (x), i ? 1, . . . , r} можно использовать (q ? 1) :
F11 (x) = f (x) + ?(max{0, ?(x)})q ,
F21 (x)
= f (x) + ?
r
X
(max{0, ?i (x)})q .
i=1
Метод параметризации целевой ункции. Управляющий параметр дан-
ного метода ? связан со значениями целевой ункции в точках генерируемой последовательности. В большинстве методов параметризации целевой ункции в качестве способа иксации этого параметра (способ B общей схемы) используется
правило ?k+1 = ?k + min{F (x, f, ?(G1 ), ?k ), x ? Rn } при ?0 ? f ? . Для ускорения
процесса решения можно использовать еще один управляющий параметр ? > 0 ,
аналогичный штраному коэициенту.
В качестве примеров свертывающих ункций при способе учета ограничений
( ?(G1 ) ) ?(x) = max{?i (x), i ? 1, . . . , r} , которые используются в методе параметризации целевой ункции, можно привести следующие ( q ? 1 ):
F12 (x) = max{0, f (x) ? ?} + ? max({0, ?(x)})q ,
F22 (x) = max{0, f (x) ? ?} + ?
r
X
(max{0, ?i (x)})q .
i=1
Один из вариантов метода параметризации целевой ункции давно имеет собственное название метод центров и имеет следующую свертывающую ункцию:
F 3 (x) = max{f (x) ? ?, ??(x)}.
194
А.А. АНДИАНОВА
Докажем далее, что применение общей процедуры метода внешней точки с аппроксимацией допустимого множества позволит получить за конечное число итераций точку z ? X?? .
Теорема 2.
вия шага
4
Существует номер
K ? 0,
для которого будут выполнены усло-
общей схемы метода внешней точки с аппроксимацией допустимого
множества. При этом
xK+1 ? X?? .
Доказательство. Предположим, что для любого k ? 0 условия шага 4 не
выполняются. Исследуем свойства построенной по общей схеме последовательности точек {xk } . Согласно известным свойствам методов внешней точки (см.,
например, [1, 2, 11, 14? для различных методов последовательной безусловной минимизации) эта последовательность будет удовлетворять следующим условиям.
1) f (xk ) ? f (x? (G1 )) для всех k = 1, 2, . . . , причем f (xk ) ? f (x? (G1 )) при
k ? ?;
2) ?(xk , G1 ) ? 0 при k ? ? , где ?(x, G1 ) = min{ky ? xk, y ? G1 } расстояние
от точки x до множества G1 .
В силу условия 2, непрерывности ункций-ограничений ?i , i = 1, . . . , r , задачи (2) и условия Слейтера для множества D найдется номер K ? 0 такой, что
xK ? D , то есть будет получено противоречие с тем предположением, что условия
шага 4 общей схемы не выполняются. При этом в силу условия 1 будет справедливо
неравенство f (xK ) ? f (x? (G1 )) , то есть xK ? Qin (G1 ) , что согласно определению
? -удовлетворительной внутренней аппроксимации означает, что xK ? X?? .
3. Понятие ? -удовлетворительной внешней аппроксимации
допустимого множества
Определение 3. Внешней аппроксимацией множества допустимых решений D
задачи (1) назовем множество G2 вида {x ? Rn : ?i (x) ? 0, i = 1, . . . , r} , для
которого выполняется условие D ? G2 . Здесь ?i , i = 1, . . . , r , непрерывные в
Rn ункции, отличные от fi , i = 1, . . . , m , каждый локальный минимум которых
является абсолютным.
Вместо исходной задачи (1) будем решать следующую вспомогательную задачу
(3)
min{f (x), x ? G2 },
где G2 внешняя аппроксимация множества D задачи (1). Введем следующие
обозначения для точки минимума вспомогательной задачи (3) и множества ее ? решений:
x? (G2 ) = argmin{f (x), x ? G2 },
Qout (G2 ) = {x ? G2 : f (x) ? f (x? (G2 )) + ?}.
Определение 4. Назовем ? -удовлетворительной внешней аппроксимацией допустимого множества для задачи (1) внешнюю аппроксимацию G2 , для которой
?
Qout (G2 ) ? X ? .
Следующая теорема определяет необходимые и достаточные условия для того,
чтобы множество G2 являлось ? -удовлетворительной внешней аппроксимацией
множества D задачи (1).
Теорема 3.
Внешняя аппроксимация допустимого множества задачи
G2 = {x ? Rn : ?i (x) ? 0, i = 1, . . . , r} является ? -удовлетворительной
?
только тогда, когда Qout (G2 ) ? X? 6= ? .
(1)
тогда и
УДОВЛЕТВОИТЕЛЬНАЯ АППОКСИМАЦИЯ. . .
195
Доказательство. Необходимость. Пусть G2 ? -удовлетворительная внешняя аппроксимация множества D для задачи (1). Согласно определению 4
?
Qout (G2 ) ? X ? . Возьмем точку-оптимум задачи (1) x? ? Argmin{f (x), x ? D} .
Очевидно, что x? ? X?? . Для решения x? (G2 ) вспомогательной задачи (3) спра?
ведливо включение x? (G2 ) ? Qout (G2 ) , откуда следует, что x? (G2 ) ? X ? , так
как G2 ? -удовлетворительная внешняя аппроксимация множества D . Согласно
последнему включению справедливо неравенство |f (x? (G2 )) ? f (x? )| ? ? , или
f (x? ) ? f (x? (G2 )) + ? . Поскольку x? ? G2 , последнее неравенство означает, что
x? ? Qout (G2 ) . Таким образом, x? ? Qout (G2 ) ? X?? . Необходимость доказана.
Достаточность. Пусть G2 некоторая внешняя аппроксимация множества D
и Qout (G2 ) ? X?? 6= ? . Обозначим точку, входящую в это пересечение, через x . Так
как x ? X?? , имеет место неравенство f (x? ) ? f (x) , где x? ? Argmin{f (x), x ? D} .
Поскольку, кроме того, x ? Qout (G2 ) , получим, что
f (x? ) ? f (x) ? f (x? (G2 )) + ?.
(4)
Отсюда следует, что x? ? Qout (G2 ) .
Заиксируем произвольно точку y ? Qout (G2 ) . Для этой точки имеет место
неравенство f (x? (G2 )) ? f (y) ? f (x? (G2 )) + ? , что согласно (4) делает справедливой следующую цепочку неравенств: f (x? ) ? ? ? f (x? (G2 )) ? f (y) ? f (x? (G2 )) +
?
+ ? ? f (x? ) + ? , то есть |f (y) ? f (x? )| ? ? , или y ? X ? . В силу произвольности
?
выбора точки y ? Qout (G2 ) , последнее включение означает, что Qout (G2 ) ? X ? , то
есть согласно определению 4 множество G2 является ? -удовлетворительной внешней аппроксимацией множества D .
Замечание 1. Заметим, что исходное множество D задачи (1) является ? -удовлетворительной внутренней аппроксимацией для множества G2 . Действительно,
поскольку Qout (G2 ) представляет собой по определению множество ? -решений для
задачи (3), необходимое и достаточное условие из теоремы 1 в этом случае ормулируется как D ? Qout (G2 ) 6= ? . Поскольку G2 ? -удовлетворительная внешняя
аппроксимация множества D , то согласно теореме 3 Qout (G2 ) ? X?? 6= ? . Отсюда
с учетом X?? ? D , очевидно, D ? Qout (G2 ) 6= ? .
Сормулируем общую схему использования ? -удовлетворительной внешней аппроксимации при построении конечных алгоритмов решения задачи (1) точностью ? > 0 .
Пусть в качестве метода решения вспомогательной задачи (3) выбран некоторый метод внутренней точки из класса методов последовательной безусловной минимизации (метод центров, метод барьерных ункции). С помощью этих методов
строится итерационная последовательность точек, принадлежащих G2 , каждая из
которых является точкой абсолютного минимума специальным образом построенной свертывающей ункции, зависящей от целевой ункции и ункций-ограничений задачи (3).
Общая схема метода внутренней точки с аппроксимацией допустимого множества.
Пусть выбрано множество G2 ? -удовлетворительная внешняя аппроксимация
множества D , а также метод внутренней точки A со свертывающей ункцией
F (x, f, ?(G2 ), ?) , где ?(G2 ) способ учета в свертывающей ункции допустимого множества, ? набор управляющих параметров метода внутренней точки.
Зададим способ выбора управляющих параметров B , зависящий от выбранного
метода A . Полагаем k = 0 .
196
А.А. АНДИАНОВА
Если получена точка xk ( k ? 0 ), то получение точки xk+1 производится следующим образом.
1. По способу B определяется очередной набор управляющих параметров ?k .
2. Строится ункция F (x, f, ?(G2 ), ?k ) , соответствующая методу A .
3. Выбирается xk+1 ? Argmin{F (x, f, ?(G2 ), ?k ), x ? Rn } .
?
4. Если xk+1 ?
/ D , то xk+1 ? X ? . Останов.
5. Полагается k = k + 1 . Переход к шагу 1.
Обоснование работы общей схемы методов внутренней точки с аппроксимацией
множества допустимых решений основывается на свойствах, имеющих место для
всех методов внутренней точки (см., например, [13, 12?). В качестве метода A
могут быть использованы метод внутренних центров и метод барьерных ункций, для каждого из которых существует несколько видов свертывающей ункции
F (x, f, ?(G2 ), ?k ) с собственными способами задания управляющих параметров ?
(способ B общей схемы).
Теорема 4.
вия шага
4
Существует номер
K ? 0,
для которого будут выполнены усло-
общей схемы метода внутренней точки с аппроксимацией допусти-
мого множества. При этом
xK
будет является
? -псевдорешением
задачи
(1).
Доказательство. Предположим, что утверждение теоремы неверно, то есть
для всех k ? 0 условия шага 4 не выполняются. Исследуем свойства построенной
по общей схеме последовательности точек {xk } . Известно (см., например, [13, 12?),
что любой из методов внутренней точки генерирует последовательность так, что
f (xk ) ? f (x? (G2 )) для всех k = 1, 2, . . . , причем f (xk ) ? f (x? (G2 )) при k ? ? .
Так как абсолютный минимум f достигается за пределами множества D , f ? >
> f (x? (G2 )) . В силу непрерывности ункции f и согласно условиям изменения
последовательности {f (xk )} найдется номер K ? 0 такой, что f (xK ) < f ? , что
возможно только, если xK ?
/ D , то есть будет получено противоречие со сделанным
выше предположением.
При доказательстве теоремы 3 было показано, что x? ? Qout (G2 ) , если G2 ? -удовлетворительная внешняя аппроксимация множества D . Отсюда следует, что
для найденной точки xK справедливо неравенство f (xK ) ? f (x? ) ? f (x? (G2 )) +
+ ? , то есть xK ? Qout (G2 ) . Из определения 4 ? -удовлетворительной внешней
?
аппроксимации следует, что тогда xK ? X ? , то есть является ? -псевдорешением
задачи (1).
Замечание 2. В частных случаях использования некоторых видов свертывающей ункции и ? -удовлетворительной аппроксимации можно получить и ? -решение задачи (1) как последнюю точку, принадлежащую множеству D [6?. Например, это справедливо для свертывающей ункции метода центров, которая может
использоваться в методе как внешних, так и внутренних центров ( ? > 0 , ? управляющие параметры метода):
F (x) = max{f (x) ? ?, ??(x)}.
Замечание 3. Использование общей схемы метода внутренней точки с аппроксимацией допустимого множества в случае, когда в качестве метода A используется
метод барьерных ункций, имеет отличие на шаге 3 общей схемы, что связано с
отсутствием непрерывности барьерной ункции на границе множества G2 . Тем
не менее это не нарушает общности рассуждений при доказательстве теоремы 4.
Модиицированный шаг 3 имеет вид:
3? . Выбирается xk+1 ? Argmin{F (x, f, ?(G2 ), ?k ), x ? G2 } .
Виды свертывающих ункций, которые можно использовать в данном случае,
можно найти в [2, 3?.
УДОВЛЕТВОИТЕЛЬНАЯ АППОКСИМАЦИЯ. . .
197
4. Об одном способе задания ? -удовлетворительной
аппроксимации допустимого множества
Самым простым видом множества, которое можно использовать в качестве аппроксимации допустимого множества задачи (1), является
G(p) = {x ? Rn : fi (x) + p ? 0, i = 1, . . . , m}.
(5)
При p > 0 множество G(p) при условии непустоты будет внутренней аппроксимацией множества D , а при p < 0 внешней аппроксимацией. Очевидно, что
случай p = 0 рассматривать не надо, так как G(0) = D . Выбор значения параметра
аппроксимации p должен обеспечивать согласованность с желаемым уровнем точности ? > 0 . Следующая теорема указывают такой способ иксации параметра p .
Теорема 5.
(5) являлось ? -удовлетворительной
D , необходимо и достаточно, чтобы
g(x) = max{fi (x), i = 1, . . . , m} .
Для того чтобы множество
внутренней аппроксимацией множества
0 < p < ? min{g(x), x ? X?? } ,
где
Доказательство. Необходимость. Пусть G(p) ? -удовлетворительная внутренняя аппроксимация множества D . Тогда по теореме 1 G(p) ? X?? 6= ? . Заиксируем точку x из этого пересечения. Поскольку x ? G(p) , то g(x) + p ? 0 . Так
как x ? X?? , то min{g(x), x ? X?? } ? g(x) . Следовательно, min{g(x), x ? X?? } +
+ p ? g(x) + p ? 0 , или 0 < p < ? min{g(x), x ? X?? } . Необходимость доказана.
?
Достаточность. Пусть 0 < p < ? min{g(x), x ? X? } . Обозначим y =
?
?
= argmin{g(x), x ? X? } (это возможно, поскольку X? замкнутое ограниченное
множество). Для этой точки справедливо g(y) + p ? g(y) ? min{g(x), x ? X?? } = 0 .
Таким образом, y ? G(p) . Следовательно, y ? G(p)?X?? , а значит, в силу теоремы 1
G(p) ? -удовлетворительная внутренняя аппроксимация множества D .
Для практического определения значения параметра p должна быть известна
оценка сверху величины min{g(x), x ? X?? } . Такие оценки можно получить при
наложении дополнительных условий на целевую ункцию и ункции-ограничения
задачи (1). Перечислим некоторые известные способы получения таких оценок.
1. Пусть целевая ункция f выпукла и удовлетворяет условию Липшица с
константой L > 0 , ункция g , задающая ограничения, является сильно выпуклой
с постоянной сильной выпуклости µ > 0 , min{g(x), x ? X?? } =
6 min{g(x), x ? Rn } .
Тогда min{g(x), x ? X?? } ? ?µ?2 /L2 (см. [7?).
Отсюда следует, что G(p) является ? -удовлетворительной внутренней аппроксимацией множества D , если выполняется неравенство
0 < p ? µ?2 /L2 .
2. Пусть целевая ункция f выпукла и удовлетворяет условию Липшица с константой L > 0 , ункция g , задающая ограничения, является равномерно выпуклой
с неубывающим модулем выпуклости ?(t) ( 0 < t < ? ), min{g(x), x ? X?? } =
6
= min{g(x), x ? Rn } . Тогда min{g(x), x ? X?? } ? ??(?/L) .
Следовательно, чтобы G(p) являлось ? -удовлетворительной внутренней аппроксимацией множества D , требуется, чтобы
0 < p ? ?(?/L).
3. Пусть целевая ункция f выпукла и удовлетворяет условию Липшица
с константой L > 0 , ункция g , задающая ограничения, является (?, ?, ?) аппроксимируемой (см. [13?), min{g(x), x ? X?? } =
6 min{g(x), x ? Rn } . Тогда
min{g(x), x ? X?? } ? ???/L .
198
А.А. АНДИАНОВА
Следовательно, чтобы G(p) являлось ? -удовлетворительной внутренней аппроксимацией множества D , требуется, чтобы
0 < p ? ??/L.
Обоснуем получение такой оценки для более общего случая.
Лемма 1.
Пусть ункция
f
является явно квазивыпуклой и удовлетворяет
L > 0 , ункция g является сильно квазивыпук? > 0 , min{g(x), x ? X?? } =
6 min{g(x), x ? Rn } . Тогда
условию Липшица с константой
лой с постоянной
min{g(x), x ? X?? } ? ?
??2
.
4L2
(6)
Доказательство. Заиксируем две точки из множества X?? : x?
=
= argmin{f (x), x ? D} и y = argmin{g(x), x ? X?? } . Известно (см. [14?), что
4
для любого x ? X?? справедливо неравенство kx ? yk2 ? (g(x) ? g(y)) , в том
?
числе и для x? ? X?? . Так как точка минимума задачи (1) лежит на границе
множества D , то g(x? ) = 0 . Следовательно,
4
4
kx? ? yk2 ? ? g(y) = ? min{g(x), x ? X?? }.
?
?
(7)
Поскольку минимум ункции g на множестве X?? не совпадает с абсолютным минимумом этой ункции, он достигается на границе множества X?? , то есть f (y) =
= f ? + ? (см. [7?). Отсюда и из условия Липшица следует, что kx? ? yk ? ?/L , что
вместе с (7) приводит к неравенству min{g(x), x ? X?? } ? ???2 /4L2 .
Таким образом, при выполнении условий леммы 1 множество G(p) будет являться ? -удовлетворительной внутренней аппроксимацией допустимого множества D , если
??2
0<p?
.
4L2
Согласно замечанию 1 для множества D и его ? -удовлетворительной внешней
аппроксимации G справедливо утверждение о том, что D является ? -удовлетворительной внутренней аппроксимацией для G . Поэтому для множеств вида (5)
в случае их использования для построения ? -удовлетворительной внешней аппроксимации имеют место следующие оценки.
1. Пусть целевая ункция f выпукла и удовлетворяет условию Липшица с константой L > 0 , ункция g , задающая ограничения, является сильно выпуклой с
постоянной сильной выпуклости µ > 0 , min{g(x), x ? X?? } =
6 min{g(x), x ? Rn } .
Тогда G(p) является ? -удовлетворительной внешней аппроксимацией множества D , если
?µ?2 /L2 ? p < 0.
2. Пусть целевая ункция f выпукла и удовлетворяет условию Липшица с константой L > 0 , ункция g , задающая ограничения, является равномерно выпуклой с неубывающим модулем выпуклости ?(t) ( 0 < t < ? ), min{g(x), x ? X?? } =
6
6= min{g(x), x ? Rn } . Тогда G(p) является ? -удовлетворительной внешней аппроксимацией множества D , если
??(?/L) ? p < 0.
УДОВЛЕТВОИТЕЛЬНАЯ АППОКСИМАЦИЯ. . .
199
3. Пусть целевая ункция f выпукла и удовлетворяет условию Липшица с константой L > 0 , ункция g является (?, ?, ?) -аппроксимируемой, min{g(x), x ?
? X?? } =
6 min{g(x), x ? Rn } . В этом случае G(p) является ? -удовлетворительной
внешней аппроксимацией множества D , если
???/L ? p < 0.
4. Пусть ункция f является явно квазивыпуклой и удовлетворяет условию
Липшица с константой L > 0 , ункция g является сильно квазивыпуклой с постоянной ? > 0 , min{g(x), x ? X?? } =
6 min{g(x), x ? Rn } . Тогда G(p) является
? -удовлетворительной внешней аппроксимацией множества D , если
?
??2
? p < 0.
4L2
5. Описание вычислительных экспериментов
Экспериментальное исследование предложенного в статье подхода позволяет
говорить о его эективности. Проведенные вычислительные эксперименты для
метода центров и метода штраных ункций подтверждают акт получения решения с заданной точностью ? > 0 по ункционалу за конечное число процессов
минимизации свертывающих ункций, используемых в методах последовательной
безусловной минимизации.
Для иллюстрации сказанного приведем результаты решения известной задачи
озена Сузуки (см. [1?). Данная задача имеет ѕовражныйї характер, поэтому особенно интересна для исследований.
Задача озена Сузуки. Пусть x ? R4 , x = (?1 , ?2 , ?3 , ?4 ) . Требуется минимизировать ункцию
f (x) = ?12 + ?22 + 2?32 + ?42 ? 5?1 ? 5?2 ? 31?3 + 4?4
при ограничениях
f1 (x) = ?12 + ?22 + ?32 + ?42 + ?1 ? ?2 + ?3 ? ?4 ? 8 ? 0,
f2 (x) = ?12 + 2?22 + ?32 + 2?42 ? ?1 + ?4 ? 10 ? 0,
f3 (x) = 2?12 + ?22 + ?32 + 2?1 ? ?2 ? 5 ? 0.
В качестве контрольного значения оптимума целевой ункции принимаем
f ? = ?44.866164 (с точностью 10?7 ).
Далее приводятся результаты решения этой задачи с помощью нескольких алгоритмов в методе центров, которые относятся к методу как внешних, так и внутренних точек. Свертывающая ункция, построенная на k -й итерации метода, имела
вид:
Fk (x) = max{f (x) ? f (xk ), ?k g(x)}
где g(x) = max{fi (x), i = 1, . . . , m} , ?k > 0 аналог штраного коэициента.
Данная ункция может использоваться как для метода внешних точек (в случаях, когда x0 ?
/ D и f (x0 ) ? f ? ), так и для метода внутренних точек (в случае,
когда x0 ? D ). Эксперимент проводился с помощью ѕклассическихї реализаций
метода внутренних и внешних центров с эвристическими критериями остановки
вычислений |f (xk+1 ) ? f (xk )| ? ? , kxk+1 ? xk k ? ? , а также их модиикаций на
основании схем, предложенных в настоящей статье. Так как ункции-ограничения
задачи озена Сузуки являются сильно выпуклыми, применяемая в экспериментах аппроксимация допустимого множества имела вид (5) при 0 < p ? µ?2 /L2
200
А.А. АНДИАНОВА
Табл. 1
езультаты экспериментов
Алгоритм
Метод внутренних центров [12?
Метод внешних центров [11?
Метод внутренних центров с аппроксимацией допустимого множества
Метод внешних центров с аппроксимацией допустимого множества
Количество
итераций
27
17
Достигнутое
значение
?44.806136
?44.867226
Погрешность
11
?44.865591
0.000573
8
?44.866134
0.000030
0.060028
0.001062
(внутренняя аппроксимация) и ?µ?2 /L2 ? p < 0 (внешняя аппроксимация). Для
получения оценки параметра сильной выпуклости µ использовалась процедура
оценки с помощью собственных чисел гессианов ункций-ограничений. В качестве
константы Липшица использовалась ее выборочная оценка.
Процессы минимизации двух свертывающих ункций, построенных для решения одной и той же задачи, занимают примерно равное время, поэтому в качестве
критерия сравнения алгоритмов используется не время работы алгоритма, а проведенное количество процессов построения и минимизации свертывающей ункции
до выполнения условий критерия остановки вычислений и получения решения заданной точности.
Табл. 1 содержит результаты решения задачи озена Сузуки различными алгоритмами. Все вычисления проводились при ? = 10?3 . Для каждого алгоритма
представлены проведенное количество итераций (процессов минимизации свертывающих ункций), достигнутое значение целевой ункции и погрешность полученного решения по сравнению с контрольным значением.
Как видно из таблицы, при использовании ѕклассическихї алгоритмов с эвристическими критериями процесс вычислений останавливался, хотя заданная точность не была достигнута. Применение же алгоритмов с аппроксимацией допустимого множества позволило получить решения заданной точности. Следует отметить также, что количество выполненных процессов минимизации свертывающей
ункции в модиикациях с аппроксимацией множества меньше, чем при применении ѕклассическихї методов решения задачи. Эти выводы подтверждаются и
другими проведенными нами вычислительными экспериментами.
абота выполнена при инансовой поддержке ФФИ (проект ќ 12-01-97022,
12-01-31515).
Summary
A.A. Andrianova. Appliation of a Satisfatory Approximation of an Admissible Set for
Solving Optimization Problems.
This work deals with the properties and onstrution priniples of a satisfatory
approximation of a set of admissible solutions for a onditional optimization problem. The
replaement of an initial admissible set by its satisfatory approximation allows one to
onstrut nite algorithms for the methods of internal and external points (methods of
penalty funtions or methods of enters) with the stopping riterion whih ensures the required
auray of the solution. Neessary and suient onditions for produing external and internal
satisfatory approximations of an admissible set are proved. One of the feasible ways for setting
a satisfatory approximation of an admissible set is formulated. This way an be used for the
development of algorithms that ensure the required auray in a nite number of iterations.
УДОВЛЕТВОИТЕЛЬНАЯ АППОКСИМАЦИЯ. . .
201
Key words: methods of sequential unonstrained minimization, penalty funtion method,
method of enters, solution of an optimization problem with a given auray, satisfatory
approximation of an admissible set, feasible stopping riteria.
Литература
1.
россман К., Каплан А.А.
2.
Евтушенко Ю.., Жадан В..
3.
4.
5.
Нелинейное программирование на основе безусловной минимищации. Новосибирск: Наука, 1981. 183 .
К вопросу о систематизации численных методов нелинейного программирования. М.: ВЦ АН ССС, 1988. 66 с.
Жадан В.. Численные методы линейного и нелинейного программирования. Вспомогательные ункции в условной минимизации. М.: ВЦ им. А.А. Дородницына
АН, 2002. 160 с.
Об одной модиикации метода сдвига штраов для задач нелинейного программирования // Изв. вузов. Матем. 2000. ќ 12. С. 4954.
Заботин Я.И., Фукин И.А.
Заботин Я.И., Фукин И.А. Алгоритмы в методе штраов с аппроксимацией допустимого множества // Изв. вузов. Матем. 2004. ќ 1. С. 3647.
6.
Заботин Я.И., Андрианова А.А.
7.
Андрианова А.А., Заботин Я.И.
8.
Андрианова А.А.
9.
10.
Алгоритмы в методе центров с аппроксимацией
допустимого множества // Изв. вузов. Матем. 2001. ќ 12. С. 4145.
Управление процессом минимизации в параметризованном методе центров // Изв. вузов. Матем. 2002. ќ 12. С. 310.
Параметризация метода центров для минимизации явно квазивыпуклых ункций // Исследования по прикладной математике и инорматике. Казань: Изд-во Казан. матем. о-ва, 2006. Вып. 26. С. 312.
Принципы построения аппроксимации допустимого множества при
решении задач условной оптимизации с заданной точностью // Труды XV Байкальской междунар. школы-семинара ѕМетоды оптимизации и их приложенияї. Т. 2. Математическое программирование. Иркутск: ИО ИДСТУ СО АН, 2011. С. 3538.
Андрианова А.А.
Сухарев А.., Тимохов А.В., Федоров В.В.
Курс методов оптимизации. М.: ФИЗ-
МАТЛИТ, 2005. 368 с.
11.
Алгоритмы с комбинированием, параметризацией и
двусторонним приближением в методе центров // Изв. вузов. Матем. 1998. ќ 12. С. 4048.
Заботин Я.И., Даньшин И.Н.
12.
Заботин Я.И.
Минимаксный метод решения задачи математического программирования // Изв. вузов. Матем. 1975. ќ 6. С. 3643.
13.
Фукин И.А.
14.
Кораблев А.И.
? -аппроксимируемость выпуклых ункций // Алгоритмический анализ
неустойчивых задач: Тез. докл. Всерос. кон., Екатеринбург, 26 евр. 2004 г. Екатеринбург: Изд-во Урал. ун-та, 2004. С. 306307.
О релаксационных методах минимизации псевдовыпуклых ункций // Исследование по прикладной математике. Казань: Изд-во Казан. ун-та,
1980. С. 38.
Поступила в редакцию
07.06.12
Андрианова Анастасия Александровна кандидат изико-математических
наук, доцент каедры системного анализа и инормационных технологий Казанского
(Приволжского) едерального университета.
E-mail: Anastasiya.Andrianovaksu.ru
Документ
Категория
Без категории
Просмотров
5
Размер файла
229 Кб
Теги
решение, оптимизация, допустимое, множества, применению, задачи, удовлетворительному, аппроксимация
1/--страниц
Пожаловаться на содержимое документа