Введение к работе
Актуальность темы. Диссертация посвящена разработке ювых быстрых алгоритмов решения двух нелинейных задач опти-ппашш. Первая задача - дискретная чсбышевская аппроксима-шя:
<р(х) = шах |/,(.г)| -> iniii, (1)
jEl-in ril
де il - многогранное множество in R", задаваемое с помощью сонетного числа линейных неравенств
cj(r) :- {bj, х) - dj > 0, j Є 1 : г.
Зторая задача - дискретная аппроксимация в норме \\\
vW:=EI/.-W|-»SJ[- (2)
і=і R
Ал практико задачи такого типа возникают в теории управления, з обшей теории антенн, при синтезе фильтров и во многих других >бластях техники.
Среди методов решения задач (1)-(2) широко используются методы линеаризации. Пася методов линеаризации очень проста - все нелинейные функции /,-, входящие в задачу, заменяются в малой жрестноетн некоторой точки хи их линейными аппроксимациями
/і^тА)й/і(їі)т(/;(д),А).
Для определения направления спуска из точки г* линеаризованная целевая функция минимизируется, что приводит к задаче линейного программирования. Однако, больше преимуществ имеют варианты методы линеаризации, в которых, к линеаризованной цеповой функции добавляется квадратичная добавка. В таких вариантах направление спуска находится как решение задачи выпуклого квадратичного программирования (ВКП). Заметим, что, как правило, задачи (1)-(2) нмеТот большое количество функций (большое j»), поэтому соответствующие задачи ВКП имеют еще и большую размерность. Разумеется, эффективность метода линеаризации зависит от способа нахождения направления спуска. В
связи с этим актуальной является разработка быстрых и не требующих большой оперативной памяти компьютера алгоритмов для задач BKIL возникающих в методах линеаризации.
Цель работы. Обоснование нового варианта метода линеаризации для задачи (2) н разработка быстрых алгоритмов для решения задач выбора направления спуска в методах линеаризации для задач (1) и (2).
Методика исследования. Исследования опираются на общую теорию математического программирования и на теорию нелинейных чебышевских приближений.
Научная новизна. В диссертации получены следующие результаты:
1. На основании метода Бэста с учетом специфики задачи
разработан алгоритм, определяющий направление спуска в методе
линеаризации с квадратичной добавкой для чебышевекой аппрок
симации.
2. Описан новый вариант метода линеаризации с квадратич
ной добавкой для задачи аппроксимации в норме /( н доказаны
следующие результаты:
при некотором дополнительном предположении о задаче, всякая предельная точка последовательности {xj-}, генерируемой описанным методом, является стационарной:
в окрестности марковской точки имеет место квадратичная скорость сходимости;
в линейном случае имеет место конечность метода;
выбор направления спуска сводится к решению задачи ВКП с двусторонними прямыми ограничениями на переменные.
-
Разработаны алгоритмы решения задачи ВКП с двусторонними прямыми ограничениями на переменные в случаях, когда матрица квадратичной формы имеет малый порядок или большой порядок, но малый ранг.
-
Для всех описанных алгоритмов составлены программы на языке PASCAL и приведены результаты численных эксперимен-
TOD.
Практическая ценность. Программы, представленные с диссертации, могут быть использованы для численного решения задач аппроксимации (1)-(2), а также для самостоятельного решения задач квадратичного программирования.
Апробация работы. По результатам диссертации сделаны доклады на семинаре кафедры исследования операций, на семинаре по нелинейным экстремальным задачам и на семинаре по нелинейному анализу при С.-Петербургском Университете.
Структура и объем работы. Диссертация состоит из введения, пяти параграфов, списка литературы и приложений. Объем диссертации - 100 страниц основного текста и 59 страниц приложений. Список литературы содержит 51 наименование.