Геометрические свойства и численные методы нелинейной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ

На правах рукописи

РОДИОНОВ Алексей Вадимович

УДК 519.6

ГЕОМЕТРИЧЕСКИЕ СВОЙСТВА И ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОЙ ОПТИМИЗАЦИИ

01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1993

Работа выполнена в Институте проблем кибернетики Российской Академии наук.

Научный руководитель

Официальные оппоненты-

Ведущая организация -

доктор физико-математических, наук, профессор В.Г.Карманов

доктор физико-математических наук Ю.А.Флеров

кандидат физико-математических наук Т.Д.Березнева Московский Государственный Университет им. М.В.Ломоносова

Защита диссертации состоится "_"_1993 г.

в _ час. _ мин. на заседании Специализированного Совета

К 003.78.01 при Институте проблем кибернетики РАН по адресу: 117312, Москва, ул.Вавилова, 37.

С диссертацией можно ознакомиться в библиотеке Института

Автореферат разослан 1993 г.

Ученый секретарь Специализированного Совета к.ф.-м.н.

А.З.Ишмухаметов

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. К настоящему времени теория и практика решения задач оптимизации достигли весьма ощутимых успехов и продолжают быстро развиваться. Например, сейчас интенсивно разрабатывается область параллельных методов оптимизации в связи с широким внедрением суперЭВМ. В частности, наблюдается повышенный интерес к многошаговым методам, адаптированным к векторно-конвейерным суперЭВМ, эффективность работы которых существенно зависит от степени загруженности всех функциональных устройств. В этих методах на каждой итерации используются направления движения на предыдущих итерациях. Все эти направления можно сохранять на векторных регистрах и использовать в векторных операциях, улучшая загруженность суперЭВМ. В диссертации исследован метод "тяжелого шарика".

С другой стороны, нет еще полного понимания поведения даже простейших методов как конечномерной оптимизации (градиентного, штрафных функций и др.), так и бесконечномерной (отказ от использования неустойчивых разностных схем - решение линейных уравнений в бесконечномерном пространстве можно рассматривать как задачу оптимизации). Например, считалось, что типичная траектория градиентного метода при минимизации "овражной" функции представляет собой "пилу", т.е. точки минимизирующей последовательности перескакивают со "склона" на "склон". Это верно для метода скорейшего спуска. Однако, в диссертации показано, что минимизирующая последовательность, построенная градиентным методом с постоянным шагом определенной длины, по крайней мере для квадратичных сильно выпуклых функций, не покидает тот ортант (в системе координат из собственных векторов с началом в точке решения), в котором находилась начальная точка. Кроме того, антиградиент функции в точках такой последовательности стабилизируется своим направлением на точку минимума. Эти свойства важны и для теории, так как позволяют получать новые результаты, и для практики, так как служат обоснованием предложенных методов.

Одним из наиболее распространенных методов решения задач математического программирования является метод штрафных функций. Известные варианты этого метода сталкиваются с серьезными трудностями при выборе параметра штрафа - самой ответственной операции метода. В диссертации исследуется эта проблема.

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

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

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

Аппробация работы. Материалы диссертации обсуждались на семинаре отдела прикладной математики Института проблем кибернетики РАН, на 1-й Всесоюзной школе-семинаре по численным методам для многопроцессорных ЭВМ (Вийтна ЭССР, 1986), на IV Симпозиуме по методам решения нелинейных уравнений и задач оптимизации (Вильянди, ЭССР, 1987), на 2-й Всесоюзной школе-семинаре по численным методам для многопроцессорных ЭВМ (Вийтна ЭССР, 1987), на Всесоюзной конференции "Современные проблемы информатики, вычислительной техники и автоматизации" (1988г., Москва).

Публикации. По теме диссертации опубликовано 4 работы.

Структура и объем диссертации. Работа состоит из списка обозначений, введения, двух глав, объединяющих 7 параграфов, заключения и списка литературы из 143 названий и содержит 128 страниц машинописного текста.

Нумерация формул и утверждений диссертации и автореферата не совпадают.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Первая глава посвящена нетрадиционному изучению некоторых

- 5 -

