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

Введение

1 Опорные векторы и их свойства

1.1 Основные понятия

1.2 Конус направлений попадания во множество.

1.3 Конус направлений попадания в многогранное множество

1.4 Опорный конус для непустого многогранного множества

2 Метод опорных векторов для отыскания точки выпуклого множества

2.1 Метод опорных векторов с составным шагом.

2.2 Оценки толщины множества в методе опорных векторов

2.3 Регулировка заглубления по натуральному ряду.

2.4 Приемы локального ускорения метода опорных векторов с составным шагом.

2.4.1 Суммирование соседних направлений.

2.4.2 Ортогонализация направления по предыдущему

2.5 Решение экстремальных задач методом опорных векторов с составным шагом.

2.6 Комбинация метода опорных векторов с составным шагом и метода проекции точки.

Метод опорных векторов с мультипликативным шагом для решения систем выпуклых неравенств

3.1 Метод опорных векторов с мультипликативным шагом

3.2 Метод зеркального отражения

3.2.1 Метод зеркального отражения в гильбертовом пространстве . ,.

3.2.2 Метод зеркального отражения в конечномерном пространстве.

3.2.3 Комбинация метода зеркального отражения и метода опорных векторов с составным шагом

3.3 Метод линеаризации.

3.3.1 Решение одного неравенства.

3.3.2 Метод линеаризации, использующий задачу квадратичного программирования

3.3.3 Общая схема методов линеаризации для решения систем выпуклых неравенств.

3.3.4 Метод линеаризации, использующий задачу линейного программирования

3.3.5 Метод линеаризации, использующий задачу решения системы линейных неравенств.

Метод опорных векторов для решения экстремальных задач

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

4.1.1 Метод решения задачи выпуклого программирования с заданной абсолютной погрешностью

4.1.2 Метод решения задачи выпуклого программирования с заданной относительной погрешностью

4.1.3 Метод выпуклого программирования с заданной абсолютно-относительной погрешностью.

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

4.2 Отыскание минимакса с заданной точностью.

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

4.3.1 Метод решения задачи с абсолютными уступками

4.3.2 Метод решения задачи с относительными уступками

4.3.3 Метод решения задачи с абсолютно-относительными уступками

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

Одной из таких проблем является разработка простых и эффективных методов решения систем неравенств:

Pi(x) <0 г == 1,., ш, где х — выпуклые (псевдовыпуклые, квазивыпуклые) функционалы, определенные на гильбертовом пространстве Н.

Теоретически эта задача сводится к задаче математического программирования (см. Зойтендейк Г. [26, с.97]): min т] fi(x) — i] < 0 i = 1,., m, или к минимаксной задаче (см. Пшеничный Б.Н. [59, с.65]): . min max{-l,(pi(^),. .,срт(х)}, х£Н б однако, при таких подходах теряется возможность учета специфики задачи.

Одним из специальных методов решения систем неравенств, по видимом}^, можно считать метод последовательного проектирования для отыскания общей точки семейства выпуклых множеств Брэгма-на Л.М. [4]. Более развитым методом решения систем выпуклых неравенств является метод фейеровских приближений, предложенный Ереминым И.И. в [15] и развитый в его последующих работах. Этот метод, как показано в диссертации, включает в себя метод последовательного проектирования. В схему метода фейеровских приближений укладываются также и метод линеаризации для систем выпуклых неравенств Пшеничного Б.Н. [59, с.65-73], и проекционный метод Булавского В.А. [5], и метод ортогонального спуска Щепакина М.Б. [79]-[81]. Но реализации метода фейеровских приближений имеют, на наш взгляд, существенный недостаток: они гарантируют получение решения системы неравенств лишь в пределе. Это справедливо даже в том случае, когда система неравенств удовлетворяет условию Слейтера, и сведение ее к задаче математического программирования или минимаксной задаче гарантирует получение решения за конечное число итераций.

