Введение к работе
Актуальность темы. Многоэкстремальные задачи оптимизации широко встречаются в различных областях технического и экономико-математического моделирования. Стандартные методы нелинейного программирования не приводят к успеху при решении таких задач. В большинстве случаев причиной этого эффекта является именно многоэкстремальность, т.е. наличие нескольких локальных экстремумов. Использование таких локальных понятий как градиент, субградиент, матрица вторых производных и т.д. позволяет надеяться лишь на получение локального оптимума. Главная проблема стандартных методов - отсутствие возможности конструктивной проверки глобальной оптимальности полученного решения. Более того, в настоящее время не существует вычислительно эффективных (т.е., не требующих экспоненциального числа арифметических операций для своей проверки) необходимых условий глобальной оптимальности за исключением тривиальных или специальных задач, решение которых очевидно.
Тем не менее, к настоящему времени в области теории и методов глобальной оптимизации получены серьезные результаты. Прежде всего выяснена структура всех практически значимых невыпуклых функций. Оказалось, что невыпуклая непрерывная функция «почти всегда» может быть представлена в качестве разности двух выпуклых функций. Такие функции впервые появились в работах А.Д. Александрова, Е.М. Ландиса в конце 40-х и начале 50-х годов и в работах П. Хартмана (P. Hartman) в конце 50-х годов прошлого века. Термин d.c. (difference of convex -разность выпуклых) функция введен в работах Ж.-Б. Ириарта-Уррути (J.-B. Hiriart-Urryty) и X. Туя (Н.Тиу) в середине 80-х годов прошлого века и используется с тех пор всеми авторами как общепринятый в исследованиях по глобальной оптимизации. Структурные свойства d.c. функций привели к разработке широкого класса эффективных методов глобальной оптимизации, которые в специальных случаях (таких, как задачи размещения) позволяют решать за приемлемое время задачи с несколькими сотнями переменных с доказательством глобальной оптимальности полученного решения. Н. Сахинидисом (N. Sahinidis) и М. Тавармалани (М. Tawarmalani) на основе теории и методов оптимизации d.c. функций был создан решатель (solver) BARON - пакет прикладных программ, который в настоящее время признан одним из самых лучших для практического решения задач глобальной оптимизации. В России интенсивные исследования в
области d.c. оптимизации ведутся А.С. Стрекаловским и его учениками. Основное направление этих исследований составляют разработка критериев глобальной оптимальности и развитие методов невыпуклой оптимизации на основе этих критериев.
Другой класс задач глобальной оптимизации составляют задачи так называемой липшицевой оптимизации (Lipschitz optimization). Напомним, что функцию, удовлетворяющую условию Липшица, называют липшицевой функцией. Задачу минимизации липшицевой функции на множестве, заданном ограничениями-равенствами и ограничениями-неравенствам с липшицевыми функциями в левых частях, называют задачей липшицевой оптимизации. Исторически, задача липшицевой оптимизации была первой задачей глобальной оптимизации. На эту тему существует большое количество публикаций, в которых описаны различные методы липшицевой оптимизации. Среди основных авторов стоит назвать С.А. Пиявского, Ю.Г. Евтушенко, Р.Г. Стронгина, В.П. Гергеля, Я.Д. Сергеева, А.Г. Сухарева. Из зарубежных авторов существенных успехов добились Я. Пинтер (J. Pinter), П. Хансен (P.Hansen), В. Джамар (В. Jaumard), Д. Джонс (D. Jones). Многие методы широко протестированы и хорошо зарекомендовали себя на практике. В связи с этим упомянем здесь еще один коммерческий решатель LGO, разработанный Я. Пинтером. Центральным направлением современной липшицевой оптимизации служит разработка параллельных алгоритмов. Одним из обширных приложений липшицевой оптимизации является оптимизация функций, заданных неявно. Как обычно, под этим понимается то, что значения оптимизируемой функции получаются в результате решения какой-либо другой оптимизационной или вычислительной задачи или требуют проведения затратного технического эксперимента и т.д. Константа Липшица в этих случаях вычисляется, а чаще аппроксимируется, адаптивно (т.е. в ходе решения задачи). На эту тему существует достаточно обширная литература.
Теория и методы оптимизации постоянно развиваются и в последние 10-15 лет появились новые направления перспективных исследований таких, как полуопределенное программирование (Semidefinite programming - SDP) и копозитивное программирование, в основном связанные с задачами невыпуклого квадратичного программирования. В рамках SDP исследуются задачи линейного программирования, в которых переменные являются симметричными матрицами, скалярное произведение есть след произведения двух матриц, условия неотрицательности переменных заменяется на условие положительной полуопределенности переменных матриц. Например,
задача, двойственная в обычном смысле задаче невыпуклого квадратичного программирования с квадратичными функциями-ограничениями (в данном контексте такие задачи впервые рассматривались Н.З. Шором) может быть представлена как задача SDP программирования. Применяя современные методы SDP программирования, можно быстро получать оценки снизу глобального минимального значения целевой функции, а в случае отсутствия разрыва двойственности находить и глобальное решение.
И все же задачи глобальной оптимизации явно или аналитически заданных функции все еще являются трудно решаемыми. С этой точки зрения интерес представляют подходы к минимизации многоэкстремальных функций, основанные на других идеях и конструкциях, чем те, что были упомянуты выше. К ним относится идея представления оптимизируемой функции в виде верхней огибающей или поточечного супремума вспомогательного семейства непрерывных функций. Идея эта продиктована желанием обобщить свойство выпуклой функции быть представленной в виде верхней огибающей семейства аффинных функций. В выпуклой оптимизации это свойство привело к разработке эффективных вычислительных схем, ярким представителем которых является метод опорных плоскостей. Переход от выпуклых функций к невыпуклым требует замены множества аффинных функций другими семействами. Первой работой в этом направлении можно считать статью Е. Беккенбаха, опубликованную в 1937 г. Следующей, существенной на взгляд автора, является монография С.С. Кутателадзе и A.M. Рубинова «Двойственность Минковского и ее приложения», опубликованная в 1972 году. Затем последовал ряд работ зарубежных авторов таких, как А. Бен-Тал (A. Ben-Tal), А. Бен-Израэль (A. Ben-Israel), С. Долеккий (S. Dolecky), Д. Паллашке (D. Pallaschke), С. Ролевич (S. Rolewicz), И. Зингер (I. Singer). Основное внимание в этих работах было уделено теоретическим результатам. Особо следует выделить монографию A.M. Рубинова «Abstract convexity and global optimization» (2000 г.), в которой теоретические результаты присутствуют наравне с практическими алгоритмами глобальной оптимизации. Возможность рассмотрения семейства вогнутых непрерывных функций в качестве вспомогательного семейства была впервые отмечена В.П. Булатовым в 1984 году, им же был введен термин «функция, имеющая вогнутую миноранту». Дальнейшим существенным вкладом в этом направлении была статья В.И. Норкина «О методе Пиявского для решения общей задачи глобальной оптимизации» (1992 г.). Взгляд на невыпуклую функцию, как на функцию, являющуюся верхней огибающей некоторого семейства вогнутых непрерывных функций,
оказался плодотворным и позволил разработать новые эффективные методы глобальной оптимизации.
Данная диссертационная работа является продолжением исследований, начатых в монографиях и статьях В.П. Булатова, В.И. Норкина и A.M. Рубинова. Основные усилия в предлагаемой работы были направлены на исследование свойств функций, имеющих вогнутую непрерывную опорную функцию-миноранту, и разработку эффективных численных методов минимизации таких функций.
Целями работы являются:
проведение сравнительного анализа функций, имеющих вогнутую опорную функцию-миноранту, с другими классами функций, широко использующимися в оптимизации;
разработка конструктивных способов построения опорных вогнутых функций-минорант и опорных выпуклых функций-мажорант;
разработка методов локальной оптимизации, использующих выпуклые опорные функции-мажоранты;
развитие методов отсечений для глобальной минимизации функций с вогнутыми опорными минорантами;
разработка новых методов ветвей и границ с использованием вогнутых опорных функций-минорант;
использование методов глобальной оптимизации с вогнутыми минорантами для решения задач вычислительной математики и системного анализа.
Научная новизна. В диссертации впервые широко исследован класс функций имеющих вогнутую опорную функцию-миноранту, а также его подкласс, образованный функциями, имеющими в дополнении к вогнутой миноранте выпуклую опорную функцию-мажоранту.
Показано, что использование выпуклых опорных функций-мажорант позволяет существенно расширить класс методов локальной оптимизации, сходящихся к необходимым условиям оптимальности.
Впервые введено и описано понятие автоматической глобальной оптимизации.
Исследованы условия сходимости методов отсечений по вогнутой
миноранте в задачах непрерывной глобальной оптимизации. Предложен новый тип глубоких отсечений в задачах вогнутого и 0-1 линейного программирования.
Разработаны новые методы ветвей и границ, использующих методику целочисленного программирования, классическую теорию двойственности, методику, комбинирующую ветви и границы с отсечениями по вогнутой миноранте.
Описано применение опорных функций-минорант и опорных функций-мажорант к задачам линейного параметрического программирования. Предложены редукции некоторых задач дискретного программирования к задаче глобальной минимизации функции с вогнутой минорантой.
Методы исследования. В диссертационной работе использованы теория необходимых условий оптимальности, выпуклого анализа, выпуклого программирования, методология разработки методов ветвей и границ, теория игр, методы целочисленного программирования.
Основные результаты диссертации, выносимые на защиту.
-
Исследованы основные свойства функций, имеющих вогнутую опорную миноранту и выпуклую опорную мажоранту на компактном подмножестве конечномерного евклидова пространства. Проведен сравнительный анализ этих функций с полунепрерывными снизу функциями, липшицевыми функциями, функциями, представимыми в виде разности двух выпуклых функций, слабовыпуклыми и выпуклыми функциями. Сформулированы необходимые условия оптимальности в терминах выпуклых опорных мажорант. Описаны методы локальной оптимизации в невыпуклых задачах математического программирования, обоснована их сходимость к стационарным точкам. Разработана технология конструктивного построения выпуклых мажорант и вогнутых минорант для широкого класса явно заданных функций.
-
Детально описана и протестирована технология автоматической глобальной оптимизации явно заданных одномерных функций. Разработана и численно протестирована методика нахождения корней нелинейных одномерных уравнений, основанная на понятии вогнутой опорной миноранты. Обоснована сходимость.
-
Исследована сходимость методов отсечений в Ш.п и в Шп+ для глобальной оптимизации функций с вогнутой минорантой. Предложена и обоснована модификация этих отсечений, основанная на понятии вогнутого продолжения и существенно улучшающая работу методов отсечений. Разработан метод, комбинирующий отсечения в WLn и в Mn+1. Проведено численное тестирование. Предложен новый тип глубоких отсечений для решения задач 0-1 линейного программирования.
-
Разработаны методы ветвей и границ с вогнутыми минорантами, которые: сводят вспомогательные задачи глобальной оптимизации к задачам 0-1 программирования, используют двойственные оценки, а также применяют метод отсечений в Mn+1.
-
Предложена методика анализа параметрических задач линейного программирования и задач равновесного программирования на основе методов оптимизации с вогнутыми минорантами и выпуклыми мажорантами.
-
Описаны и обоснованы редукции некоторых задач дискретной оптимизации к непрерывным задачам глобальной оптимизации, в которых целевые функции имеют вогнутые опорные функции-миноранты.
Теоретическая и практическая значимость работы. Разработанная теория и методы решения задач математического программирования, основанная на понятиях вогнутой опорной функции-миноранты и выпуклой опорной функции-мажоранты, позволяет проводить более глубокие исследования задач глобальной оптимизации, конструировать эффективные методы локального и глобального поиска в практических задачах экономико-математического и технического моделирования. Методика, изложенная в работе, позволяет из всей задачи глобальной оптимизации выделить подзадачу минимизации выпуклой функции на выпуклом множестве (в случае локального поиска) и подзадачу минимизации вогнутой функции на выпуклом множестве для построения оценки снизу минимального значения целевой функции (в случае глобального поиска). Предложенные в работе методы детализированы в виде конкретных алгоритмов, проведено численное тестирование этих алгоритмов, показавшее хорошую вычислительную работоспособность.
Апробация работы. Результаты работы докладывались на ряде международных и всероссийских конференций и на семинарах, в числе которых:
Конференции в России: Всероссийская конференция по математическому
программированию (Свердловск, 1987 г., 1989 г., 1993 г., Екатеринбург
2000 г., 2007 г.), всероссийская конференция «Алгоритмический анализ
неустойчивых задач» (Екатеринбург, 2004 г.), Байкальские международные
школы-семинары «Методы оптимизации и их приложения» (Иркутск, 1989
г., 1992 г., 2005 г.), всероссийская конференция «Проблемы оптимизации и
экономические приложения» (Омск, 1997 г., 2002 г, 2009 г.), всероссийская
конференция «Дискретный анализ и исследование операций» (Новосибирск,
1998 г., 2000 г., 2002 г, 2004 г., Владивосток, 2007 г), международная
конференция «Оптимизация и экономические приложения в окружающей
среде» (Екатеринбург, 2000 г.), международный семинар «Либерализация
и модернизация электроэнергетических систем» (Иркутск, 2000 г.),
международный конгресс по математическому моделированию (Нижний
Новгород, 2004 г.), международная конференция «Математика в современном
мире» (Новосибирск, 2007 г.), всероссийская конференция «Математическое
моделирование и вычислительные технологии в междисциплинарных
научных исследованиях» (Иркутск, 2009).
Зарубежные конференции: Международная конференция IFIP-7
(Лейпциг, 1989 г., Трир, 2001 г., Германия), международная конференция
по математическому программированию (Хидензее, Германия, 1993 г.),
международный симпозиум по математическому программированию (Анн-
Арбор, США, 1994 г., Лозанна, Швейцария, 1997 г.), международный
семинар по глобальной оптимизации (Зегед, Венгрия, 1995 г.), франко-
германская конференция по методам оптимизации (Трир, Германия, 1996
г.), германская конференция по оптимизации (Ламбрехт, Германия, 1997
г.), международная конференция по методам оптимизации и оптимальному
управлению (Улан-Батор, Монголия, 2002 г.), международная конференция
EURO-23 (Бонн, Германия, 2009 г.), EURO-24 (Лиссабон, Португалия, 2010
г.)
Семинары в: институте исследования операций при Цюрихском
университете (Цюрих, Швейцария, 1993 г., 1997 г.), Цюрихском университете (Цюрих, Швейцария, 1998 г.), университете им. А. Гумболдта (Берлин, Германия, 1997 г.), Трирском университете (Трир, Германия, 1997 г.), Институте математики, экономики и информатики Иркутского государственного университета (1995 г.), Институте прикладной математики
ДВО РАН (1998 г.), Вычислительном центре РАН (2005 г., 2009 г.), Институте математики и механики УрО РАН (2005 г., 2009 г.), Нижегородском государственном университете (2005 г., 2009 г.), Институте проблем управления РАН (2009 г.), Московском государственном университете (2009 г.), Институте динамики систем и теории управления (Иркутск, 2009 г., 2010 г.).
Публикации. По теме диссертации опубликовано 45 научных работ. Основные результаты представлены в [1-36]. В число указанных публикаций входят 9 статей из «Перечня ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора наук» [1-9].
Личный вклад автора. Все основные результаты получены автором лично. В совместных работах вклад соискателя является основным (за исключением работы [9], где ему принадлежит описание реализации метода парабол). Конфликт с интересами соавторов отсутствует. Результаты соавторов в диссертационную работу не включены.
Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы (244 наименования). Общий объём диссертации - 275 страниц, включая 29 рисунков и 21 таблицу.
