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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

. ОД

На правах рукописи УДК 519.853.32

ЧЕРНЭУЦАНУ ТАТЬЯНА ВАСИЛЬЕВНА

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

Специальность 01.01.09 - Математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 1998

Работа выполнена на кафедре исследования операций математико-механ ического факультета Санкт-Петербургского государственного университета.

Научный руководитель - кандидат физико-математических

наук, доцент ДАУГАВЕТ В.А.

Официальные оппоненты - доктор физико-математических

наук, профессор ФОМИН в.н.

кандидат физико-математических наук, профессор ВАСИЛЬЕВ Л.В.

Ведущая организация - Сыктывкарский государственный университет.

Защита состоится «. _» ¿ _ 1998 г.

в часов на заседании диссертационного Совета К.063.57.49 по

защите диссертаций на соисканне ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Старый Петергоф, Библиотечная площадь 2,математико-механический факультет.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета по адресу: 199034, С.-Петербург, Университетская набережная, 7/9.

Автореферат разослан «_ » ¿¿УГьАг^Л- 1998 г.

УЧЕНЫЙ СЕКРЕТАРЬ

диссертационного Совета А.И.Шепелявый

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

Актуальность темы. Диссертация посвящена разработке ювых быстрых алгоритмов решения двух нелинейных задач опти-шзашш. Первая задача - дискретная чсбышеоская аппрокстша-шя:

<Р(*) ■= |//И! »»"> 0)

аЕ1т г€и

до - многогранное множество нз И", задаваемое с помощью сонечного числа линейных неравенств

Ъ(г) := {Ъ}, х) - (I, > О, У € 1 : г. Зторая задача - дискретная аппроксимация в норме 1\\

т

(2)

.=1 1г

;1а практике задачи такого типа возникают в теории управления, з обшей теории антенн, при синтезе фильтров и во многих других »бластях техники.

Среди методов решения задач (1)-(2) широко используются методы линеаризации. Идея методов линеаризации очень проста - все нелинейные функции /,-, входящие в задачу, заменяются в малой жрестностп некоторой точки хи их линейными аппроксимациями

¡Зля определения направления спуска из точки х* линеаризованная целевая функция минимизируется, что приводит к задаче линейного программирования. Однако, больше преимуществ имеют варианты методы линеаризации, в которых к линеаризованной цеповой функции добавляется квадратичная добавка. В таких вариантах направление спуска находится как решение задачи выпуклого квадратичного программирования (ВКП). Заметим, что, как правило, задачи (1)-(2) имеют большое количество функции (большое 7»), поэтому соответствующие задачи ВКП имеют еще [I большую размерность. Разумеется, эффективность метода линеаризации зависит от способа нахождения направления спуска. В

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

Цель работы. Обоснование! нового варианта метода линеаризации для задачи (2) н разработка быстрых алгоритмов лля решения задач выбора направления спуска в методах линеаризации для задач (1) и (2).

Методика исследования. Исследования опираются на общую теорию математического программирования и на теорию нелинейных чебышевских приближений.

Научная новизна. В диссертации получены следующие результаты:

1. На основании метода Бэста с учетом специфики задачи разработан алгоритм, определяющий направление спуска в методе линеаризации с квадратичной добавкой для чебышевской аппроксимации.

2. Описан новый вариант метода линеаризации с квадратичной добавкой для задачи аппроксимации в норме 1\ и доказаны следующие результаты:

- при некотором дополнительном предположении о задаче всякая предельная точка последовательности {л^}, генерируемой описанным методом, является стационарной:

- в окрестности марковской точки имеет место квадратичная скорость сходимости;

- в линейном случае имеет место конечность метода;

- выбор направления спуска сводится к решению задачи ВКП с двусторонними прямыми ограничениями на переменные.

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

4. Для всех описанных алгоритмов составлены программы на языке РАБСАЬ и приведены результаты численных эксперимен-

тов.

Практическая ценность. Программы, представленные в диссертации, могут быть использованы для численного решения задач аппроксимации (1)-(2), а также для самостоятельного решения задач квадратичного программирования.

Апробация работы. По результатам диссертации сделаны доклады на семинаре кафедры исследования операций, на семинаре по нелинейным экстремальным задачам и на семинаре по нелинейному анализу при С.-Петербургском Университете.

Структура и объем работы. Диссертация состоит из введения, пяти параграфов, списка литературы и приложений. Объем диссертации - 100 страниц основного текста и 59 страниц приложении. Список литературы содержит 51 наименование.

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

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

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

F(xk, Л) h) + max |ЛЫ + {¿(хк), h)\ hjf .

Z ifcl.T«

Эта задача равносильна задаче ВКП:

!</,./,)+*-> inf (3)

1 AeR . ieR

(f'i^t),h)+t>-fi(xk), i £ 1 : m, (¿У, Л) > -фк), j el: Г.

В качестве шага а* в выбранном направлении hk берется максимальное а из числовой последовательности {1, 0, О2,...}, для которого выполняется неравенство

фк + ahk) < фк) - сф(хк) - F(rk, hk)). (4)

Здесь S € (0,1) и в € (0,1) - параметры метода линеаризации.

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

при ограничениях

- мстила Бита. В работах Б'и'та было показано, что существующие различные методы перебора граней отличаются по-сушеству лише, способом решения на каждой итерашш некоторой линейной системы. Если черт Л обозначить матрицу ограничений задачи (3), а через ЛJ матрицу, состоящую нз линейно независимых строк матрицы Л с номерами из индексного множества ./. то матрица этой линейной системы имеет следующую блочную структуру