методов безусловной выпуклой оптимизации.

Через Con1(X) далее будем обозначать класс выпуклых непрерывно-дифференцируемых функций на некотором множестве х , через Con1 будем обозначать подкласс функций из Con1, градиент которых удовлетворяет условию Липшица с константой L >О

\Г (х) - /' (у) | $ L-1 х - у | , V х,у е Я".

В § 1.1 изучаются некоторые неравенства для функций из класса Соп^-1 и исследуется круг вопросов, в той или иной степени связанных с поведением градиентного метода

хк+1= тк - а/'(хк) , а = const >0 (1)

при решении с его помощью задачи выпуклой безусловной минимизации

min f(x) , х € ñ" . (2)

Получено усиление известного неравенства

< /' (х)-Г (у), х-у > > —I/• (х)-/' (у)|2, (3)

справедливого для любой функции / е Соп^'1, V х,у € Я": Лемма 1. Пусть / € CotiJ/ 1. Тогда V х,у € Я" < /' (х)-/' (у), х-у > > 1 00

^ fix) - /(у) + </'(у), у-*> + — I IГ (V-/'(x)|2 >

2Ь u=o

^ 00 ^ 00 ^ 1 \r^)-rix)\z + - J l/'№k)-/'(y)|2,

к=о к=о

где 1

