Методы отсечений с обновлением аппроксимирующих множеств для задач нелинейного программирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

УДК 519.85

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

ЯРУЛЛИН РАШИД САМАТОВИЧ

МЕТОДЫ ОТСЕЧЕНИЙ С ОБНОВЛЕНИЕМ АППРОКСИМИРУЮЩИХ МНОЖЕСТВ ДЛЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Автореферат

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

2 О МАЙ 2015

005569242

КАЗАНЬ - 2015

005569242

Работа выполнена в ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» на кафедре анализа данных и исследования операций.

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

сор кафедры анализа данных и исследования операций Казанского (Приволжского) федерального университета Заботин Игорь Ярославич

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

доктор физико-математических наук, заведующий лабораторией невыпуклой оптимизации Института динамики систем и теории управления им. В.М. Матросова СО РАН (г. Иркутск), профессор

Стрекаловский Александр Сергеевич

доктор технических наук, профессор кафедры прикладной математики и информатики Казанского национального исследовательского технического университета им. А.Н. Туполева - КАИ Галиев Шамиль Ибрагимович

Ведущая организация: Омский филиал Института математики им.

С.Л. Соболева СО РАН

Защита состоится 2 июля 2015 г. в 14 часов 30 минут на заседании диссертационного совета Д 212.081.24 при ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, д. 35, ауд. 1011 2-го корпуса КФУ.

С диссертацией можно ознакомиться в научной библиотеке им. Н.И. Лобачевского ФГАОУ ВПО «Казанский (Приволжский) федеральный университет».

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

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

А.И. Еникеев

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации представлялись и обсуждались в 2011-2014 гг. на итоговых научных конференциях КФУ, Всероссийской конференции «Статистика. Моделирование. Оптимизация» (Челябинск, 28 ноября - 3 декабря 2011 г.), XIV Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 28 февраля - 4 марта 2011 г.), итоговых научно-образовательных конференциях студентов Казанского университета в 2011, 2012 гг., V Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2-6 июля 2012 г.), Республиканских конкурсах научных работ студентов и аспирантов на соискание премии им. Н.И.Лобачевского (Казань, РМОО «Лига студентов Республики Татарстан», 9 -12 апреля 2013 г.: 9-12 апреля 2014 г.), 37-й и 38-й Всероссийских молодежных конференциях «Информационные технологии и системы » (Калининград, 1 -6 сентября 2013 г.: Ниж. Новгород, 1-5 сентября 2014 г.), XVI Всероссийской конференции «Математические методы распознавания образов» (г. Казань, 610 октября 2013 г.), Международной конференции «Дискретная оптимизация и исследование операций (Б0011-2013) » (Новосибирск, 24 - 28 июня 2013 г.), XVII Международной конференции «Проблемы теоретической кибернетики» (Казань, 16-20 июня 2014 г.), XV и XVI Международных школах-семинарах «Методы оптимизации и их приложения» (Байкал, 23 - 29 июня 2011 г.: 30

июня - 6 июля 2014 г.), IX Всероссийской и X Международной конференциях «Сеточные методы для краевых задач и приложения» (Казань, 17 - 22 сентября 2012 г.: 24 сентября - 29 сентября 2014 г.).

Публикации. Основные результаты диссертации опубликованы в 21 работе, из них 4 статьи - в рецензируемых журналах, рекомендованных ВАК, и еще одна, цитируемая в SCOPUS.

Структура и объем работы. Диссертация изложена на 147 страницах и состоит из введения, трех глав, заключения и списка литературы, содержащего 163 наименования.

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

1) предложен подход к построению методов отсечений для задач нелинейного программирования, который позволяет включать в эти методы различные процедуры обновления аппроксимирующих множеств с целью периодического отбрасывания накапливающихся отсекающих плоскостей. Упомянутый подход основан на введенных в диссертационной работе критериях оценки качества аппроксимирующих множеств в окрестности итерационных точек;

2) на основе этого подхода для задач условной минимизации с различными условиями задания целевой функции и области ограничений разработаны два метода отсечений с аппроксимацией допустимой области, четыре метода отсечений, использующих аппроксимацию надграфика целевой функции, и метод проектирования точки на выпуклое множество, в которых заложена возможность периодического обновления аппроксимирующих множеств путем отбрасывания произвольного числа любых построенных секущих плоскостей;

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

