ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2007, том 43, № 3, с. 127-132
МЕТОДЫ ОПТИМИЗАЦИИ
СЕДЛОВОЙ МЕТОД,
__V &
ИСПОЛЬЗУЮЩИЙ НЕТОЧНЫЕ ИСХОДНЫЕ ДАННЫЕ
© 2007 г. Е. Г. Гольштейн
(Москва)
Описан метод оракульного типа отыскания седловой точки выпукло-вогнутой липшицевой функции при наличии ошибок в откликах оракула. Установлены требования к ошибкам оракула. При соблюдении этих требований метод позволяет найти е-седловую точку исследуемой функции при фиксированном е > 0. Получена оценка сверху для числа итераций, необходимых для вычисления е-седловой точки.
1. ВВЕДЕНИЕ
В работе (Бэр, Гольштейн, Соколов, 2001) был предложен итеративный метод отыскания седловой точки выпукло-вогнутой функции, эффективное множество которой содержится в многограннике. Предполагалось, что исследуемая функция задается с помощью некоторого вспомогательного алгоритма - оракула. При каждом обращении к оракулу вычисляется определенная локальная характеристика функции, которая используется в процессе поиска седловой точки. Анализ сходимости метода, содержащийся в (Бэр, Гольштейн, Соколов, 2001), опирался на допущение о том, что все отклики оракула не содержат ошибок. Вместе с тем, во многих случаях оракул, являясь численным алгоритмом, работает с ошибками, величина которых зависит от времени использования соответствующего алгоритма. Исследуем поведение метода отыскания седловой точки функции, локальные характеристики которой содержат ошибки. Начнем с необходимых обозначений.
Пусть Gx и G - выпуклые компакты, расположенные в конечномерных евклидовых пространствах Ex и E , соответственно, и имеющие непустые внутренности, G = Gx х Gy; Mx с Ex и My с Ey - выпуклые многогранники, содержащие, соответственно, Gx и Gy, M=Mx хMy. Рассмотрим функцию f(z) = fx, y), z = (x, y), определенную конечными значениями на G с M и являющуюся выпукло-вогнутой на G, т.е. выпуклой относительно x е Gx при любом фиксированномy е Gy и вогнутой относительно y е Gy при любом фиксированном x е Gx. Кроме того, допустим, что функция f удовлетворяет на G условию Липшица с постоянной L.
Сделанные предположения обеспечивают наличие у функции f седловой точки и субдиффе-ренцируемость (супердифференцируемость) функции f по x(y) в каждой точке z0 = (x0,y0) е G, т.е. непустоту субдифференциала df(x0, y0) (супердифференциала df(x0, y0)) функции f в точке (x0, y0) относительно x(y). При этом, если z0 е intG, lx е df(x0,y0), ly е df(x0,y0), то (||4||2 + ||ly||2)1/2 - L.
Выпукло-вогнутая функция f задается при помощи некоторого вспомогательного алгоритма (оракула). Действие оракула состоит в следующем. Для произвольной точки z0 е M он, прежде всего, выясняет, принадлежит ли данная точка внутренности множества G. Если z0 е int G, то оракул вычисляет приближенное значение lx некоторого субградиента lx е df(z0) и приближенное
значение ly некоторого суперградиента ly е dyf(z°). Если же z0 й intG, то оракул находит с некоторой ошибкой гиперплоскость, проходящую через точку z0 и содержащую множество G в своем нижнем полупространстве, т.е. приближенное значение а, ||а || = 1 такого единичного вектора а, что maxz е G(a, z - z0) - 0.
Проанализируем сходимость итеративного метода, описанного в (Бэр, Гольштейн, Соколов, 2001) для случая, когда используются приближенные отклики оракула (lx, ly, а).
* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 05-0100491).
2. ОПИСАНИЕ МЕТОДА
Метод отыскания седловой точки выпукло-вогнутой функции f на множестве G зависит от параметра X, выбираемого из интервала (0, 1), и реализуется в виде серии однотипных итераций. Перед началом итерации к >2 считаются известными уже найденные точки zt е М, 1 < i < к - 1, причем за zx может быть принята любая точка многогранника М. На каждой итерации метода (исключая, быть может, последнюю итерацию) происходит одно обращение к оракулу. В результате, если точка zi е intG, то оракул выдает приближенное значение li = (lix - liy) вектора l = (lix, -liy), где lix е df(z), liy е df(z), причем ||li - l,-|| < 5. Если же zi g intG, то оракул выдает приближенное значение ai, || ai || = 1, единичного вектора ai, удовлетворяющего условию maxz е G<ai, z - z> < 0, причем || ai - аг|| < 5. Неотрицательное число 5 определяет гарантированную точность работы оракула.
Разобьем множество 1(к) = {1, ..., к - 1} номеров итераций, предшествующих итерации к, на два непересекающихся подмножества I1(k) и 12(к), положив
I1 (к) = {i е I( к): zt е intG }, I2 (к) = {i е I( к): zt g intG }.
Используя информацию, накопленную до начала итерации к, введем задачу линейного программирования йк с переменными z и t:
t —max,
<li, zi - z>> nit, i е Ii(к), (1)
<ai, zt - z>> t, i е I2(к), z е M,
где ni = ||" ||.
Итерация к начинается с решения задачи йк и двойственной задачи ¿йк. Пусть Дк - максимальное значение линейной формы задачи йк (ниже будет показана положительность этого числа),
а > 0, i е I(к) - компоненты оптимального плана задачи ¿йк.
Если е I (к) > 0 и при этом Дк < ех, где положительное число ех выбирается заранее, то итерация к заканчивается и является последней, а в качестве приближенного значения искомой седловой точки принимается точка z* = ^ е I (к) zjе г (к) . В противном случае итерация к продолжается.
Введем в пространстве Ez = Ex х Ey выпуклый многогранник Mk(t), определяемый ограничениями задачи (1) на переменную z при фиксированном значении t < Дк. Дальнейшее течение итерации к связано с построением очередной точки zk, в качестве которой принимается решение задачи квадратичного программирования
||z - Zk2 —► min, z е М^Дк), (2)
где X е (0, 1) - параметр метода. Таким образом, zk является проекцией точки zk - 1 на многогранник Мк(ХДк). После отыскания zk происходит обращение к оракулу. Если zk е int G и сообщенный
оракулом вектор lk удовлетворяет условию nк = ||lk || < е2, где положительное число е2 выбирается заранее, то итерация к является последней, а в качестве приближенного значения седловой точки принимается точка z* = zk. В противном случае осуществляется переход к итерации к + 1.
3. АНАЛИЗ МЕТОДА
Близость произвольной точки z = (x, y) е G к седловому множеству Z* функции f (z) на множестве G будем оценивать, как и в (Бэр, Гольштейн, Соколов, 2001), неотрицательной величиной
Д(z) = max [f(x, y) - f(x', y)], (3)
z' = (x', y) е G
СЕДЛОВОЙ МЕТОД, ИСПОЛЬЗУЮЩИЙ НЕТОЧНЫЕ ДАННЫЕ 129
которая обнуляется лишь в точках Z*. Мера близости (3) является обобщением оценки по функционалу, используемой в задачах оптимизации.
Прежде чем приступить к обоснованию сходимости метода, описанного в разд. 2, убедимся в положительности Ak - максимального значения линейной формы задачи (1) при любом к > 2. Очевидно, что для этого достаточно установить непустоту внутренности многогранника Mk(0), определяемого системой ограничений задачи (1) при t = 0. Последнее можно доказать, используя индукцию по к. Действительно, непустота intM2(0) вытекает из того, что intG Ф 0. Если допустить непустоту Mk(0), то Дк > 0 и, следовательно, Mk(kAk) с intMk(0), а значит, точка zk, являясь проекцией точки zk - 1 на Mk(kДk), оказывается внутренней точкой многогранника Mk(0). Многогранник Mk + х(0) представляет собой пересечение Mk(0) и полупространства, граничная гиперплоскость которого проходит через точку zk. Поэтому непустота intMk + х(0) - следствие того, что intMk(0) Ф 0, а zk е intMk(ö).
Анализ описанного в разд. 2 метода начнем с оценки близости точки z* , вырабатываемой методом на итерации k, в зависимости от максимального значения Дк линейной формы задачи ük и величины 5 > 0, характеризующей точность работы оракула.
Лемма 1. Предположим, что множество G содержит шар радиуса r > 0. Если d - диаметр многогранника M, а величины Дk и 5 настолько малы, что
Дk + d 5 < r, (4)
то множество I1(k) Ф 0 и X, е I (k) I > 0, причем
Д( z*)<(L +1 )(Д k + d 5)d/r, (5)
где z* = X, е I (k) I z/ X, е I (k) I, L - постоянная Липшица функции f.
Доказательство. Если, как ранее было отмечено, I > 0, i е I(k), - компоненты оптимального плана задачи ¿й k, то из теории линейного программирования следует, что, во-первых,
X ni Ii + X Ii = (6)
i е I1(k) i е I2(k)
а во-вторых, при любом z е M
Fk(z) = X Ii <Ii' zi - z) + X Ii < аi, zi - z>^. (7)
i е I1 (k) i е I2(k)
Введем множество G(a), состоящее из точек, содержащихся в G вместе со своей а-окрест-ностью, а > 0. В силу предположений леммы 1, множество G(a) Ф 0 при любом а < r. Если точка z' е G(a), 0 < а < r, то (а, z, - z'> > а, i е I2(k), где ||а, - аi || < 5. Следовательно,
< а, zt - z'> > а - d5, i е 12 (k), (8)
для любой точки z' е G^). Из (6)-(8) вытекает, что неравенство
X Ii<Ii, zi - z'><Дk - (1- Yk)(а - d5) (9)
i е I1(k)
верно для любой точки z' е G^), 0 < а < r, где yk = X, е I (k) n I;.
Пусть z0 - центр шара радиуса r, содержащегося в G. Тогда из (9) при а = r с учетом условия (4) получаем
X Ii <Ii, zi - z0> < yk(r - d5). (10)
i е I1(k)
Если допустить, что Xi е I (k) Ii- = 0, то Yk = 0 и неравенство (10) неверно. Следовательно, требование (4) влечет за собой положительность X, е I (k) и, в частности, непустоту множества Ii(k).
Применим теперь (9) для а = Дк + d5. Тогда получаем, что для любой точки z' е G^k + d5) имеет место неравенство
£ ц, <~!ь z, - z')<yкДк. (11)
i е Zi(k)
Вектор l, является приближенным значением вектора lt = (lix, -liy), где lix е df(z,), liy е df(z), причем
||/г - lj| <5, i е 11(к), (12)
поэтому n, = || l, || < ||1,|| + 5 < L + 5. Учитывая это и неравенство (11), имеем
£ ц, <l, z, - z'>/ £ ц, <(L + 5)Дк (13)
i е /1( к) i е /1( к)
для любой точки z' е G(Дk + d5). Из (12) и (13) вытекает, что
£ ц,(<lix, x, - x'> - <liy, у, - y'>)/ £ ц, < (L + 5)Дк + d5, (14)
i е I1 (к) i е I1 (к)
если z' = (x', y') е G(Дk + d5).
Установим оценку сверху для левой части (14) при любом z' е G. Пусть z е G, z0 - центр шара радиуса r, содержащегося в G. Как нетрудно проверить, точка z' = z(1 - (Дк + d5)/r) + z0(Дk + d5)/r е е G(Дk + d5). Следовательно, для нее справедлива оценка (14). Но z' - z = ((Дк + d5)/r)(z0 - z), поэтому
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.