ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 12, с. 2037-2054
УДК 519.658
НОВЫЕ ВАРИАНТЫ ОБОБЩЕННОГО МЕТОДА УРОВНЕЙ ДЛЯ МИНИМИЗАЦИИ ВЫПУКЛОЙ НЕДИФФЕРЕНЦИРУЕМОЙ
ФУНКЦИИ, НЕ ВСЕ ЗНАЧЕНИЯ КОТОРОЙ КОНЕЧНЫ1)
© 2007 г. Н. Ä. Соколов
(117418 Москва, Нахимовский пр-т, 47, ЦЭМИ РАН) e-mail: sokolov@cemi.rssi.ru Поступила в редакцию 03.05.2007 г.
Предлагается ряд вариантов обобщенного метода уровней для минимизации выпуклой лип-шицевой функции на имеющем непустую внутренность компакте, включающих ранее известные обобщенные и классические методы уровней для минимизации. Установлена оценка скорости сходимости для предложенных вариантов метода, в том числе для вариантов, в которых вспомогательные задачи решаются приближенно. Библ. 5.
Ключевые слова: выпуклая функция, минимизация недифференцируемой функции, метод уровней.
1. ОПИСАНИЕ ОБОБЩЕННОГО МЕТОДА УРОВНЕЙ И ЕГО ОСНОВНЫХ МОДИФИКАЦИЙ
Пусть f - выпуклая, вообще говоря, недифференцируемая функция, определенная на выпуклом многограннике G с Е конечными значениями либо значениями, равными где Е - некоторое конечномерное пространство. Введем множество G = domf = {x е G: f (x) < и будем предполагать, что выпуклое множество G непусто и содержит внутренние точки. В дальнейшем также предполагается, что G - замкнутое множество, а функция f является липшицевой на G, т.е. существует такое число L (постоянная Липшица), что |f (x') - f (x")| =s L||x' - x" || для любой пары точек x', x", принадлежащих G. Из сделанных предположений вытекает, что функция f субдиф-
ференцируема в любой точке множества G. При этом если через df(x) обозначить субдифференциал f в точке x, а под l(x) с df (x) понимать некоторый элемент df (x) (его называют субградиентом f в точке x), то для x е intG любой элемент df (x) имеет норму, не превышающую L, а при x е G\intG существует такой субградиент l(x), что ||l(x)|| =ё L.
Предметом данной работы является предложение нового варианта обобщенного метода минимизации f на G (см. [1], [2]), разработанного для случая, когда G, вообще говоря, не совпадает с многогранником G, т.е. когда в некоторых точках G функция f принимает значение, равное
Начнем с описания основной версии обобщенного метода минимизации (см. [1]). Согласно алгоритму, в процессе минимизации функции f на G строится последовательность точек xi е G, i =
= 1, 2, ..., где в качестве начальной точки x1 принимается любая точка из G. Если xi е G, то предполагаются известными f (xi) и некоторый субградиент l(xi) е df (xi). Если же xi й G, то считается,
что нам известна гиперплоскость, отделяющая точку xi от множества G, т.е. мы располагаем такими вектором ai = ai(xi) е Е (в основной версии ||ai|| = 1) и числом ai = ai(xi) > 0, что
max<at(xt), x - x^ + a(xt) ^ 0.
x е G
Многогранник G задается аналитически в виде системы линейных неравенств, а множество G и функция f(x), вообще говоря, задаются неявно с помощью специального алгоритма, называемого
Работа выполнена при финансовой поддержке РФФИ (код проекта 05-01-00491).
2037
2038
соколов
оракулом. Оракул выдает информацию о том, принадлежит ли x, множеству G или нет, а также субградиент и значение функции в точке x, е G либо отсекающую гиперплоскость при x, й G.
Пустьf* = minx е g/ (x) - минимальное значение исходной задачи,X* = {x* е G:f(x*) = f*} - (непустое) множество ее решений, а f * = min1 s j s kf (x,) - рекорд по минимизируемой функцииf полученный на k точках x1, ..., xk (вначале этот рекорд полагается равным
Далее, пусть для k = 1, 2, ... множество Ik = {1, 2, ..., k} разбито на два подмножества по признаку: попали ли точки x1, ..., xkв множество G или нет:
Ik = {1 ^ i ^ k: x, е G}, Ik = { 1 ^ i ^ k: x, й G}.
Допустим, что уже найдено k (k > 1) точек x, е G. С каждой точкой x,, 1 =s i =s k, связывается неравенство
<bi, x - x,) + ßlk ^ 0,
где
Г/(хг), i е Гк, j0, г е Гк,
b = 1 ( ) ■ г" вк = в = 1 ( ) ■ г" (1)
[aг(Хг), г е Ik, [аг(x,), г е Ik.
Эти неравенства и исходный многогранник G порождают многогранник Qk:
Qk = {x е G: <bt, x - xt) + вгк ^ 0, 1 ^ i ^ к}.
Многогранник Qk не является пустым множеством, так как содержит все точки x е G, для которых f(x) ^ f * .
Поиск точки xk + 1 е G начинается с решения задачи линейного программирования, имеющей вид
t —► max,
<b, x- x,> + p,.k +1 ^ о, г = 1,2,..., k, (dk)
x е G,
неизвестными которой являются вектор x и число t. В силу непустоты множества Qk, максимальное значение линейной формы задачи dk (обозначим его через Ak) неотрицательно. Заметим, что в силу своего определения числа Ak не возрастают с ростом k.
Поиск последовательности {xг} в обобщенном методе уровней зависит от параметра X, который может быть выбран произвольным образом из интервала (0, 1) (например, в качестве X можно взять 1/2). Рассмотрим многогранник Qk(X), задаваемый условиями
Qk(X) = {x е G: <bv x - x,> + p,* + XAk ^ 0, г = 1, 2,., k}.
Заметим, что Qk(0) = Qk, а Qk(1) с Qk(X) при любом X ^ 1. Из этого включения вытекает непустота многогранника Qk(X).
В качестве точки xk + 1 принимается проекция точки xk на многогранник Qk(X). Поиск этой проекции связан с решением задачи квадратичного программирования
||x - xJI2 —»- min, x е Qk(X). (^k)
Итак, отдельная итерация алгоритма, связанная с вычислением очередной точки xk + 1 е G, сводится к решению одной задачи линейного программирования и одной задачи квадратичного программирования (задачи dk и ^k).
В [1], [2] рассмотрено также несколько модификаций обобщенного метода уровней.
1. Метод уровней с глубокими отсечениями, в котором вместо формул (1) используется другая формула для пересчета коэффициента вг (а формула для пересчета Ь i не меняется):
[I(хг), г е 4 Г/(хг) - /*, г е II
Ь1 = 1 ( ) ■ т" вк = 1 ( ) ■
[а,(хг), г е 4, [а,(х,), г е 1к.
Использование этого метода основано на следующих соображениях. Если г е Гк, то {!(хг), х -- хг} ^ 0 и отсекаются все точки х е G, для которых/(х) > </(xi), х - хг} + /(xi) >/(хг) > /* . Итак, нас будут интересовать лишь точки, для которых {!(хг), х - хг} + /{xj) - /* 0. Отсечение будет глубоким для тех г е Гк, для которых/(хг) > /* . Числа вк > 0 и монотонно не убывают по к.
В [1] показано, что в случае G = G данный вариант обобщенного метода уровней совпадает с классическим методом уровней (см. [3], [4]).
2. Нормированный метод уровней, в котором вместо первой формулы в (1) для пересчета используется другая формула (а формула для в не меняется):
I (хг)
Ьг =
III(х- )|| , 1 е 4 в-к = в- = | ^ 1е Ik, ,,
а-(хг), г е 1к, [а(х), 1 е 1к.
В этом варианте метода и вектор 1(хг), и вектор аг (хг) одинаково нормированны, так как для всех г е 1к = {1, 2, ..., к} справедливо ||Ьг|| = 1. Предполагается, что ||/(хг)|| ф 0 для всех 1 е Гк, так как в противном случае 1(хг *) = 0 для некоторого 1 * и, следовательно, /(хг*) = /*.
3. Можно рассмотреть также третью модификацию метода уровней - нормированный метод уровней с глубокими отсечениями:
/ (х1) - /*
Ьг =
1( хг) т,
- 1 е 1к,
т'
г е 1к,
( хг )|| ' Ь
а(х1), 1 е Гк.
II1 ( х- Ж к вгк =
аг(х1), 1 е Гк,
В [1] получены оценки скорости сходимости предложенных четырех алгоритмов (они имеют порядок 0(к1/2)) для случая, когда множество G замкнуто и имеет непустую внутренность.
Далее будет рассмотрен новый вариант обобщенного метода уровней, причем описанные выше алгоритмы являются его частными случаями. Обобщение производится в нескольких направлениях: параметризация "глубины отсечения"; произвольное нормирование векторов 1(хг) и аг(хг); вместо одного, постоянного для всех итераций алгоритма числа X используется набор, вообще говоря, различных чисел , 1 = 1, 2, ...; разрешено добавлять на каждой итерации несколько линейных ограничений; вместо единичной матрицы в задаче квадратичного программирования используется произвольная симметричная положительно-определенная матрица; вспомогательные задачи линейного и квадратичного программирования решаются приближенно.
2. ОБЩАЯ СХЕМА МЕТОДА УРОВНЕЙ
Метод уровней можно применять к различным задачам (минимизация, поиск седловых точек, решение вариационных неравенств и т.д.). Ко всем этим задачам применим общую вычислительную схему метода, которую опишем, определив вначале оракул.
Пусть имеется многогранник Q с Е (Е - конечномерное пространство), содержащий некоторый непустой выпуклый компакт Q* (например, точку). Нашей целью является нахождение какой-нибудь точки из Q* либо приближение к множеству Q* с некоторой точностью. Каждой точке г е Q приписано непустое множество ответов (откликов) оракула В(г) = {(Ь(г), в(г))}, ответом оракула считается пара (Ь(г), в(г)), где Ь(г) - вектор, в(г) > 0 - число. Множество В(г) содержит набор Ь(г) = 0, в(г) = 0 лишь для точек г е 2*. Для остальных наборов ||Ь(г)|| ф 0 и каждое полупространство точек у е Е, для которых выполнено неравенство
<Ь(г), у - г} + в(г) ^ 0, (2)
содержит множество Q*.
2040
соколов
В описываемом методе уровней при z е Q\Q* оракул выдает один или несколько наборов векторов b = b(z), ||b(z)|| Ф 0, и неотрицательных чисел ß = ß(z), (b, ß) е B(z), таких, что для каждого набора выполнено (2), если же оракул определяет b(z) = 0 и ß(z) = 0 для некоторой точки z е Q, то заведомо z е Q*.
Опишем вариант обобщенного метода уровней, использующий введенный оракул. Зададим множества S0 = 0, Л0 = 0, Q0 = Q и число n0 = 0. Выберем положительно определенную симметричную матрицу H и произвольную точку z1 е Q.
Пусть уже построено к (k > 1) точек z, е Q, i = 1, 2, ..., k, определено множество Sk- 1, |Sk _ 1| = = nk- 1. С точкой zk свяжем mk (mk > 1) откликов оракула, т.е. зададим mk наборов векторов bj = = bj(zk) и чисел ßj, k = ßj, k(zk) > 0, j е Jk = {nk _ 1 + 1, ..., nk- 1 + mk}, и для каждого набора выполняется условие (2). Положим Sk = Sk- 1 u Jk, где Jk| = mk, |Sk| = nk = nk- 1 + mk. Далее будем предполагать, что ||bj || Ф 0 для всех j е Jk (иначе - точка zk е Q*).
Будем предполагать также, что многогранник Qk вида
Qk = {z е Q: <b, z - z,) + ß;,k ^ 0, j е J, i = 1, 2,..., k},
где числа ßj, k > ßj, k - 1 для всех j е J, i = 1, 2, ..., k - 1, я
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.