4) для большинства методов отсечений в диссертации при дополнительных условиях на целевую функцию и функции ограничений получены оценки точности решений и оценки скорости сходимости для последовательности приближений;

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

6) показано, что в предлагаемых методах на этапе построения итерационных точек есть возможность применения параллельных вычислений.

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

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

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

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

В § 1.1 предлагается метод отсечений для решения задачи

min{/(a;) : х G D}, (1)

где f(x) - непрерывная в n-мерном евклидовом пространстве Яп функция, D = {х G Ra : fj(x) < 0, j G J}, fj(x), j G J = {1 ,...,m}, - выпуклые в R„ функции. Предполагается, что для всех j G J множества Dj = {ж G Rn fj(x) < 0} имеют непустую внутренность int Dj.

Положим F(x) ~ max{/j(x) : j G J}, De - {z G Rn : F(x) < г}, где £ > 0, К = {0,1,...}, W(x, Dj) = {a G Rn : {a,z - x) < 0 Vz G Dj, ||a|| = 1}.

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

Метод 1.1. Строится выпуклое замкнутое множество Mq С Rn, содержащее точку х* = arg min {/(х) : х G D}. Выбираются точки v3 G int -D^ для всех j G J. Задается число fo ^ 0. Полагается к = 0, г = 0.

1. Находится точка i/i G Мг р|{х G Rn : f(x) < f(x*)}, полагается J% = {j G J : iji Dj}. Если Ji = 0, то yi - решение задачи.

2. Для каждого,?' G Ji на интервале (v3,yi) определенным образом находится точка zf (ji int Dj. Выбирается некоторое подмножество Hi С J,-.

3. Для каждого .7 6 Я* выбирается конечное множество А\ С ,

и полагается Мг+1 = П {я 6 Иг, : {а, х - г?} < 0 Уа € А]}. Множество