где Д] некоторая фиксированная матрица, а 0 - нулевая матрица. В п.1.3 диссертации разработан способ решения системы с матрицей (5). который связан с пересчетом на каждой итерации матрицы

Заметим, что у индексного множества / на каждой итерации меняется не более, чем один индекс: множество ,/ может расширяться на один индекс, либо сокращаться на один индекс, либо в нем происходит замена одного индекса другим. Для каждого из этих случаев разработаны алгоритмы пересчета матрицы /?(•/).

Во втором параграфе диссертации рассматривается метод линеаризации для задачи (1). Для решения задачи квадратичного программирования (3) используется метод Бзста. Одним из трудоемких моментов в методе Бэста является поиск точки, с которой можно начинать вычисления. В п.2.3.2 показано, что для задачи (3) этот процесс не вызывает затруднений. В п.2.3.3 показано, что специфика задачи (3) позволяет сократить алгоритм Бэста, а именно, доказано, что некоторые ситуации алгоритма для задачи (3) заведомо не реализуются.

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

Б(.1) = С(./)-'.

лепестков в радиационной модели построения 15-элементной линейной антенны при ограничении на расположение элементов.

Остальные параграфы диссертации связаны с задачей (2). Выбор нормы 1\ обусловлен следующими соображениями. Если значения аппроксимируемой функции являются экспериментальными даннымн, то они могут содержать случайные ошибки, так называемые "'дикие'" точки, когда значения функции резко отличаются от ожидаемых. В этом случае чебышевская аппроксимация сильно искажает истинную картину. Если "дикие'" точки изолированы и их мало, то коэффициенты наилучшей аппроксимации в норме 1\ мало отличаются от коэффициентов наилучшей аппроксимации для приближаемой функции без "диких" точек.

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

В частности, в п.5.4 показано, что на к-том шаге неравенство (4) выполняется за конечное число проб. В п.5.5 диссертации доказано, что при выполнении некоторых дополнительных требований к исходной задаче (2) предельная точка последовательности {./'I}, генерируемой методом линеаризации, является стационарной. В п.5.7 установлена квадратичная скорость сходимости метода в окрестности марковской точки. В п.5.8 доказана конечность метода в линейном случае.

Обратимся к численной реализации рассматриваемого метода линеаризации. Направление спуска 1ц из точки ¿ч- находится как решение экстремальной задачи

F(xk,h):=l-{hJ,)+ £ |/,-(**) +{¿(а*),Л>Н W, • (')

¿ íel:m herí

Метод решения этой задачи предлагается в четвертом параграфе диссертации.

В третьем параграфе диссертации исследуется негладкая

экстремальная задача 1

:= -(Dx. .г) + <«„,.т) + £ 1<пу,л-> + -4 шГ , (8)

- ; —1 .гбН.

где О - снмметрпчнад неотрицательно определенная матрица п.—го порядка, «„.а],,..,«,, - заданные л-мерные векторы, (/(,...,</,„ -вещественные числа. Задача (7) является частным случном этой задачи.

Показано, что задача (8) эквивалентна задаче ВКП: .г) + (я0, .г) + Е,е1:т и -> И1Гх,(,,...,(т ,

(а,-,+ и

¿' е 1 : я;,

и в случае положительно определенной матрицы О решение задачи (9) можно свести к решению другой задачи ВКП с двусторонними прямыми ограничениями на переменные:

-1 < уЩ <1 V 2 е 1 : т. ^

Здесь С) = 1AD~]Ä', а через А обозначена матрица. строками которой являются секторы «ь- ■•,»«• Если у - решение задачи (10), то решением задачи (9) является вектор

Разработке алгоритма решения задачи (10) посвяшен четвертый параграф. Для эффективной работы метода линеаризации требуется алгоритм, который использует небольшой объем оперативной памяти компьютера и быстро работает. В диссертации представлены два алгоритма решения задачи (10), использующие идею метода Ломке.

Первый алгоритм предназначен для случая, когда порядок матрицы Q, равный tri, невелик. Заметим, что при применении метода Ломке к задаче (10) на каждой итерации метода требуется решать базисную систему порядка 2т. Специфика задачи (10)

позволила свести решение базисной системы метода Лсмке к решению другой системы вдвое меньшего порядка, поэтому первый алгоритм требует хранения в оперативной памяти массива длиной т .

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

Заметим, что второй алгоритм позволяет решать задачи (7) при небольшом п и достаточно большом значении т. так как ранг матрицы Q не превосходит п.

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

Проведены также численные эксперименты с таблицами функций, содержащими "дикие1' точки.

Основное содержание диссертации опубликовано в работах

Даугавет В.А., Чернэуцану Т.В. Об одной задаче негладкой оптимизации. // Вестник СПбГУ. 1997. Вын.2, N 8. С.11-1-5.

Чернэуцану Т.В. Метод линеаризации для дискретной аппроксимации в /ь // Деп. в ВИНИТИ. АГ2064В97 от 24 июня 1997 г. 26 С.

Чернэуцану Т.В. Минимизация выпуклой квадратичной функции с двусторонними ограничениями на переменные. // Вестник СПбГУ. 1997. Вып.4, N22. С.56-61.