Читать онлайн «Фейеровские процессы: синтез и рандомизация»

ТРУДЫ И Н С Т И Т У Т А МАТЕМАТИКИ И М Е Х А Н И К И УрО РАН Том 10 № 2 2004 УДК 519. 6 1 ФЕЙЕРОВСКИЕ ПРОЦЕССЫ: СИНТЕЗ И Р А Н Д О М И З А Ц И Я И . И . Еремин Рассматриваются итерационные процессы фейеровского типа, сходящиеся к одной из неподвижных то­ чек фейеровского оператора. Предложен метод синтеза оператора по системе фейеровских отображений с различными пространствами их образов. Такой прием позволяет повысить эффективность итерационных методов для сильно структурированных систем линейных и выпуклых неравенств. Рассмотрены также варианты рандомизированных процессов, порождаемых вероятностными фейеровскнми отображениями. 1. Введение Пусть X — линейное нормированное пространство и М — некоторое множество из X. В 60-х годах [1-4] автор ввел понятие (и сам термин) М-фейеровского отображения Т Е {X —> X}, как оператора, обладающего свойствами: Т(у) = у, \\Т(х) - у\\ < \\х - у\\, УуЕМ, Vx<£M. (1. 1) Использование таких операторов связано, в первую очередь, с решением систем линейных и выпуклых неравенств, а также задач линейного и выпуклого программирования. В качестве множества М в этих случаях выступает множество решений системы неравенств или опти­ мальное множество (Arg) оптимизационной задачи. Истоками исследований по применению процедур фейеровского типа для решения систем линейных неравенств послужили работы [5,6]. Простейшим примером М-фейеровского отображения является оператор метрического проектирования Р г (х) на выпуклое замкнутое множество М гильбертова пространства Н. м Приведем еще один пример. Пусть М :— {х | lj{x) := (a,j, х) — bj < 0, j = 1 , . . . , m} ф 0 , d(x) : = m a x / j ( x ) , J(x) := {j \ d(x) = lj{x)}. U) a \\ j II x + где 0 < Л < 2, d (x) = max{0,d(x)}, а индексу j E J(x) можно тем или иным спосо­ x бом придать однозначность, взяв, например, в качестве j наименьший j Е J[x). Отображе­ x ние (1. 2) удовлетворяет соотношениям (1. 1). Сразу же отметим, что при произвольном на­ чальном хо G Н процесс, порожденный рекуррентным соотношением х^+\ = L(xk), будет сходиться к решению системы линейных неравенств, задающей множество М. Отображения типа (1. 2) можно построить как для счетных систем линейных и выпуклых неравенств, так и для континуальных [7]. Основные два вопроса, рассматриваемые в настоящей работе, суть: (1) синтез фейеровских отображений по конечной совокупности частных отображений с раз­ ными пространствами их образов; х Работа выполнена при финансовой поддержке программы НШ-792. 2003. 1 и Российского Фонда Фундаментальных Исследований, коды проектов 04-01-00108, 03-01-00565.