1 (4) ®к= wk-i+ -£-[/'(У)_/' (Юк~1'

В частности, V х.у € й"

1 -

< /*(х)-/'(у), х-у > ?-|/'(х)-/'(у)1г +

Tj

^ 00 ^ 00

+ ~ I + Г7 1 1/'Ч)-/'(у)|г. (5)

2Ь к=1 гь к=1 в

Заметим, что последовательности íu^}, (гук), определяемые

согласно (4), можно интерпретировать как последовательности,

построенные градиентным методом минимизации с постоянным

шагом 1/L соответственно для функций

G(z) = f(z) - <f'(x), z>,

Р(г) = /(г) - </'(у), 2> из начальных точек у и х соответственно.

Для точки ха~ х-оу" (х) установлено следующее неравенство.

Леша 2. Пусть / € Соп^'1, х € Я11, /' (х) * 0 , О $ а < 1/1. Тогда

1 - а£ «с- $ 1 . (6)

!/'<*> I |

Эта лемма показывает, что, с одной стороны, градиентный метод (1) обладает свойством монотонного невозрастания нормы градиента целевой функции на элементах минимизирующей последовательности {хк), а с другой стороны, метод (1) способен обеспечить на каждом шаге уменьшение нормы градиента не более чем в 1 -а! раз. Заметим, что как правое, так и левое неравенства в (б) могут обращаться в равенства при любом а, /Ъ. Отсюда сразу следует такой факт.

Утверждение 1. Пусть / € Соп^'\ /'(х0) * О, О ^ а < 1/1. Тогда градиентный метод (1) не может за конечное число шагов привести в точку минимума :

|/'(хк)| > 0, к = 0, 1..........|

Затем исследован вопрос об условиях достижения равенства в неравенстве (3).

Леша 3. Пусть / € Сот^'1. Равенство

< /'(х)-/'(у), х-у > = —[Г (х)-/'(у)|2

ь

выполняется тогда и только тогда, когда

/• ( х + — [/' (у)-/' (х)] ] = /• (у),

1 (7) /'( У + — [/'(*)-/'(у)] ) = /'(х). |

Смысл последней леммы не очевиден, если оставаться в рамках уже классического неравенства (3). В то же время, обратившись к новому неравенству (5), легко видеть, что условие (7) обеспечивает обращение в нуль рядов в правой части (5).

Более тонкие исследования, чем в лемме 2, позволили установить следующие результаты.

Теорема 1. Пусть / € Соп^-1, 0 < а < 1/1, (х) Ф 0.Тогда

(1-аЬ)[1 - (1-аЬ)соз2{/' (ха), /•(*)>] |/'(ха>|

- < - ^

а!соз{/' (х ), /'(х)} |/'(х)|

- 7 -

соз2{/'(ха), /'(х)} + аЬ - 1

^ - , (8)

aLcoaif (ха), /'(х))

1 - аL |/'(га)|

-^- ^ cos{/'(х_), /'(х)>. (9)

соз{/'(та), fix)} |/'(х)| а |

Неравенства (8), (9) содержат больше информации о свойствах градиентного метода, чем неравенство (6). Так неравенство (9) показывает, что если

cos{f(xa), f(x)} < 1 (т.е. если изменилось направление градиента в точке ха ), то

1Г(*а>| < 1Г(х)|, и в левом неравенстве (б), в этом случае, уже не может быть равенства.

В §1.2 изучены некоторые геометрические свойства градиентного метода в конечномерном пространстве.

В общем градиентном методе решения задачи (2):

=*k- V'(V • <10>

выбор шага с^ > 0 осуществляется по условию Данилина-Армихо:

/(V - /(rk - v,(V> > eakl/'(Vl2- (11)

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

Установлено важное свойство монотонности градиентного метода (10) - (11) относительно множества Лебега.

Лемма 4. Пусть / € Con1, последовательность Схк> строится по схеме (10) - (11) при s с (1/2, 1). Если /'(хк) * 0, то для любого у € Я" такого, что

Я{/) ^ Я*к+1) будет справедливо неравенство

|хк+1 - < |хк - у|. |

Завершает параграф простое доказательство монотонной сходимости градиентного метода.

Теорема 2. Пусть / € Con1, X* ¿ 0, последовательность (xk) строится по схеме (10) - (11) при е € И/2, 1), причем

о^ > a > 0 .

Тогда последовательность (хк> сходится к некоторому элементу Хф € Г :

|хк - х+| - 0, к - оо . При этом, если /'(х^+1) Ф 0 , то для любого х* е X* будет

справедливо неравенство

|хк+1 - х* | < |хк - х* | при всех k = 0, 1.....I. |

В §1.3 рассматривается градиентный метод со специальным выбором шага, приспособленный для минимизации "овражных" функций.

Для решения задачи безусловной минимизации (2) для функций из класса Con^1 предлагается следующий метод. Выбирается некоторое число е - уровень стабилизации направления градиентов ( 0 < в < 1 ) и некоторый номер I . Итерации осуществляются градиентным методом по схеме (10), причем о^. ( k 2 I ) выбирается по методу наискорейшего спуска если

cos {/'(хк_г), / Mik))H • В противном случае полагаем ак = а,0<а<1. Для квадратичной сильно выпуклой функции

/(х) = i < Ах, х> - <u, х>, А - А* > О (12)

метод минимизации запишем в виде

Xk+1= Хк - а(Агк- и) , хо е д" . (13)

Пусть собственные значения матрицы А удовлетворяют условию

0 < \г $ ... < \п , Х1 < \п . (14)

Обоснование разумности предложенного метода дано в теореме:

Теорема 3. Пусть выполнены условия (14) и пусть проекция вектора xQ- х* на множество

не равна 0:

V й { х € R"| Ах = \,х } у 4 рг (х - х*) jt 0 .

7 °

Тогда для последовательности {хк>, построенной по схеме

(13) для квадратичной функции /(х) из (12) при

2

0 < а < -

1 п

справедливо соотношение

соз I /' (xk), v > -» 1 , при k •* оо . |

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

Тестовые примеры, просчитанные этим методом, дают весьма существенное ускорение сходимости по сравнению с методами наискорейшего спуска и градиентного метода с постоянным

шагом.

В §1.4 изложен подход, основанный на применении градиентного метода к абстрактной приближенной (не обязательно устойчивой ) схеме в гильбертовом пространстве. Теория разностных схем изучает в основном устойчивые разностные схемы. В тех случаях, когда устойчивые разностные схемы не применимы, используются различные методы регуляризации.

Изложим основной результат теории абстрактных приближенных схем в гильбертовом пространстве. Для гильбертова пространства Н введем последовательность гильбертовых пространств {Нп), п = 1, 2,... , аппроксимирующих Н, и линейные ограниченные операторы сужения Тп: Н - Нп , ТпН = Яп . Пусть заданы линейные ограниченные операторы А : Н - Н и Ап: Нп - Яп,

п = 1,2.....Пространство линейных ограниченных операторов

из Я в С будем обозначать через ЦН, С); ЦН) = ЦН, Н). Для оператора А е ЦН) через А* будем обозначать сопряженный оператор к А : <А*х, у> = <х, Ау> , V х,у € Н .

Напомним следующие определения. Последовательность Схп), хп € Нп, называется Т-сходящейся к элементу х е Н , если

|ХП - Тпх\[] - О при п - 00 . п

Нормы в Нп называются согласовавший с нормой в Н , если для любого х € Н

11ш [Тх[н = |х|„ . (15)

11-ию п

Будем говорить, что на элементе I е й выполнено условие аппроксимации, если

Г х - Т Ах[и - 0 при п - оо . (16)

п

Говорят, что для последовательности (А ), А с Т,(Н ) выполнено условие устойчивости, если существует постоянная 7 > О такая, что начиная с некоторого номера по

Ип*п1И * Т|хп|н . V хп€ яп , п * по • (17)

п п

В теории абстрактных приближенных схем рассматривается разрешимое операторное уравнение

Ах = и , и а 1т А , А е ЦН) (18)

и последовательность приближенных уравнений

Основной результат теории абстрактных приближенных схем

сформулирован в теореме:1

Теорема 4. Пусть выполнены следующие условия :

1) согласования норм (15);

2) аппроксимации (16) на каждом решении уравнения (18);

3) устойчивости (17) для {¿4п> с постоянной 7 > 0 ;

4) последовательность (и ) Т-сходится к и при п - <» .

п А

Тогда

1') решение х уравнения (18) единственно; 2') для всех достаточно больших п решение хп уравнения

(19) единственно; 3') (лМ Г-сходится к х при п - со и справедлива оценка

«V ГЛ * Г1[ IV Гпи|н + 1АпТпХ - ТпАх\н ] . I

п ц п п

Условие 2) теоремы проверить практически очень трудно, поэтому обычно требуют выполнения условия аппроксимации (16) при всех х € И . Однако, в этом случае условие устойчивости накладывает весьма существенные ограничения на оператор А . Точнее, справедливо

Утверждение 2. Пусть выполнены условия

1) аппроксимации (16) при всех х е Н ;

2) устойчивости (17) для с постоянной 7 > 0 ;

3) согласования норм (15). Тогда

|Аг|я ^ , V * е Н . (20|

Соотношение (20) означает, что на 1ш А существует ограниченный обратный оператор ¿Г1 € 1(1ш А, Н) , причем 1^"11ь(1гп А Н) ^ 7~1• Это очень сильное ограничение на оператор А .

При нарушении условия устойчивости может отсутствовать Т-сходимость решения приближенного уравнения к решению исходного.

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

1 См. Треногин В.А. функциональный анализ,- М.: Наука, 1980.

(19), то будет справедлива Г-сходимость последовательности к нормальному решению уравнения (18). Приближенное уравнение (19) запишем в следующем виде

АпХп= ип (21)

(здесь не предполагается разрешимость уравнения (21)). Считаем, что выполнены условия А=А* > О, Ап=Ап>0' МП1=Ь п=1,2,... ,

А € ЦН), Ап € € ЫН,Н„), Т„Н = Я„

(22)

ип= Тп<и + Еп>' 8п € Н• 1Еп1 - О. П - «о .

Наряду с приближенным уравнением (21) рассматривается функционал

= I < Лпхп> Хп> - < V V' ХП « Нп (23) Последовательность {хп> , Г-сходящаяся к нормальному относительно хо решению ро уравнения (18), строится методом градиентного типа для минимизации функционала / (х ) вида

(23). При каждом п = 1, 2,... берем

х = Т х (24)

п.о по

и делаем некоторое количество шагов по формуле

х , ,= х , - (А х , - и ), к = 0,1,2,..., к , (25)

п,к+1 п.к п п.к п ' * п'

которая является схемой градиентного метода с постоянным шагом для функционала Т (х ) из (23):

Сходимость предложенного метода доказана в теореме: Теорема 5. Пусть а € (0,|] - фиксированное число, Огп> -последовательность положительных чисел,

0п=тах (|7п|, Ип|, V V Г С I2-Пусть выполнены следующие условия :

1) справедливы предположения (22);

2) выполнено условие согласования норм (15);

3) б -» 0, п - оо .

п

Тогда последовательность {х . ), построенная по схеме

п

(24)-(25), Г-сходится к нормальному относительно хо решению ро уравнения (18):

2 Здесь Г У 1 означает наименьшее целое число не меньшее у

' к " '«Ро» 0 ' п - 00 • ■

■ п

Последовательность {х } из теоремы 5 "минимизирует

п* п

невязку" последовательности приближенных задач (21):

IАх , - и I - 0, п -« оо . * п п.к п1 п

В §1.5 рассматривается метод тяжелого шарика для минимизации функций из класса СапЭтот метод на каждой итерации использует информацию о поведении оптимизируемой функции на предыдущей итерации. Метод обладает более высокой скоростью сходимости, чем градиентные методы. В частности, такой метод достаточно хорошо проходит овраги.

Метод тяжелого шарика для решения задачи безусловной выпуклой минимизации (2) записывается в следующем виде

хк+1= хк ~ (хк) + Р(хк ~ ь (2б)

Теорема 6. Пусть / € Соп.и выполнены условия :

1) X* * 0 ;

2) последовательность (хк> строится по схеме (26), х =<г0;

2(1-р)г

3) 0 < 0 < 1, 0<а< - .

(1+Р)1

Тогда последовательность (хк) сходится к некоторому элементу х* € X*. |

Глава 2 посвящена итеративным методам штрафных функций для решения задачи выпуклого программирования. Метод штрафных функций является одним из наиболее распространенных методов решения задач математического программирования. Универсальность и простота в реализации - его основные черты - зачастую являются наиболее важными для решения многих практических задач.

Основная идея метода штрафных функций заключается в решении задачи безусловной минимизации с некоторым фиксированным значением параметра штрафа. При этом, если параметр штрафа выбирать очень большим, то минимум штрафной функции будет близок к решению исходной задачи. В этом случае, однако, замедляется скорость сходимости методов безусловной минимизации, что связано с усилением "овражности" штрафной функции.

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

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

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

Рассматривается задача выпуклого программирования

/(х) - min, х € X. (27)

Штрафная функция для задачи (27) записывается в виде

F{x, С) = fix) + Cg(x), С > О, где g(x) - выпуклая на Я™ функция, причем g(x) = 0 , если х 6 X , g(x) > 0 , если х ¿ X .

Вводятся обозначения X* £ Argmln { /(х) I х € X ), /* - Inf { /(x) I x € X ). Через Conioc1,1 будем обозначать класс таких выпуклых непрерывно-дифференцируемых на К" функций /(х), что для любого ограниченного множества S найдется число L = Ь(/, S) > О :

\Г(х)-/'(у)\ $ L-\x-y\ , V х,у е S. Минимизирующая последовательность для решения задачи (27) строится по следующей итерационной схеме

В §2.1 доказываются вспомогательные результаты и некоторые теоремы. В частности, важна следующая лемма.

Лемма 5. Пусть f.gí Con1, X* ¿ 0 , dlam X* < <» , последовательность (xk) строится по схеме (28), ис^ > О удовлетворяют условию

Р(хк, Ck)-P(xk^kF' (xk, Ck), Ck) :> eak|í"(xk, Ck)|2, (29)

где 1/2 < e < 1. Тогда последовательность txk) ограничена. |

Решение неравенства (29) существует V хк и для его нахождения применяется метод дробления следующим образом. Выбираем некоторое число 0 € (О, 1) и начальное приближение а0 > 0. Алгоритм состоит из следующих шагов: (30)

5) существует подпоследовательность {х } такая, что

Ki

Шаг 0: а := а°/Ск ;

Шаг 1: Проверяем неравенство (29) при с^ = а. Если неравенство выполняется, то алгоритм заканчивает свою работу. В противном случае выполняем

Шаг 2: а := 0-а и переходим к шагу 1. |

Показано, что в случае /, g е Conloe1,1 число дроблений в алгоритме (29) равномерно ограничено по fe. Важное значение имеет следующая теорема. Теорема 7. Пусть /, ge Conloe1,1 и выполнены следующие условия :

1) последовательность (хк) строится по схеме (28) ;

2) X* * 0 , diam X* < со ;

3) Ск * со ;

4) о^ вычисляются по алгоритму (30) при 1/2 < е < 1; следовательность <

р(х. , Г) - О, I Ki Тогда

р(хк, Г) - 0, fe - «о . |

С помощью этой теоремы получен следующий результат. Теорема 8. Пусть /, g € Conloe1•1 и выполнены следующие условия :

1) последовательность (хк) строится по схеме (28) ;

2) X* * 0 , dlam X* < оо ;

3) Ск * оо ;

4) а^ вычисляются по алгоритму (30) при 1/2 < в < 1;

5) Ст+1 удовлетворяет условию

Сш+1

--- 0 , m - оо .

т к=0

Тогда

р(агк, X*) - О, fe - со . |

В этом методе параметры Ск и с^ можно задавать априорно, если /, g ( Соп^-1 и известна константа Липшица Ь. Например, Ск = ln (fe + 2) , с^ = 1/(21 + 2L>ln (fe + 2)) . В §2.2 доказываются очень важная теорема об альтернативе и ее следствия.

Теорема 9. (Теорема об альтернативе). Пусть выполнены следующие условия :

1) /, g e Conloe^ '1 ;

2) X* ¿ 0 , diam X* < ю ;

3) последовательность (хк> строится по схеме (28) ;

4) Ск t о» ;

5) с^ вычисляются по алгоритму (30) при 1/2 < е < 1; Тогда либо

р(тк, X*) - 0, к - оо ,

либо

3 х í X \ X*: |х - х | - 0., fe - со . |

Сходимость метода (28), (30) к единственной точке из допустимого множества X при отсутствии сходимости к множеству X* решений задачи (27) весьма важна для понимания свойств итеративного метода штрафных функций.

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

Теорема 10. Пусть выполнены следующие условия :

1) g € Conloé •1 ;

2) X* ¿ 0 , dlam Г < «> ;

3) последовательность Сх. } строится по схеме (28) ;

» 1

4> Ск т ю • I -г = "> '

к=о °к

5) о^ вычисляются по алгоритму (30) при 1/2 < е < 1; Тогда

р(хк, Г) - О, k - со . |

Если в условиях теоремы 10 взять " 1

2 - < 00 ,

к=0 Ск

то легко привести примеры, когда будет отсутствовать сходимость метода (28), (30) к решению задачи (27). Таким образом, обобщение теоремы 10 на случай сходящегося ряда обратных величин параметров штрафа не представляется возможным.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

Приведем основные результаты, полученные в диссертации.

1. Получены новые неравенства для функций класса Con1. Исследовано неравенство (3). Получены двусторонние оценки нормы градиента в градиентном методе.

2. Выделено и доказано важное свойство сильной монотонности градиентного метода с выбором шага из условия Данилина-

- 16 -

Армихо относительно любой точки множества Лебега.

3. Предложен и обоснован овражный градиентный метод для реше-задач безусловной оптимизации.

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

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

6. Доказана теорема об альтернативе для итеративного метода штрафных функций.

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

Материалы диссертационной работы содержатся в следующих

публикациях:

1. Антипин A.C., Родионов A.B. Метод проекции тяжелого шарика // Труды 4 Международного симпозиума "Автоматизация и научное приборостроение '87". - Варна, Болгария, 1987.- Т.1.- С.1-11.

2. Родионов A.B., Третьяков A.A. Один метод решения задачи выпуклого программирования // Вопросы кибернетики. Методы и алгоритмы анализа больших систем. - М.: 1988.-С.111-117.

3. Родионов A.B. Об итеративных методах штрафных функций. // "Современные проблемы информатики, вычислительной техники и автоматизации". - Тезисы докладов Всесоюзной конференции. - Москва, 1988.- С. 28-28.

4. Родионов A.B. О методе тяжелого шарика // Вопросы кибернетики. Модели и методы анализа больших систем. - М.: 1991.- С.96-104.