<2; задается следующим образом. Если эд ^ то <5; = В противном случае полагается г^ = г, х^ = у{к, и выбирается выпуклое замкнутое множество

= ^ такое, что х* е <5».

4. Задается число £к+\ > 0, значение к увеличивается на единицу. Далее следует переход к п. 1 при г, увеличенном на единицу.

Качество аппроксимации допустимой области множествами Мг определяется в окрестности точек ?/; условием £ Бек. На шаге г = 1к, где для у\ выполняется это условие, качество аппроксимации считается удовлетворительным для фиксирования точки и за счет практически произвольного выбора множества = происходит обновление множества На тех итерациях, на которых для точек у^ выполняется условие т/г ф. Ц^, качество аппроксимации считается недостаточным для обновления, т. е. до шага г = отсекающие плоскости будут накапливаться.

В методе 1.1 можно использовать различные процедуры обновлений погружающих множеств М,. Пусть yi £ Б£к. Положим <5, = Мп, где 0 < < г = г^. Тогда при всех гг- = 0,..., г включение х* £ Qi выполняется, и в качестве (¿{к можно выбирать любое из построенных к ik-oщ шагу множеств Мо,..., M¿t. В частности, можно положить <5г = Мо, тем самым при г = г^, к £ К, произойдет полное обновление аппроксимирующего множества Мгк+\.

В случае выбора чисел £к положительными доказано, что для каждого к £ К найдется номер г = при котором выполнится включение уг £ Юек, а значит, представится возможность обновления погружающего множества.

Теорема 1. Пусть последовательность {х^}, к £ К, построена предложенным методом с условием, что > О для всех к е К, и ек —>■ 0 при к оо. Тогда любая предельная точка этой последовательности принадлежит множеству решений задачи (1), а если для всех к £ К выполняются неравенства /(Хк+г) > f{xk), то вся последовательность {х&}, к £ К, сходится к множеству решений.

Если /(х) выпукла, ¡¿(х), j £ ,/, сильно выпуклы с константами сильной выпуклости ^ соответственно, множество Б удовлетворяет условию Слейте-ра, и любая точка абсолютного минимума функции /(х), при наличии таковых, не принадлежит множеству цй Д то получены оценки точности решения \\хк — < 4, где 6к = уек/ц . Если к тому же /(х) удовлетворяет условию Липшица, то при каждом к £ К справедлива оценка - /(х*) | < Ьбк■ Если £к = 1 /кр, где р > 0, то на основе приведенных выше оценок для {х^}, к £ К,

Далее, в § 1.2 предлагается метод отсечений для решения задачи (1), в которой область ограничений имеет более общий вид:

где Б', Б" - выпуклые замкнутые в Кп множества, причем второе из них может заведомо иметь пустую внутренность.

В отличие от метода 1.1 в данном методе аппроксимируется не множество!), а содержащее допустимую область множество Б'. Метод отличается от разработанного в § 1.1 метода также способами построения аппроксимирующих множеств. А именно, погружающее множество М,-+1 получается путем отсечений от Мг точки у{ плоскостями, построенными с помощью субградиентов функций, определяющих множество Б'. Кроме того, в этом методе по сравнению с предыдущим предусмотрены более широкие возможности для выбора итерационых точек основной последовательности. За счет этих возможностей допустимо построение на основе этого метода отсечений некоторых смешанных алгоритмов, причем сходимость таких смешанных алгоритмов будет гарантирована сходимостью предложенного метода отсечений. Метод из § 1.2 характерен тем, что также предусматривает возможность периодического обновления аппроксимирующих множеств на тех итерациях, где качество аппроксимирующего множества становится удовлетворительным.

При дополнительных предположениях на целевую функцию и на функции, определяющие область Б', в случае Б" = Пп получены оценки точности решения и оценки скорости сходимости, аналогичные приведенным в§ 1.1.

В § 1.3 предлагается метод отсечений для нахождения проекции точки у 6 Яп на выпуклое множество Б, заданное в виде (2). На каждой итерации метода определенным образом строится многогранное множество, аппроксимирующее область Б', и приближение получается путем проектирования точки у на пересечение этого аппроксимирующего множества с множеством Б". В случае, если Б" задано системой линейных уравнений или неравенств, построение приближения не вызывает большого труда, так как задача проектирования решается известными алгоритмами за конечное число шагов. Как и в методах из предыдущих параграфов, в этом методе проектирования тоже заложена возможность обновления аппроксимирующих область Б' множеств за счет отбрасывания дополнительных ограничений.

В § 1.4 для задачи (1) строится еще один метод отсечений с аппроксимацией области ограничений, который отличается от методов из §§ 1.1,1.2 тем, что до-

(2)

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

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

Первый параграф второй главы посвящен решению задачи минимизации выпуклой в Пп дискретной функции максимума /(х) на выпуклом замкнутом множестве Б с Ип. Предлагаемый для решения задачи метод заключается в следующем. На г-ом шаге (г > 0) находится решение (2/;,7г) следующей задачи:

тш{7 \xeGi, (х, 7) (Е Ми 7 > 7г}, (3)

где Мг - множество, аппроксимирующее надграфик целевой функции, -некоторое подмножество области Д 7,- < /* = тт{/(ж) : х £ Б}. Если разность ¡{уг) — 7^ достаточно мала, то качество аппроксимации надграфика множеством Mi считается удовлетворительным. В таком случае ?/; фиксируется в качестве точки основной последовательности приближений, и происходит обновление аппроксимирующего множества М¡. В противном случае строится

очередное аппроксимирующее множество Mj+i путем отсечения от Мг- точки (УьЪ)-

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

В параграфе 2.2 предлагается метод отсечений для решения задачи (1) с выпуклой функцией f(x) на выпуклом множестве D.

Положим epi (/, G) = {(£,7) 6 Rn+1 : х е G,4 > f{x)}, где G С Я», W{u,Q) = {а G Rn+i : (a,z - и) < 0 Vz € Q, ||а|| = 1}, где Q С iW

Предлагаемый метод вырабатывает последовательности {yt}, г G К, {хк}, к G К, и заключается в следующем.

Метод 2.2. Выбираются точки tP € int epi (/, Rri) для всех j G J, выпуклое ограниченное замкнутое множество Gq С D, содержащее точку х* = arg min {f(x) : х 6 D}, выпуклое замкнутое множество Mq с Rn+i такое, что (х*, f(x*)) G Mq. Задаются £q > 0, 7о < f{x*), и полагается г = 0, к = 0.

1. Отыскивается точка (y,,7i), где у, € Rru G R\, как решение задачи (3). Если ¡(уЦ = 7,, то yi - решение исходной задачи.

2. Если выполняется /(у;) — 7* > то полагается Qi = Mi, щ = у,, и следует переход к п. 4. В противном случае выполняется п. 3.

3. Выбирается выпуклое замкнутое множество Qi С Rri+i так, чтобы выполнялось включение (x*,f(x*)) G Qi. Выбирается точка хк G Rn, удовлетворяющая условиям хк G Gi, f(xk) < f{yi). Полагается ik = г, ак = -yik, щ = щк = хк, задается ек+\ > 0, значение к увеличивается на единицу.

4. Для каждого j G J в интервале (V, {щ, 7г)) некоторым образом выбирается точка z? int epi (/, Rn).

5. Для каждого j G J выбирается конечное множество А\ с W(z{, epi (f,Rn)), и полагается

Mi+1 = Qif]Ti, где Т{ = П {(я, T) G Rn+i ■ (а, (x, 7) - zj) < 0 Va G Aj).

jeJ

6. Выбирается выпуклое замкнутое множество Gi+\ С Gq, содержащее точку х*. Задается число 7,+i из условия 70 < 7i+i < /*. Значение г увеличивается на единицу, и следует переход к п. 1.

Качество аппроксимации надграфика функции множествами Mi определяется в окрестности точек у; величиной /(уг) — 7t. На итерациях, где для yi выполняется неравенство /(у;) — 7,- > ек, качество аппроксимации считается

недостаточным для фиксирования точки ж*. На таких итерациях множества Qi выбираются совпадающими с Mi, и тогда при формировании множеств Mj+i отсекающие плоскости накапливаются. На шаге г = ц, на котором выполняется fiUi) ~ Ii — £к, качество аппроксимации считается удовлетворительным, точка Хк зафиксируется согласно условию f(xk) < f(ijik), и за счет практически произвольного выбора множества Qi = Qik при желании происходит обновление аппроксимирующего множества Mik+j.

На основе критерии оценки качества аппроксимации надграфика можно строить различные приемы обновления аппроксимирующих множеств. Пусть для точки (yi, т,) выполняется неравенство f(iji) — 7i < ек■ В таком случае согласно п. 3 метода 2.2 множество Qi = Qik выбирается удовлетворяющим лишь включению (x*,f(x*)) £ Qi. Положим, например, Qi = Rn+1 или Qi = Mq. Тогда, соответственно, Mi+1 = Ti или Mi+1 = Mof|Tj, и в формировании Mi+1 не участвуют ни одна из построенных ранее отсекающих плоскостей. При условии f(iji) — 7; < множество Qi = Qik можно задать и в виде Qi = Мп, где

0 < Ti < i = ik- В таком случае при построении множества Mi+\ отбрасывается только часть накопленных к шагу i~ik отсечений.

Доказано, что для каждого к £ К существует номер г — ik, при котором выполнится неравенство /(i/j) ~Ъ ^ £к, а следовательно, появится возможность обновления аппроксимирующего множества.

Теорема 2. Пусть последовательность {{хк, к £ К, построена методом

с условием, что -)• 0, ^ -> оо. Тогда lim f{xk) = f{x*), lim <?к = f{x*).

keK keK

Условия выбора в п. 3 точек Хк дают большую свободу для их построения.

Эти уловия, во-первых, позволяют привлекать для нахождения точек Хк, отличных от у;, многие известные релаксационные методы условной минимизации, и, во-вторых, дают возможность построения на основе метода 2.2 различных смешанных алгоритмов. Например, считая jjik точкой начального приближения, можно для минимизации f(x) на множестве G,k проделать, начиная с yik, определенное число шагов известным градиентным или субградиентным алгоритмом в зависимости от свойств целевой функции. Таким образом, на основе предложенного метода отсечений будет построен новый алгоритм, причем сходимость такого смешанного алгоритма является обоснованной в силу теоремы 2.

Общность условий задания точек Хк в методе 2.2 позволяют также применить на этапе их нахождения параллельные вычисления. А именно, можно на шаге

1 = ik любыми алгоритмами параллельно построить некоторое число вспомогательных точек wl,...,w[,l> 1, таких, что иРк £ Gik> f{wß < f{yik), j = l,...,l, а затем искомую точку Хк выбрать из условия f(xk) = min{/(w^),..., f(w[)}.

В § 2.3 предлагается модификация известного метода уровней для решения задачи (1), где /(ж) — выпуклая функция, а Б — выпуклое ограниченное замкнутое множество. Главное отличие предлагаемого метода от известного заключается в том, что в нем заложена возможность периодического отбрасывания накапливающихся в процессе счета отсекающих плоскостей, что делает предложенную модификацию привлекательной с практической точки зрения. Другое немаловажное отличие этого метода от известного заключается в более общем способе задания итерационных точек. В частности, в предлагаемом методе при построении приближений можно привлекать параллельные вычисления.

Далее в § 2.4, основываясь на способе построения аппроксимирующих множеств из § 2.2, разрабатывается еще один метод отсечений для задачи (1) с выпуклой целевой функцией. В методе при построении итерационных точек происходит аппроксимация множествами М,- надграфика не целевой функции /(ж), а некоторой вспомогательной функции д{х). Существенным отличием предлагаемого метода от методов, построенных в предыдущих параграфах, является заложенный в нем новый критерий оценки качества аппроксимирующих множеств А/,-, а значит, и критерий отбрасывания отсекающих плоскостей. А именно, как только итерационная точка из М{ становится достаточно близка к надграфику функции д(х), качество аппроксимации считается приемлимым, и происходит обновление множества М^

Данный метод за конечное число шагов позволяет найти ^-решение задачи (1). Если же после нахождения ¿-решения процесс построения приближений продолжается, то любая предельная точка итерационной последовательности будет принадлежать множеству решений. Отметим, что данный метод, как и многие предыдущие, позволяет строить смешанные алгоритмы с привлечением других известных методов условной минимизации. Кроме того, при построении приближений в методе можно использовать и параллельные вычисления.

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

В § 3.1 предлагается общий метод отсечений для задачи (1), где /(ж) — вы-

пуклая функция. Метод строит последовательность приближений следующим образом. На г-ом шаге метода находится точка (у*, 70 как решение задачи

1шп{7 : (х, 7) 6 Ми х€ С*, 7 > а},

где М{ С Ип+х - множество, аппроксимирующее надграфик целевой функции, б* С Яп - множество, аппроксимирующее область ограничений в окрестности решения исходной задачи, а - нижняя оценка значения /*. Компонента yi, найденной точки, принимается за текущую итерационную точку. Далее строятся очередные аппроксимирующие множества 1 и Сг+1. Первое из них — путем отсечения от множества М* точки (уг-, 7,-), а второе — на основе отсечения от приближения у{ в случае у{ ^ Б. Отсечения в предлагаемом методе строятся на основе обобщенно-опорных элементов к надграфику целевой функции или к допустимой области. Предлагаются различные варианты выбора начальных погружающих множеств, а также различные способы построения отсекающих плоскостей.

На основе идеи одновременной аппроксимации надграфика целевой функции и области ограничений в § 3.2 предлагается метод отсечений с обновлением аппроксимирующих множеств для задачи выпуклого программирования (1) с областью О, заданной в виде (2), где Ю' = {х € Яп : ^(х) < 0}, Р(х) — выпуклая в Пп функция.

Пусть = {х € Яп : Р(х) < е}, /* = тш{/(х) : х е £>}, Х*(е) = {х е £> : 1{х) < /* + е}, где £ > 0, х* = аг§шт {/(х) : х € £>}.

Метод 3.2. Выбираются выпуклые замкнутые множества Мо С (?о С Яп+1 такие, что х* е М0, ер1 (/, Яп) С (?о, и для любой точки (х, 7) 6 Со, где х £ Мо, выполняется неравенство 7 > 7 > —оо. Задаются числа £о > 0. ¿о > 0, и полагается г = 0, к = 0.

1. Отыскивается точка (уг-,7,), где уг 6 Яп, 7г £ йь как решение задачи

шт{7 : х 6 Мг П £)", (х, 7) е

Если yi € В', и /(уг) = 7г, то у; - решение исходной задачи.

2. Если выполняется у{ £ И' и /(?/г) - 7; < <5^, то yi £ Х*(6к)- Далее процесс либо завершается, либо следует переход к п. 3.

3. Строятся множества М;+1, £¿+1 способами, зависящими от выполнения для точки (?/г,7г) следующих условий.

а) Пусть (?/г,7г) такова, что у,- ^ Тогда строятся определенным образом очередные аппроксимирующие множества М,-+1, Множество - на основе отсечения приближения yí от М,, а £7г+1 - путем отсечения точки (уг-, 7,)

ОТ С,.

б) Пусть точка (?/i,7t) такова, что у; G D'Ek, но при этом выполняется неравенство f(yi) - 7i > 5к. Тогда, во-первых, полагается Ml+\ = М,-, если уг G .D', либо множество Mt-+i строится согласно п. За), если у, G D[k \ D'. Во-вторых, строится множество Gj+i также, как и в п. За).

в) Пусть для точки (j/i,7i) одновременно выполняются yi G D's и /(у*) — 7г < Во-первых, если yi G D', то полагается Mj+i = M;, а в противном случае

определенным образом строится выпуклое замкнутое множество Mj+j Ç Mo такое, что х* G Mî+i, и уг ^ Во-вторых, строится выпуклое замкнутое

множество Si С Go таким образом, чтобы epi (/, /?„) с Sj, далее некоторым образом выбирается множество Gî+i С Sj. В-третьих, полагается ik = i,xk = yik, сгк = 7ik, задаются e/t+i > 0, > 0, и значение к увеличивается на единицу.

4. Следует переход к п. 1 при i, увеличенном на единицу.

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

За счет выбора множеств Qi, Si можно проводить обновления погружающих множеств путем отбрасывания накапливающихся отсекающих плоскостей. Пусть при некотором i = гк для точки (у;,7г) выполнились одновременно условия У(уг) 7г < h, Ui G D'£k. Положим, например, Q,- = Qik = MT, S{ = Sik = Gh где 0 < r < ik, 0 < l < ik. Поскольку Mr С M0, G; С G0 для всех г = 0,..., ik, I = 0,...,ik, а кроме того, x* G Mr, epi(f,Rn) С G\ для всех г = 0,...,ik, I = 0,... ,ik, то в качестве Qik можно выбрать любое из построенных к ik-ому шагу множеств Mo,..., Mik, а в качестве S,t — любое из множеств Go,Gik. В частности, если положить Qik = М0, S;t = Go, то произойдет отбрасывание всех накопившихся к шагу i — ik отсекающих плоскостей, и множества Mi+i, Gj+i построятся на основе множеств Mo, Go путем отсечения точек у,, (yj, 7¿) от Mo и Go соответственно.

При построении очередных множеств Mj+i в отсечениях используются субградиенты функции F(x), а при построении Gj+1 - субградиенты функции f(x).

В параграфах 1.5, 2.5 и 3.3 представлены результаты численных экспериментов, которые проводились с целью исследования методов, разработанных в §§ 1.1, 1.2, 2.1, 2.2, 3.3. Указанные методы программно реализованы на языке программирования С++ в среде Microsoft Visual Studio 2008. Методы из §§ 1.1,1.2,3.3 тестировались на задачах, в которых допустимая область задавалась нелинейными функциями. Остальные из указанных методов исследовались на примерах, в которых область ограничений являлась многогранником,

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

Работы автора по теме диссертации в журналах, входящих в перечень ВАК и цитируемых в SCOPUS

[1] Яруллин Р. С. Алгоритм отсечений с аппроксимацией надграфика [Текст] / И.Я. Заботин, P.C. Яруллин // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки.

- 2013. - Т. 155, N 4. - С. 48 - 54.

[2] Яруллин P.C. Об одном подходе к построению алгоритмов отсечений с отбрасыванием отсекающих плоскостей [Текст] / И.Я. Заботин, P.C. Яруллин // Изв. вузов. Матем. - 2013. - N 3. - С. 74 - 79.

[3] Яруллин Р. С. Метод отсечений с обновлением погружающих множеств и оценки точности решения [Текст] / И.Я. Заботин, P.C. Яруллин // Учен. зап. Казан, ун-та. Сер. Физ.-матем. науки. - 2013. - Т. 155, N 2. - С. 54 - 64.

[4] Яруллин P.C. Метод отсечений с обновлением аппроксимирующих множеств и его комбинирование с другими алгоритмами [Текст] / И.Я. Заботин, P.C. Яруллин // Известия Иркутского гос. ун-та. Сер. «Математика». - 2014. -Т. 10. - С. 13 - 26.

[5] Yarullin R.S. А cutting method for finding discrete minimax with dropping of cutting planes [Electronic resource (SCOPUS)] / I.Ya. Zabotin, R.S. Yarullin // Lobachevskii Journal of Mathematics. - 2014. - Vol. 35, N 2. - P. 157-163.

- URL: http://www. Springer.com/matheraatics/journal/12202 (дата обращения: 22.10.2014).

Работы автора по теме диссертации в прочих изданиях

[6] Яруллин P.C. Некоторые процедуры погружений-отсечений и их применение в методах условной минимизации [Текст] / И.Я. Заботин, P.C. Яруллин // Информационная бюллетень Ассоциации матем. программирования . - № 12.

- тезисы докл. XIV Всерос. Конф. «Математическое программирование и приложения» (Екатеринбург, 28 фев. - 4 мар. 2011 г.). - Екатеринбург: УНЦ УПИ. -2011. - С. 40.

[7] Яруллин P.C. Алгоритм условной минимизации, допускающий параллельные вычисления [Текст] / P.C. Яруллин // Итоговая научно-образователь ная конференция студентов Казанского университета 2011 года. - 2011. - С. 110 -111.

[8] Яруллин Р. С. Об одном методе условной минимизации, допускающем параллельные вычисления [Текст] / И.Я. Заботин, P.C. Яруллин // Труды XV Байкальской Междунар. Школы-семинара «Методы оптимизации и их приложения» (Байкал, 23 - 29 июня 2011 г.) - Т. 2, «Математическое программирование» - Иркутск: РИО ИДСТУ СО РАН. - 2011. - С. 87 - 91.

[9] Яруллин Р. С. Алгоритм отсечений для задачи математического программирования, допускающий параллельные вычисления [Текст] / И.Я. Заботин, P.C. Яруллин // Сборник трудов всероссийской конференции «Статистика. Моделирование. Оптимизация» (Челябинск, 28 нояб. - 3 дек. 2011 г.). - Челябинск: Издат. Центр ЮУрГУ. - 2011. - С. 114 - 117.

[10] Яруллин P.C. Алгоритмы отсечений без вложения погружающих множеств [Текст] / И.Я. Заботин, P.C. Яруллин // Проблемы оптимизации и экономические приложения : материалы V Всероссийской конференции (Омск, 2 -6 июля 2012 г.). - Омск: Изд-во Ом. Гос. Ун-та, 2012. - С. 177.

[11] Яруллин P.C. Алгоритм проектирования точки, использующий аппроксимирующие множества [Текст] / И.Я. Заботин, P.C. Яруллин// Труды девятой Всероссийской конференции «Сеточные методы для краевых задач и их приложения» (Казань, 17 - 22 сентября 2012 г.). - Казань: Казан, ун-т, 2012. - С. 131 - 136.

[12] Яруллин P.C. Об одном методе отсечений с обновлением погружающих множеств и его численном исследовании / P.C. Яруллин // Республиканский конкурс научных работ студентов и аспирантов на соискание премии им. Н.И. Лобачевского (Казань, 9-12 апреля 2013 г.), РМОО «Лига студентов Республики Татарстан». - 2013. - С. 34 - 36.

[13] Яруллин P.C. Алгоритмы отсечений без вложения аппроксимирующих множеств и оценки точности решения [Текст] / И.Я. Заботин, P.C. Яруллин // Междунар. конференция «Дискретная оптимизация и исследование операций (DOOR - 2013)» (Новосибирск, 24 - 28 июня 2013 г.). - Новосибирск: Изд-во Ин-та математики, 2013. - С. 48.

[14] Яруллин P.C. Алгоритм отсечений с аппроксимацией надграфика без вложения погружающих множеств [Электронный ресурс] / И.Я. Заботин, P.C. Яруллин // 37-ая конференция-школа молодых ученых «Информационные технологии и системы (ИТиС'13)» (Калининград, 1 -6 сентября 2013 г.). М.: ИППИ

РАН, 2013. - С. 8 - 11. - Режим доступа: http://itas2013.iitp.ru/ru /search.html (дата обращения: 22.10.2014).

[15] Яруллин P.C. Об одном методе отсечений с отбрасыванием отсекающих плоскостей [Текст] / И.Я. Заботин, P.C. Яруллин // X Всероссийская конференция ММРО-16 (Казань, 6-10 октября 2013 г.). - М.: Торус Пресс, 2013. - С. 81.

[16] Яруллин Р. С. Метод отсечений с аппроксимацией надграфика и оценка точности решения [Текст] / И.Я. Заботин, P.C. Яруллин // XVII международная конференция «Проблемы теоретической кибернетики» (Казань, 16 - 20 июня 2014 г.). - Казань: Отечество, 2014. - С. 92 - 95.

[17] Яруллин P.C. Метод отсечений с обновлением аппроксимирующих множеств и его комбинирование с другими алгоритмами [Текст] / И.Я. Заботин, P.C. Яруллин // Тезисы докладов XVI Байкальской международной школы-семинара «Методы оптимизаций и их приложения» (Байкал, 30 июня - 6 июля 2014 г.). - Иркутск: ИСЭМ СО РАН, 2014. - С. 106.

[18] Яруллин Р. С. Алгоритм отсечений на основе одновременной аппроксимации допустимой области и надграфика целевой функции [Текст] / P.C. Яруллин // Труды X Международной конференции «Сеточные методы для краевых задач и их приложения» (Казань, 24 - 29 сентября 2014 г.). - Казань: Казан, ун-т, 2014. - С. 683 - 687.

[19] Яруллин P.C. Метод отыскания проекции точки, основанный на процедурах отсечений [Текст] / И.Я. Заботин, О.Н. Шульгина, P.C. Яруллин// Труды X Международной конференции «Сеточные методы для краевых задач и их приложения» (Казань, 24 - 29 сентября 2014 г.). - Казань: Казан, ун-т, 2014. - С. 300 - 304.

[20] Яруллин Р. С. Об одном методе отсечений на основе аппроксимации надграфика с отбрасыванием секущих плоскостей и его численном исследовании / P.C. Яруллин // Республиканский конкурс научных работ студентов и аспирантов на соискание премии им. Н.И.Лобачевского (Казань, 2014 г.), РМОО «Лига студентов Республики Татарстан». - 2014. - С. 65 - 67.

[21] Яруллин P.C. Об одном алгоритме отсечений для задачи выпуклого программирования [Электронный ресурс] / И.Я. Заботин, P.C. Яруллин // 38-ая конференция-школа молодых ученых «Информационные технологии и системы (ИТиС'14)» (г. Нижний Новгород, 1 - 5 сентября 2014 г.). - М.: ИППИ РАН, 2014. - С. 2 - 5. Режим доступа: http://itas2014.iitp.ru/ru/search.html (дата обращения 22.10.2014).

Подписано в печать 07.05.2015. Бумага офсетная. Печать цифровая. Формат 60x84 1/16. Гарнитура «Times New Roman». Усл. печ. л. 1,05. Уч.-изд. л. 0,14. Тираж 100 экз. Заказ 32/5

Отпечатано с готового оригинал-макета в типографии Издательства Казанского университета

420008, г. Казань, ул. Профессора Нужина, 1/37 тел. (843) 233-73-59,233-73-28