Другим специальным методом решения систем квазивыпуклых неравенств является метод обобщенного спуска во множество, предложенный Хабибуллиным Р.Ф. [73], [74], идейно происходящий от работ Шора Н.З. [77] и Поляка Б.Т. [53]. Этот метод при условии непустоты внутренности множества решений системы неравенств обеспечивает получение решения системы неравенств за конечное число итераций. Но, к сожалению, указанные авторы ограничились лишь очень общими условиями выбора шагов итерационного процесса и не дали рекомендации для построению эффективных численных реализаций этого метода. 7

Одной из задач, рассматриваемых в диссертации, является задача отыскания точки выпуклого множества Q из гильбертова пространства Н. Очевидно, что эта задача является общей моделью для задачи отыскания решения систем неравенств. В диссертации предлагается метод решения этой задачи, названный методом опорных векторов с составным шагом, описанный в терминах аппарата обобщенно-опорных функционалов, введеных Заботиным Я.И., Кораблевым А.Й., Хабибуллиным Р.Ф. в [22]. Предложенный метод обеспечивает отыскание точки из выпуклого множества с непустой внутренностью за конечное число итераций. Фактически метод является комбинацией метода фейровских приближений и метода обобщенного спуска во множество.

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

Далее в диссертации рассматривается задача выпуклого программирования: min (ро(х) pi(x) < 0 г = 1,., т.

Обилие методов решения этой задачи общеизвестно (см., например, Зойтендейк Г. [26], Кюнци Г.П., Крелле В. [43], Зангвилл У.И. [25], Полак Э. [52], Пшеничный Б.Н., Данилин Ю.М. [60], Химмельблау Д. [76], Еремин И.И., Мазуров В.Д. [19], Шор Н.З. [77], Васильев Ф.П. 8 б], Евтушенко Ю.Г. [12], Бейко И.В., Бублик Б.Н., Зинько П.Н. [3], Пшеничный Б.Н. [59], Гилл Ф., Мюррей У., Райт М. [7], Мину М. [45] и др.). Характерной особенностью большинства имеющихся методов является то, что они генерируют в общем случае бесконечные последовательности точек, в пределе сходящиеся к решению задачи. Но лишь немногие методы снабжены критериями погрешности решения по целевому функционалу или по норме. Поэтому в большинстве случаев приходится использовать эвристические критерии остановки (близость соседних точек итерационного процесса по целевому функционалу или по норме, малость нормы субградиента целевого функционала и т.п., см. например, Гилл Ф., Мюррей У., Райт М. [7]).

В диссертации же предлагаются конечные методы решения задачи выпуклого программирования с заранее заданной абсолютной, относительной или абсолютно-относительной погрешностью по целевому функционалу. Эти методы опираются на основную идею метода опорных векторов с составным шагом. При разработке алгоритмов решения задачи выпуклого программирования обнаружилась потребность в специфических методах решения систем выпуклых неравенств: они должны давать решение системы неравенств за конечное число итераций, причем не удалять начальную точку от множества, т.е. быть элементами фейеровских отображений относительно внутренности множества решений системы неравенств. Для разработки таких методов потребовалась разработка иного аппарата, названного методом опорных векторов с мультипликативным шагом. В рамках этого метода предложены две группы алгоритмов: мет,од зеркального отражения и мет,од линеаризации. Название первого метода происходит от геометрической интерпретации одного из методов решения систем линейных неравенств, который предложили одновременно Agrrion S. [82] и Motzkin T.S., Schoenberg I.J. [88] и идейно, конечно, связан с ним. Ме9 тод линеаризации имеет идейную близость с методом линеаризации для систем неравенств Пшеничного В.Н. [59] и проекционным методом Булавского В.А. [5], но, в отличие от них, его реализации (их в диссертации предложено три) обеспечивают получение решения за конечное число итераций.

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

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

Диссертация состоит из введения, четырех глав, заключения и списка литературы.