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

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

4-

Хамисов Олег Валерьевич

МЕТОДЫ ВЫПУКЛЫХ И ВОГНУТЫХ ОПОРНЫХ ФУНКЦИЙ В ЗАДАЧАХ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ

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

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

Иркутск - 2010

1.8 НОЯ 2010

004613377

Работа выполнена в Учреждении Российской академии наук Институте систем энергетики им. Л. А. Мелентьева Сибирского отделения РАН

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

Антипин Анатолий Сергеевич

Ведущая организация: Нижегородский государственный университет

им. Н. И. Лобачевского

Защита состоится 26 ноября 2010 г. в 14:00 на заседании диссертационного совета Д 212.074.01 при ГОУ ВПО «Иркутский государственный университет» по адресу: 664003, г. Иркутск, бульвар Гагарина, 20, Институт математики, экономики и информатики.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).

Автореферат разослан 25 октября 2010 г.

Учёный секретарь диссертационного совета,

доктор физико-математических наук, профессор Дыхта Владимир Александрович

доктор физико-математических наук Попов Леонид Денисович

канд. физ.-мат. наук, доцент

/ Антоник В. Г. /

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

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

Тем не менее, к настоящему времени в области теории и методов глобальной оптимизации получены серьезные результаты. Прежде всего выяснена структура всех практически значимых невыпуклых функций. Оказалось, что невыпуклая непрерывная функция «почти всегда» может быть представлена в качестве разности двух выпуклых функций. Такие функции впервые появились в работах А.Д. Александрова, Е.М. Ландиса в конце 40-х и начале 50-х годов и в работах П. Хартмана (Р. Hartman) в конце 50-х годов прошлого века. Термин d.c. (difference of convex -разность выпуклых) функция введен в работах Ж.-Б. Ириарта-Уррути (J.-B. Hiriart-Urruty) и X. Туя (Н.Тиу) в середине 80-х годов прошлого века и используется с тех пор всеми авторами как общепринятый в исследованиях по глобальной оптимизации. Структурные свойства d.c. функций привели к разработке широкого класса эффективных методов глобальной оптимизации, которые в специальных случаях (таких, как задачи размещения) позволяют решать за приемлемое время задачи с несколькими сотнями переменных с доказательством глобальной оптимальности полученного решения. Н. Сахинидисом (N. Sahinidis) и М. Тавармалани (M. 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 программирования, можно быстро получать оценки снизу глобального минимального значения целевой функции, а в случае отсутствия разрыва двойственности находить и глобальное решение.

И все же задачи глобальной оптимизации явно или аналитически заданных функций все еще являются трудно решаемыми. С этой точки зрения интерес представляют подходы к минимизации многоэкстремальных функций, основанные на других идеях и конструкциях, чем те, что были упомянуты выше. К ним относится идея представления оптимизируемой функции в виде верхней огибающей или поточечного супремума вспомогательного семейства непрерывных функций. Идея эта продиктована желанием обобщить свойство выпуклой функции быть представленной в виде верхней огибающей семейства аффинных функций. В выпуклой оптимизации это свойство привело к разработке эффективных вычислительных схем, ярким представителем которых является метод опорных плоскостей. Переход от выпуклых функций к невыпуклым требует замены множества аффинных функций другими семействами. Первой работой в этом направлении можно считать статью Э. Беккенбаха1. Следующей, существенной на взгляд автора, является монография С.С. Кутателадзе и A.M. Рубинова2. Затем последовал ряд работ зарубежных авторов таких, как А. Бен-Тал (А. Ben-Tal), А. Бен-Израэль (А. Ben-Israel), С. Долеккий (S. Dolecky), Д. Паллашке (D. Pallaschke), С. Ролевич (S. Rolewicz), И. Зингер (I. Singer). Основное внимание в этих работах было уделено теоретическим результатам. Особо следует выделить монографию A.M. Рубинова3, в которой теоретические результаты присутствуют наравне с практическими алгоритмами глобальной оптимизации. Возможность рассмотрения семейства вогнутых непрерывных функций в качестве вспомогательного семейства была впервые отмечена В.П. Булатовым в 1984 году, им же был введен термин «функция, имеющая вогнутую миноранту». Дальнейшим существенным вкладом в этом направлении была статья В.И. Норкина4. Взгляд на невыпуклую

Jeckenbach Е. F. Generalized convex functions // Bull. Am. Math. Soc. - 1937. - N>43. - P. 363-371

2Кутателадзе С. С., Рубинов A. M. Двойственность Минковского и ее приложения. - Новосибирск: Наука, 1976. - 254 с.

3Rubinov А. М. Abstract Convexity and Global Optimization. - Kluwer Academic Publishers, 2000. - 470 p.

4Норкин В. И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журн. вы'шсл. матем. и матем. физики. - 1992. - Т. 32. - №7. - С. 992-1007.

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

Данная диссертационная работа является продолжением исследований, начатых в монографиях и статьях В.П. Булатова, В.И. Норкина и A.M. Рубинова. Основные усилия в предлагаемой работы были направлены на исследование свойств функций, имеющих вогнутую непрерывную опорную функцию-миноранту, и разработку эффективных численных методов минимизации таких функций.

Целями и задачами работы являются:

• проведение сравнительного анализа функций, имеющих вогнутую опорную функцию-миноранту, с другими классами функций, широко использующимися в оптимизации;

• разработка конструктивных способов построения опорных вогнутых функций-минорант и опорных выпуклых функций-мажорант;

• разработка методов локальной оптимизации, использующих выпуклые опорные функции-мажоранты;

• развитие методов отсечений для глобальной минимизации функций с вогнутыми опорными минорантами;

• разработка новых методов ветвей и границ с использованием вогнутых опорных функций-минорант;

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

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

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

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

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

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

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

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

Основные результаты диссертации, выносимые на защиту.

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

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

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

4. Разработаны методы ветвей и границ с вогнутыми минорантами, которые: сводят вспомогательные задачи глобальной оптимизации к задачам 0-1 программирования, используют двойственные оценки, а также применяют метод отсечений в Жп+1.

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

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

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

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

• Конференции в России: Всероссийская конференция по математическому программированию (Свердловск, 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 таблицу.

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

Во введении дается краткий обзор по теории и методам глобальной оптимизации.

В Главе 1 исследованы свойства функций с вогнутой опорной минорантой и выпуклой опорной мажорантой.

В параграфе 1.1 дано определение и проведепо сравнение функций с вогнутой минорантой с другими классами функций.

Определение 1.2. Будем говорить, что функция ¡(х) имеет вогнутую опорную функцию-миноранту на множестве X, если существует функция ф(х,у), ф : Еп х X —► К, непрерывная и вогнутая по х для каждого фиксированного у и такая, что

Множество всех функций f(x), / : X —> К, имеющих вогнутую опорную функцию-миноранту на X, обозначим через СМ(Х) и каждую функцию / £ СМ(Х) будем для краткости называть с.т. функцией на множестве X (с.т. - первые буквы выражения «concave minorant» - вогнутая миноранта). Функцию / 6 СМ(Ш.п) будем называть просто с.т. функцией.

Теорема 1.1. Каждая функция f £ СМ(Х) является полунепрерывной снизу на X функцией.

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

Определение 1.3. Пусть X с Rn и f(x) - соответственно компактное множество и полунепрерывная снизу функция на X. Точка у € X называется с.т. точкой функции f(x), если f{x) имеет вогнутую опорную миноранту в точке у.

Введем в рассмотрение множество dom(f, X) :

и будем обозначать через [й] замыкание множества Б с К".

Теорема 1.2. Множество всех с.т. точек полунепрерывной снизу функции /(х) на X плотно в с?от(/, X).

Теорема 1.3. Любая точка локального минимума полунепрерывной

Цх)>ф(х,у) Цх,у)еХхХ,

f(y) = i>(y,y) vyex.

(1) (2)

dom{f, X) = {я G X : f[x) < +00}

снизу функции f{x) на компактном множестве X является с.т. точкой. Условия линшицевости с.т. функций приведены в следующей теореме. Теорема 1.4. Пусть f(x) - некоторая с.т. функция и гр{х,у) - её вогнутая опорная функция-миноранта. Если существует константа М > О такая, что

|Ф(х,у)\<М \/(х,у)еХхХ, (3)

то f(x) удовлетворяет условию Липшица с некоторой константой L.

Результатом первого параграфа является сравнение функций с вогнутой минорантой с другими функциями, представленное в виде Таблицы 1.

Функция /(*) Поточечная операция по у Опорные функции

выпуклая на X (X выпукло) sup ■Ф(х,у) = /(у)+Рт(х~ у), Р^дДу)

выпуклая на, Б Б выпукло, X С т^5) max Ф(х,у) = }(у)+рТ(х-у), реа/ы

слабо выпуклая max у) = /(»)+- у) + рЬ - г/112, £ бГ.рбМ

(1.С. sup ф(х, у) = с[у)т{х - у) + г(у) - я(х) с(у)екп,г(у)ек, д(я) - непрерывная вогнутая функция

липшицевая max Ф(х, у) ~ вогнута по х, равномерно ограничена по у

непрерывная sup ф(х, у) - вогнута по х равностепенно по у

с.т. max ф(х,у) - вогнута по х

полунепрерывная снизу sup ф(х, у) - вогнута по х

Таблица 1. Свойства функции f(x) в зависимости от свойств опорной

миноранты ~ф(х,у).

Во втором параграфе приводятся правила построения вогнутых минорант для широкого класса невыпуклых функций. Существенная часть посвящена нахождению константы Липшица для дифференцируемых функций.

Описаны и более общие результаты.

Теорема 1.5. Пусть заданы с.т. функции f(x), fi{x), i = 1,..., т. Тогда справедливы следующие утверждения:

т

(г) линейная комбинация J2 )ч/,{х) есть с.т. функция,

¿=i

если \ > 0, г — 1,..., т;

(п) функция максимума max /¡(х) есть с.т. функция;

1 <i<m

(Hi) функция минимума min Ых) есть с.т. функция.

l<i<m

Напомним, что функция f(x),f : 1" 1 называется монотонно неубывающей функцией если для любых х,у G К" таких, что х, > уг, i = 1,..., п справедливо f(x) > f(y).

Теорема 1.6. Пусть gfa), gi : R" -> R, i = 1,..., m и h(x), h :Шт -+Ш есть с.т. функции. Если для каждого фиксированного у е Rm существует монотонно неубывающая вогнутая миноранта фи(х,у) функции h, то f(x) = h(g(x)) есть с.т. функция.

Следствие 1.3. Пусть /¿(я), /< : R" Ж, г — 1,..., к - с.т. функции. Тогда функция

к

/(*) = ][>iai{0)/<(*)}]« q> 1

i=l

есть с.т. функция.

Следствие 1.4. Пусть /(х) - с.т. функция. Тогда eJ№ также будет с.т. функцией.

Следствие 1.5. Пусть f{x) такая с.т. функция, что tp(x, у) > 0 Wx, у £ X. Тогда функции 1п(/(а;)), у/f(x), —щ являются с.т. функциями на X.

Следствие 1.6. Пусть fi{x),i = 1, ...,k такие с.т. функции, что ipi{x, у) > О V.T, у е X, где ipi(x, у) - вогнутая опорная миноранта функции fi(x). Тогда F(x) = nLi/>(x) есть с-т- Функция X.

В третьем параграфе вводится понятие выпуклой опорной мажоранты. Определение 1.8. Будем говорить, что функция ¡(х) имеет выпуклую опорную мажоранту на множестве X, если существует функция tp(x,y), ip : Rn х X —* R, непрерывная и выпуклая по х для каждого фиксированного у и такая, что

f(x)<<p(x,V)V(z,y)£XxX, (4)

f{y) = viv,y) Vyex. (5)

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

Определение 1.9. Если функция f{x),f : X -* R, X С Rn удовлетворяет включениям

/ЕСМ(Х),-/ЕСМ(Х), (6)

то f называется с.т. симметричной функцией на X.

Множество всех с.т. симметричных функций на X обозначим через CMS(X). Конструктивные свойства с.т. симметричных функций определяются следующей теоремой.

Теорема 1.8. Пусть f Е CMS{X) и /,• £ CMS{X), г = 1 ,...,т, т > 1, X - компактное множество . Тогда

т

(О EVi€CMS(X), Ai6K;

(и) lf2€CMS(Xy, (iii) /l • /2 е CMS(X);

(vi) если f(x) > 0,VxeX,mojfoe CMS(X).

Опишем некоторые дифференциальные свойства с.т. симметричных функций. Всюду в дальнейшем Vxi>(x,y)(Vx'p[x,y)) есть градиент опорной функции-миноранты (функции-мажоранты) по х при фиксированном у.

Лемма 1.1. Пусть int(X) Ф 0 и опорные функции ф{х, у) и <р(х, у) дифференцируемы по х при каждом фиксированном у S X. Тогда

= VMv, у) Чу е int(X). (7)

Теорема 1.9. Пусть / Е CMS(X), int(X) Ф 0 и опорные функции ф{х,у) и <р(х,у) дифференцируемы по х при каждом фиксированном у Е X. Тогда f(x) - дифференцируемая функция на int(X) и

V/M = у) = у) Vy Е int(X). (8)

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

min f(x), (9)

9i(x) <0, i = l,...,m, hi(x) = 0, i — xtX,

(И) (12)

где X С - компактное множество, e CM(X),i — 1,... ,m, hi 6 CMS(X),i = 1,...,/. Задачу (9)—(12) будем называть задачей c.m. программирования.

Основную идею, лежащую в основе метода локального поиска, проиллюстрируем на примере задачи c.m. программирования без ограничений равенств.

ПРОЦЕДУРА ЛОКАЛЬНОГО УЛУЧШЕНИЯ LOCAL-1.

Входная информация: Целевая функция f(x), выпуклая мажоранта ff{x,y) функции f(x), функции-ограничения <ji{x), выпуклые мажоранты <pSi(x,y) функций <ji(x),выпуклое компактное множество X.

Шаг 0. Задать некоторую стартовую точку ха £ X. Установить к = 0.

Шаг 1. Точка xk+l находится из решения задачи выпуклого программирования

Шаг 2. Если хк = хк+1, то стоп. Иначе обновить к = к + 1, перейти на Шаг 1.

Условия сходимости процедуры ЬОСАи-1 определяются следующей теоремой.

Теорема 1.12. Если х° - допустимая точка задачи с.т. программирования без ограничений-равенств (9),(10),(12),функции /(х),ф) непрерывно дифференцируемы, функции ^(х,у),(рд^х,у) непрерывны по совокупности переменных (х,у) и непрерывно дифференцируемы по х, то любая предельная точка процедуры LOCAL-I есть стационарная точка задачи (9),(10), (12). Учет ограничений-равенств исследуется для задачи

<pj(x,xk) —> min,

(pSi{x, xk) < 0, г = 1,..., m, х€Х.

f(x) min, h(x) = 0, l£l

Процедура, локального поиска в этом случае имеет вид

ПРОЦЕДУРА ЛОКАЛЬНОГО УЛУЧШЕНИЯ ЮСАЫ!.

Входная информация: Целевая функция f{x), выпуклая мажоранта <Р/(х,у) функции /(¡г), функция-ограничение /г(ж), выпуклая мажоранта и вогнутая миноранта фк{х,у) функции к{х), выпуклое компактное множество X.

Шаг 0. Задать некоторую стартовую точку £ X. Установить к = 0.

Шаг 1. Определить функцию

Шаг 3. Если И{хк+1) = 0, то стоп. Иначе обновить к = к + 1, перейти на Шаг 1.

Далее в параграфе исследуются вопросы сходимости и приводится иллюстративный численный пример.

В параграфе 1.6 описано обобщение метода Пиявского для задачи

tjjh(x,xk), если h(xk) > 0, -iph{x,xk), ecmh[xk)<0.

Шаг 2. Точка хк+1 - стационарная точка задачи

ifif(x, хк) —» min, <0, j = 0,...,k, хеХ.

(14)

min f(x), xeX.

(15)

(16)

Пусть x1, x2,..., xk - некоторые точки из X. Тогда

f{x) > max ф(х, х*) = Д(ж) Vx 6 X. i <i<k

Назовем задачу

(17)

min fk{x), xeX

(18) (19)

Задача (18)—(19) снова является задачей с.т. программирования и, следовательно, многоэкстремальна. Однако, эта задача уже имеет специальный вид, что дает некоторые преимущества, а именно, функция /к(х) является с1.с. функцией, поскольку

/*(*) = №)-/*"(*),

где

к

к ¿=1

и обе функции /¿"(х) и /¿"(ж) выпуклы. Вводя дополнительную переменную х„+1, мы можем свести аппроксимирующую с.т. задачу к следующей

тт{гп+1 - /¿"(ж)}, (21)

/+(*) < *п+ь (22) 1бХ (23)

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

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

В параграфах 1.6 и 1.7 описаны технические приемы, позволяющие увеличить эффективность методов локального и глобального поиска в задачах с.т. программирования.

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

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

Цх) > 0), Ь,^(х)), тах{/(х), й.(ж)}, тт{/(а:), <?(а;)}. Показано, что все эти правила могут быть запрограммированы, т.е. демонстрируется возможность автоматической глобальной оптимизации, когда от пользователя требуется только введение явного вида оптимизируемой функции (т.е. не требуется ни производных, ни констант Липшица и т.д). Весь дальнейший анализ, построение минорант и мажорант, а также глобальная оптимизация происходят автоматически (т.е. осуществляются компьютером). На выходе выдается точка глобального минимума. Тестирование на стандартном наборе задач одномерной оптимизации показало, что предлагаемая методика в среднем в 3-10 раз работает быстрее известных методов липшицевой оптимизации.

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

В качестве примера рассмотрим следующую задачу. Пусть /(х) - дважды непрерывно дифференцируемая функция, тогда существует константа р > 0 такая, что функция /(ж) + р{х — у)2 выпукла на отрезке [а, /?] для любого фиксированного у. Задача состоит в нахождении корня на [а,/3]. Не уменьшая общности будем считать /(а) > 0. Вогнутая миноранта

условии

Ф{х,у) = /Ы + /\у){х -у)- р{х - у)2.

Для генерируемой последовательности

1{хк) + ¡'{хк){хм - хк) - р(хк+1 - хк)2 = 0.

Откуда следует

хш = хк +

Я»*)+ >/[№)]+ 4р/(з*) 2 р

(24)

Процесс (24) сходится к искомому корню (в предположении, что он существует) при х° = а.

В параграфе 2.4 приводится редукция задач невыпуклого квадратичного программирования с ограничениями равенствами и (или) ограничениями неравенствами к задаче нахождения корней одномерного полинома. Сначала записывается система необходимых условий оптимальности. Данная система представляет собой систему полиномиальных равенств и может быть решена алгебраическими методами, основанными на понятии базисов Грёбнера. Прямые и двойственные переменные являются равноправными в исследуемой системе. Основная идея алгебраических методов состоит в обобщении метода исключения Гаусса для решения систем полиномиальных уравнений. Привлекательность этих методов заключается в том, что с помощью них можно решать задачи малой размерности примерно также, как решаются системы линейных алгебраических уравнений с небольшим количеством переменных. Проводя исключение переменных в соответствие с алгоритмом Бухбергера, в итоге получаем полином от одной переменной. Находим корни этого полинома и двигаясь в обратном порядке (аналог обратного хода в методе Гаусса) находим и прямые и двойственные переменные, соответствующие каждой стационарной точке. В параграфе приводятся примеры иллюстрирующие предлагаемый подход.

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

Общую методику исследования сходимости можно рассмотреть на примере отсечений в Шп. Рассматривается следующая задача с.т. программирования

стх —»тт, <0, г = 1 ,...,т, }ц{х) = 0, i = l,...,l¡ хеХ,

где gi 6 СМ{Х),г = 1,...,т ^ € СМЗ(Х),i = l,...,1,

Х = {хеП :Ах< Ь), П — {х 6 Еп : х < х < х), -оо < щ < х< +оо, j =

А - р х п-матрица, Ь е

(25)

(26)

ПРОЦЕДУРА ОТСЕЧЕНИЙ В Kn: CUT".

Входная информация: Целевая функция (Fx, функции <?;(#), вогнутые опорные миноранты ф^(х,у) функций gi(x) % = 1,... ,m, функции hi(x), выпуклые мажоранты УлДа;,«/) и вогнутые миноранты ф}ц{х,у) функций hi(x) i = выпуклый многогранник вида (26).

Шаг 0. Решить задачу линейного программирования

(Fx —► min, а; еХ.

Пусть хй - оптимальное решение, Г° - невырожденный конус с вершиной Xй, образованный активными в я0 ограничениями. Установить к = 0.

Шаг 1. Найти величину максимальной невязки

ök = max{gi(x*),..., дт{хк)% lhi(x*)|,..., |ЭД®*)|}.

Шаг 2. Если 6к = 0, перейти на Шаг 7, иначе перейти на Шаг 3.

Шаг 3. Определить опорную функцию: если 5к — max{sn(a;lE),... ,дт(хк)}< определить г* : gik(xk) = ök и установить Шк[х) = фтк(х,хк)\ если 6к = max{|/ii(:E*)|,..., |/1/(ж*)|} , определить г* : = 6к, если

hik(xk) < 0, то установить Шк(х) = -(/^(¡е,^*), иначе установить Шк{х) = ф^{х,хк). В силу построения Wfc(x) - непрерывная вогнутая функция, обладающая свойством и>к(хк) > 0.

Шаг 4. Найти точки пересечения ребер Sk'\i — 1,...,п конуса Тк с границей выпуклого множества Ф* = {а; 6 R" : Шк{х) > 0} и провести через них отсекающую плоскость Lk = {х € R™ : (ак)тх = ßk}

Шаг 5. Решить задачу линейного программирования

стх —► min, (offxüßt, 1 = 1,...,*,

Пусть хк+1 - оптимальное решение, Г4"1"1 - невырожденный конус с вершиной xk+l, образованный активными в хк+1 ограничениями.

Шаг 6. Установить к = к + 1 и перейти на Шаг 1.

Шаг 7. Стоп.

Очевидно, что с?хк < с* Ук, где с* - глобальное минимальное значение целевой функции в задаче (25) и, если процедура CUT конечна, то точка хк, полученная на последней итерации, - глобальный минимум задачи (25).

Для анализа сходимости сделаем одно важное предположение

min 1 / ,„ < A < 0. (27)

Условие (27) означает, что хотя бы одно ребро конуса Г4 не параллельно отсекающей плоскости.

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

• Опорные функции фд<{х,у),у)к(х,у),/ф}н{х,у) удовлетворяют условию Липшица равномерно по у;

• На каждой итерации выполняется условие (27).

Тогда каждая предельная точка последовательности {хк} есть точка глобального минимума задачи (25).

В параграфе 3.3 описанные результаты распространяются на метод отсечений в R"+1.

В параграфе 3.4 вводится важное понятие вогнутого продолжения. Пусть f(x) - вогнутая дифференцируемая функция.

Определение 3.1. Функцию W(x) будем называть вогнутым продолжением функции f(x) на множестве X, если выполняются следующие условия

1. W(x) - непрерывная вогнутая функция;

2. W(x) = f(x) Vx е X;

3. W(x) > f{x) Vx 6 R".

Множество всех вогнутых продолжений W(x) на X будем обозначать EXT(f,X). Очевидно, что / б EXT(j, X).

Определение 3.2. Функция F{x) называется максимальным вогнутым продолжением функции f(x) на множестве X, если

1. F е EXT{f, X);

2. F{x) > W(x) Vx € Rn, VVF G EXT{f, X).

Теорема 3.5. Максимальное вогнутое продолжение F(x) вогнутой дифференцируемой функции f(x) на выпуклом компактном множестве X определяется следующим образом

F(x) = min{f(y) + Vf(y)T(x-y)}. (28)

Введем в рассмотрение множество

D = {deRn:d = v/(®), хеХ},

которое будем называть образом градиентного отображения множества X и co(D) - выпуклую оболочку D. Теорема 3.6. Предположим, что

О £int(co(D)). (29)

Тогда F(x) имеет рецессивное направление.

Предположим, что f(x) - вогнутая квадратичная функция

f{x) = xTQx,

Q - отрицательно полуопределенная симметричная матрица. Тогда

F{x) = min{yTQy + 2yTQ{x - у)} = min{2yTQx - yTQy). (30)

xcX xeX

Следовательно, вычисление функции F(x) в точке эквивалентно решению задаче выпуклого программирования (30). Кроме того, в силу линейности градиентного отображения квадратичной функции Теорему 3.6 можно уточнить следующим образом. Теорема З.Т. Если

О ^ int(X), (31)

то F{x) имеет рецессивное направление.

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

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

Основным результатом параграфа 3.6 является алгоритм,

комбинирующий отсечения в R" и Rn+1.

Рассматривается общая задача с.т. программирования

}{х) ->■ min,

9i{x) <0, i = 1,...,т, hi(x) = 0, г = 1,..., /, хЕХ,

(33)

(34)

(35)

где / е CM(X),gi е CM(X),hi € CMS(X), X С К", mi(X) ф 0 -

выпуклый многогранник.

КОНЕЧНАЯ ПРОЦЕДУРА ОТСЕЧЕНИЙ В К" и Mn+1: CUT"x(n+1).

Входная информация: Целевая функция f(x), вогнутая опорная миноранта 1pj(x,y) функции f(x), функции ^¿(ж), вогнутые опорные миноранты фяХх,у) функций gi{x), г = 1,... , т, функции hi(x), выпуклые мажоранты PhХх,у) и вогнутые миноранты фh,(x,y) функций }ц(х), г = 1,...,/, выпуклый многогранник X, точность вычислений е > 0, положительное целое N .

Шаг 1. Построить симплекс S Э X, S = coin1,... ,г)"+1}.

Шаг 2. Определить

Шаг 3. Построить вогнутую миноранту 1р}(х,ш).

Шаг 4. Через точки (v1,rl}}[vliu)),...,(vn+itipf(vn+1,w))) провести плоскость, задаваемую уравнением жп+1 = рц(х).

Шаг 5. Установить /0 = +оо, к = 0, Х° - X, N = 0.

Шаг 6. Решить задачу линейного программирования

п+1

xn+i —► min, Pi(x) <xn+hi = 0,...,k, хеХк.

Пусть (хк, хк+1) - оптимальное решение.

Шаг 7. Если хк допустимая точка, то произвести локальный спуск из хк в точку ,Л+1

w^1, установить fk+i = f[wk+l). Если

fk+l - Хп+1 ^ е>

то стоп: ■шк+1 - е-оптимальное решение задачи (32)—(35).

Шаг 8. Построить в точке (хк,хк+1) конус Г£+1. Найти точки =

1,...,п+ 1 пересечения ребер конуса Г"+1 с поверхностью, задаваемой уравнением хп+1 = ф((х,хк).

Шаг 9. Через точки = 1,...,п + 1 провести плоскость,

определяемую уравнением хп+\ =р^\{х).

Шаг 10. Если

max - min zti-, < е,

l<j<n+l 71+1 l<j<n+l n+1

то установить N = N + 1, иначе установить А: = А: +1 и перейти на Шаг б.

Шаг И. Если N > N, то стоп: процедура заканчивает работу, найдя двустороннюю оценку

хкп+1 </»< fk+i. (36)

Шаг 12. Решить задачу линейного программирования

Рк+i(x) min, хеХк.

Пусть хк - оптимальное решение.

Шаг 13. В точке хк построить множество Ф* = {х : ф{(х,хк) > fk+i}-

Шаг 14. Используя множество Ф* произвести отсечение части Хк из вершины хк и получить многогранник Хк+1. Если Xk+l = 0, то стоп: если fk+i < +оо, то wk+1 - е-оптимальное решение задачи (32)—(35), иначе допустимое множество в задаче (32)-(35) пусто.

Шаг 15. Установить к = к + 1 и перейти на Шаг б.

Количество итераций в этой процедуре не превышает N. Геометрические соображения, лежащие в основе данной процедуры следующие. Главными являются отсечения в Rra+1 поскольку они обладают двусторонней оценкой (36). Отсечения в R" играют вспомогательную роль, основное их назначение состоит в сокращении множеств Хк, так как чем «меньше» множество Хк,

тем эффективнее отсечения в К"+1.

Вычислительный эксперимент подтверждает более высокую эффективность процедуры сит"х^п+1' по сравнению с ранее описанными методами отсечений.

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

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

В параграфе 4.2 в качестве процедуры оценивания рассматривается задача минимизации невыпуклой квадратичной функции на выпуклом многограннике.

где д(:г) = хгС}х + хтс, симметричная п х п матрица С} имеет хотя бы одно отрицательное собственное число, с € Е", множество X - выпуклый многогранник, определяемый системой неравенств

А-щхп матрица, Ь е йт. Задача квадратичного программирования (37)-(39) эквивалентна следующей

q(x) —► ш,

(37)

(38)

гехсг

X = {® € Я" : Ах < 6} ,

(39)

^ (стх - Ът\) -+ тт. 2 4 ' (г,Л)

2е}х + с + \тА = 0, А ¿вг = 0, г = 1,т,

(40)

(41)

(42)

(43)

(44)

Ах + й = Ь, А, >0, г = 1 ,тп,

5,->0, % = 1, п. (45)

Задача (40)—(45) есть задача минимизации линейной функции при линейных ограничениях (41), (43), (44), (45) и билинейных ограничениях (42) в пространстве переменных {х, А).

Предположим, что множество X удовлетворяет условию Слейтера, т.е. существует х Е 1гй(Х). Тогда можно указать константу М > 0 :

А^ < М ] - 1,тп.

Очевидно, что переменные в;, также ограничены. Таким образом, можно считать, что существует константа N > 0 такая, что

Аi<N, в; < ./V, г = ТРт. (46)

Вводя вспомогательные 0-1 переменные щ, г = 1,т и учитывая неравенства

(46), ограничения (42) можно переписать в следующем, эквивалентном виде

А<-Ж-г*<0, в< - N(1 - я) < 0, г = Т~гп. (47)

Заменяя в задаче (40)-(45) ограничения (42) на ограничения (47), получим задачу линейного, частично-целочисленного программирования (40)—(41),

(47), (43)-(45).

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

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

В параграфе 4.4 описан метод ветвей и границ для минимизации на многограннике функции с квадратичной вогнутой опорной минорантой. В качестве вспомогательной задачи на каждом шаге решается задача 0-1 смешанного программирования. Метод основан на редукции, приведенной в параграфе 4.1.

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

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

f(x) - min, (48)

Ф)<0, г = 1,...,т, (49)

хвХ, (50)

где f(x),gi(x) - вогнутые функции, X - многогранник с известными вершинами X = co{vl,...,xN}, N > п + 1. Пусть f* - глобальное минимальное значение целевой функции. Тогда /* > в*, где

в* = supö(/i), li> о

0(/i) = mmL{x,ß),

ХбЛ

т

ß) = f(x) + ^ ßi9i{x).

i=i

В силу вогнутости L(x, ß) по х

L(x,ß) = min(/(w>) +

1 < 1< /V ' '

1<J<At

i=l

e* = sup min (f(v>) + V

Последняя задача эквивалентна следующей задаче лилейного программирования

Но —+ max,

m

+ЛЛ(^) > j = 1, ■ • •, N,

¿=1

Hi > 0, i — 1,... ,m.

Следовательно, решение задачи, двойственной (48)—(50), не вызывает вычислительных трудностей и оценка 0* может быть легко получена. Если вершины многогранника X неизвестны, то вместо множества X можно использовать любое аппроксимирующее множество D = со{г;1,... D э X. В параграфе описаны способы аппроксимации задачи с.т.

программирования (32)-(35) задачами вида (48)-(50) и метод ветвей и границ, основанный на такой аппроксимации.

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

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

Пусть заданы билинейные функции gt(x, у), г = 1,..., т. Требуется найти вектор уй Е У С К1 такой, что

Р(у°) = {х 6 X С R" : дг(х,у°) < 0,г = 1,... ,mj ± 0, X и У - непустые выпуклые компактные множества. Введем функцию

w(y) = min max gt(x,y).

xeX 1 <i<m

Тогда P(y°) Ф 0 тогда и только тогда, когда w(y°) < 0. Поэтому для нахождения точки у0 достаточно решить задачу минимизации w(y) на У. В общем случае w(y) не является выпуклой функцией. Нетрудно видеть, что вычисление значения w(y) в некоторой точке у € У эквивалентно решению задачи линейного программирования. Пусть х - найденное оптимальное решение. Тогда

w(y) = min max д<(х, у) < max д{(х, у)

хеХ 1<г<т 1<г <т

И

w{y) = max д,{х, у),

1 <г<т

т.е. функция

является опорной в точке у выпуклой функцией-мажорантой функции ги(у).

<Р{У,У) = max gi{x,y)

1<%<т

Далее,

т т

w(y) - min max д>(х,у) = min max V щд{ (x, у) = maxmin У)щд^х,у), хйХ l<t<m хёХ 1' '

¿=1 ¿=1

где i1, = {u 6 E" : = l,Ui > 0,t = l,m} (в силу компактности

X и линейности по и и по а: операции min и max перестановочны). При заданном у € У, решив задачу линейного программирования, найдем соответствующие значения (й,х). Тогда

т

w{y) > min Yjk9i{x,v) = Ф(у,у),

igX *■—' i=i

т.е. ф(у,у) есть вогнутая функция-миноранта w(y), опорная в точке у. Таким образом невыпуклая функция w(y) имеет выпуклую опорную функцию-мажоранту и вогнутую опорную функцию-миноранту в каждой точке множества Y и для решения поставленной задачи могут использоваться локальные и глобальные методы с.т. программирования. Затем в данном параграфе описанный выше подход детализируется для приближённого нахождения диапазона изменения функции оптимального значения задачи линейного программирования, в которой целевая функция и (или) функции-ограничения линейно (аффинно) зависят от векторного параметра.

В параграфе 5.2 используемая в предыдущем параграфе методика применяется для решения задачи равновесного программирования. Найти V* е ft С R" :

V* е Argmin{$(v\ w) :w€ П}, (EPA)

где Ф(и, w) есть некоторая функция, определенная на R" х R". Задача (ЕРА) рассматривается без предположений о выпуклости (или квазивыпуклости) функции Ф(г>, w) по второй переменной. Следовательно, не гарантируется существование решения. Предлагается вычислительная процедура, которая предполагает использование методов глобальной оптимизации и которая либо устанавливает, что равновесного решения не существует, либо находит одно из равновесных решений (в том случае, если их несколько).

Введем в рассмотрение функцию

Ф(г;, w) = Ф(и, w) - Ф(у, v). (51)

Мы будем предполагать, что функция Ф(г», и>) непрерывна, а множество П - выпуклое компактное множество. Перепишем задачу (ЕРА) в виде: найти и* :

$(v*,w) > О Vu; € Л, (52)

что, в свою очередь, эквивалентно следующему:

max min Ф(и, w) > 0. (53)

ueii wen

Если ввести вспомогательную функцию

P(v) = пйпФ^ги), (54)

то для проверки неравенства (53) достаточно решить задачу

P{v) —► max, (55)

veil. (56)

В общем случае функция P(v) может быть многоэкстремальной. Пусть v* есть глобальный минимум в задаче (55)-(56). Если P(v*) < 0, то задача равновесного программирования не имеет решения. В противном случае v* есть точка равновесия. Нетрудно видеть, что P(v) < 0 Vw 6 П, и, если v* есть точка равновесия, то

P(v') = 0. (57)

Следовательно, условие (57) можно использовать в качестве необходимого и достаточного условия глобальной оптимальности в том случае, если точка равновесия существует. В силу (54) задача (55)—(56) есть задача оптимизации с неявно заданной целевой функцией. Для того чтобы вычислить значение целевой функции P(v), необходимо решить задачу (54). Тем не менее, поскольку P(v) есть «функция минимума», этот факт может быть использован для разработки итеративной процедуры решения задачи (55)-(56).

Пусть V е Ü - некоторая произвольная точка. Решим задачу (54). Пусть W - оптимальное решение. Если P(v) = 0, то v есть точка равновесия. Если нет, то из (54) имеем

P(v) = y(v,ui), (58)

P(v) < $(v,w)Vveil. (59)

Другими словами, функция Ф(v,w) есть опорная функция-мажоранта функции P(v), следовательно, для нахождения глобального максимума P(v) можно снова применить методы глобальной оптимизации, основанные на использовании нелинейных опорных функций, разработанные в данной работе. Далее в параграфе приводится описание метода глобальной оптимизации для решения задачи (55)—(56), обосновывается сходимость,

приводится численный пример.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых журналах, рекомендованных ВАК

[1] Хамисов О. В. Методы отсечения в В™"1"1 для решения задач глобальной оптимизации на одном классе функций / В. П. Булатов, О. В. Хамисов // Журн. вычислит, математики и мат. физики. — 2007. — Т. 47. — №11. — С. 1830-1842.

[2] Хамисов О. В. Численное решение специальных задач невыпуклого квадратичного программирования / О. В. Хамисов // Дискретный анализ и исследование операций. Серия 1. — 2005. — Т. 12. — №4. — С. 81-91.

[3] Хамисов О. В. Глобальная оптимизация функций с вогнутой опорной минорантой / О. В. Хамисов // Журн. вычислит, математики и мат. физики. - 2004. - Т. 47. — №11. — С. 1830-1842.

[4] Хамисов О. В. Алгебраическое решение задач невыпуклого квадратичного программирования / О. В. Хамисов // Автоматика и телемеханика. — 2004. — №2. - С. 63-74.

[5] Хамисов О. В. Автоматическая глобальная оптимизация / А. Р. Ершов, О. В. Хамисов // Дискретный анализ и исследование операций. Серия 2. — 2004. - Т. 11. - №2. - С. 45-68.

[6] Хамисов О. В. Метод ветвей и границ для мининмизации невыпуклой квадратичной функции при выпуклых квадратичных ограничениях / М. С. Нечаева, О. В. Хамисов // Дискретный анализ и исследование операций. Серия 2. - 2000. - Т. 7. - №2. - С.74-88.

[7] Хамисов О. В. Модифицированный метод симплексных погружений с несколькими секущими плоскостями / Е. В. Апекина, О. В. Хамисов // Известия вузов. Математика. — 1997. — №12. — С. 16-24.

[8] Khamisov О. V. On Optimization Properties of Functions with a Concave Minorant / О. V. Khamisov // Journal of Global Optimization. —1999. — №14. — P.'79-101.

[9] Хамисов О. В. Численное решение задач управления развитием электроэнергетических систем / Д. В. Иванов, И. В. Караулова, Е. В. Маркова, В. В. Труфанов, О. В. Хамисов // Автоматика и телемеханика. - 2004. - №3. - С. 125-136.

Прочие публикации

[10] Хамисов О. В. Нахождение равновесных точек в рыночных моделях 99С / А. 3. Гамм, Е. В. Таирова, О. В. Хамисов // Известия РАН. Энергетика. - 2000. - №6. - С. 57-73.

[11] Хамисов О. В. О коалиционном поведении в рыночных моделях электроэнергетических систем / Е. В. Таирова, О. В. Хамисов // Известия РАН. Энергетика. - 2002. - №4. - С. 40-47.

¡12] Хамисов О. В. Методы управления теплоснабжением потребителей в условиях рынка / В. А. Стенников, О. В. Хамисов, А. В. Пеньковский // Известия РАН. Энергетика. - 2009. - №3. - С. 27-36.

[13] Хамисов О. В. Равновесные модели в экономике и энергетике / В. И. Зоркальцев, О. В. Хамисов. — Новосибирск : Наука, 2006. — 221 с.

[14] Khamisov О. V. A Global Optimization Approach to Solving Equilibrium Programming Problems / О. V. Khamisov // Series on Computers and Operations Research. Optimization and Optimal Control. — 2003. — Vol. 1. — P. 155-164.

[15] Khamisov О. V. The branch and bound method with cuts in En+1 for solving concave programming problem / V. P. Bulatov, О. V. Khamisov. Lecture Notes in Control and Information Sciences. — Springer-Verlag, 1991. - P. 273-282.

[16] Хамисов О. В. Оптимизация и равновесное программирование / О. В. Хамисов // В кн.: Методы исследования и моделирования технических социальных и природных систем. — Новосибирск : Наука, 2003. — С. 278-292.

[17] Хамисов О. В. Некоторые алгебраические и комбинаторные аспекты задачи невыпуклого квадратичного программирования / О. В. Хамисов // В кн.: Современные методы оптимизации и их приложения к моделям энергетики. — Новосибирск : Наука, 2003. — С. 229-247.

[18] Хамисов О. В. К глобальной оптимизации явно заданных функций / Д. В. Иванов, И. В. Мокрый, О. В. Хамисов // В кн.: Методы исследования и моделирования технических социальных и природных систем. — Новосибирск : Наука, 2003. — С. 256-269.

[19] Khamisov О. V. Functions with concave minorant. A general view / О. V. Khamisov. Manuscripte, Institut fur Opeartions Research der Universität Zurich. - Zurich, 1994. - 25 p.

[20] Khamisov О. V. On application of convex and concave support functions in nonconvex problems / О. V. Khamisov // Manuscripte, Institut fur Opeartions Research der Universität Zurich. — Zurich, 1998. — 16 p.

[21] Хамисов О. В. Функции с вогнутой минорантой: определение, оптимизационные свойства и сравнение с другими классами функций / О. В. Хамисов // Оптимизация, управление, интеллект. — Иркутск : ИДСТУ, 1995. - №1 - С. 61-76.

[22] Хамисов О. В. Нахождение вещественных корней полинома на отрезке методом опорных вогнутых функций / О. В. Хамисов // Оптимизация, управление, интеллект. - Иркутск : ИДСТУ, 1999. - №3. - С. 167-177.

[23] Хамисов О.В. О построении новых отсечений в целочисленном программировании / О. В. Хамисов // Труды XIII Байкальской международной школы-семинара «Методы оптимизации и их приложения». — Иркутск, 2005. — Т. 1. — С. 607-612.

[24] Хамисов О. В. Нахождение корней нелинейных уравнений методом вогнутых опорных функций / О. В. Хамисов // Труды XII Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 2001. - Т. 4. - С. 194-198.

[25] Хамисов О. В. К минимизации бивыпуклой функции / О. В. Хамисов // Труды XI Байкальской международной школы-семинара «Методы оптимизации и их приложения». — Иркутск, 1998. — Т. 1. — С. 208-211.

[26] Хамисов О. В. К решению одной невыпуклой векторной задачи оптимизации / Е. В. Таирова, О. В. Хамисов // Труды XI Байкальской международной школы-семинара «Методы оптимизации и их приложения». - Иркутск, 1998. - Т. 1. - С. 238-241.

[27] Хамисов О. В. Применение метода нелинейных опорных функций для параметрического анализа задач выпуклого программирования /

О. В. Хамисов // Труды международной конференциии по распределенным системам: Оптимизация и экономические приложения в окружающей среде. - Екатеринбург, 2000. - С. 184-187.

[28] Khamisov О. V. The cutting method in En+1 through concave extension for solving global extremum problem / V. P. Bulatov, О. V. Khamisov // 21 JAHRESTAGUNG «Mathematische Optimerung». - Berlin, 1989. - P. 16-19.

[29] Khamisov О. V. An optimization approach to finding the Pareto and Nash equilibrium solutions in a mathematical model of energy systems functioning / О. V. Khamisov // Proceedings of the International Workshop «Liberalization and modernization of power systems: operation and control problems». — Irkutsk, 2000. - P. 84-88.

[30] Khamisov О. V. To Global Minimization of a Concave Quadratic Function over a Polytope / О. V. Khamisov, E. V. Tairova // Proceedings of the International Workshop «Discrete Optimization Methods in Production and Logistics». — Omsk, 2004. - P. 83-90.

[31] Khamisov О. V. Game mathematical model to study power system interconnections in view of economic interests of participants: preliminary consideration / О. V. Khamisov, P. V. Kostenko, S. V. Podkovalnikov // Proceedings of the International Conference «Asian Energy Cooperation: Interstate Infrastructure and Energy Markets». - Irkutsk, 2004. - P. 321-324.

[32] Khamisov О. V. On the reduction of some multiextremal problems to the convex-concave programming problem / V. P. Bulatov, О. V. Khamisov // Proceedings of the International Conference «On engineering mathematics and applications». - Shenzhen, 1992. - P. 103-107.

[33] Khamisov О. V. An investigation of equality constrained mathematical programming problems and its application to the economic and power engineering problems / V. P. Bulatov, О. V. Khamisov // Proceedings of the Second SEI-IPRI Seminar «On Methods for solving the problems on energy power system development and control». — Irkutsk, 1992. — P. 90-95.

[34] Хамисов О. В. Методы ветвей и границ с отсечениями в задачах глобальной и дискретной оптимизации / О. В. Хамисов // Материалы российской конференции «Дискретная оптимизация и исследование операций». — Новосибирск, 2007. — С. 83-86.

[35] Хамисов О. В. Равновесное программирование и методы глобальной

оптимизации / О. В. Хамисов // Материалы российской конференции «Проблемы оптимизации и экономические приложения». — Омск, 2009. — С. 83-86.

[36] Хамисов О. В. Метод ветвей и границ для минимизации вогнутой функции на многограннике / О. В. Хамисов // Материалы XXXI конференции молодых учёных. — Иркутск, 1991. — С. 25-33.

Тираж 120 экз. Заказ №169

Отпечатано полиграфическим участком ИСЭМ СО РАН 664033, Иркутск, ул. Лермонтова, 130

ВВЕДЕНИЕ

Предварительные замечания.

Краткий обзор.

ГЛАВА 1. ФУНКЦИИ С ВЫПУКЛЫМИ МАЖОРАНТАМИ И

ВОГНУТЫМИ МИНОРАНТАМИ

1.1 Определение функций с вогнутой минорантой и сравнение с другими классами функций.

1.2. Методы построения вогнутых минорант.

1.3 Выпуклые опорные мажоранты

1.4 Задачит. и c.m.s. программирования. Локальный поиск.

1.5 Задачат. программирования. Глобальный поиск.

1.6 Использование свойств опорных функций.

1.7 Декомпозиция целевой функции в глобальной оптимизации

ГЛАВА 2. ОПТИМИЗАЦИОННЫЕ И ВЫЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ С ОДНОМЕРНЫМИт. ФУНКЦИЯМИ

2.1 Автоматическая глобальная одномернаят. оптимизация

2.2 Нахождение корней нелинейного уравнения методом вогнутых опорных функций

2.3 Нахождение действительных корней полинома на отрезке

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

ГЛАВА 3. МЕТОДЫ ОТСЕЧЕНИЙ

3.1 Предварительные замечания.

3.2 Отсечения вГ.

3.3 Отсечения в Rn+

3.4 Вогнутое продолжение.

3.5 О построении глубоких отсечений в целочисленном программировании.

3.6 Комбинация отсечений в!пи Rn+1.

3.7 Минимизация выпуклой недифференцируемой функции на выпуклом ограниченном множестве.

ГЛАВА 4. МЕТОДЫ ВЕТВЕЙ И ГРАНИЦ

4.1 Предварительные замечания.

4.2 Минимизация невыпуклой квадратичной функции на многограннике

4.3 Задача линейного программирования с одним дополнительным квадратичным ограничением-неравенством.

4.4 Глобальная минимизации дважды непрерывно дифференцируемой функции на выпуклом многограннике

4.5 Двойственные оценки в задачахт. программирования.

4.6 Метод ветвей и границ с отсечениями в К7144.

Предварительные замечания

В работе исследуется задача нахождения глобального минимума многоэкстремальной функции / на компактном подмножестве X пространства Rn, f(x) min, х е X, обладающая следующими свойствами:

А1. минимизируемая функция f в каждой точке мноэ/сества X имеет вогнутую опорную непрерывную функцию-миноранту;

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

Часть работы посвящена задаче (0.1.1), для которой, помимо А1 и А2, предполагается выполнение следующих дополнительных условий:

A3, минимизируемая функция f в каждой точке множества X имеет выпуклую опорную непрерывную функцию-маэ/соранту;

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

Два раздела современной глобальной оптимизации методически наиболее тесно связаны с исследованиями, проведёнными в работе: липшицевая оптимизация1 и d.c. оптимизация. Под задачей липшицевой оптимизации понимается задача нахождения глобального минимума липшицевой функции на компактном множестве, заданном ограничениями-неравенствами и (или) ограничениями-равенствами с липшицевыми функциями в левых частях. D.c. функция есть функция, представимая в виде разности двух выпуклых хТермин заимствован из англоязычной литературы - Lipschitz optimization.

0.1.1) функций. Если в определении задачи липшицевой оптимизации все липшицевые функции заменить на 6.с. функции, то получим определение задачи с1.с. оптимизации.

Чтобы определить место предлагаемой работы в общих исследованиях по глобальной оптимизации выделим ряд основных проблем.

Проблема I. Критерий глобальной оптимизации. К настоящему времени не разработано конструктивно проверяемых критериев глобальной оптимальности для сколько-нибудь нетривиальных классов задач. Сравним эту ситуацию с задачей нахождения точки минимума дифференцируемой выпуклой функции на К™. Точка х тогда и только тогда есть точка глобального минимума, когда в ней градиент минимизируемой функции обращается в ноль: У/(ж) = 0. Конструктивность использованного критерия (У/(ж) = 0) как это ни тривиально звучит определяется тем, что мы можем вычислить градиент в заданной точке за приемлемое время. Существующие критерии глобальной оптимальности требуют вычисления многомерного интеграла, проверки принадлежности одного выпуклого множества другому, перебор вершин многогранника и т.д. Уже в случаях нескольких переменных точное или приближённое решение подобных задач потребует недопустимо больших вычислительных затрат (например, непрерывной работы всех существующих на Земле компьютеров в течении нескольких десятилетий). Есть несколько достаточных критериев глобальной оптимальности, но они маломощны. Нет конструктивных необходимых условий именно глобальной оптимальности.

Проблема II. Нахождение точки глобального минимума. Если известно, что точка глобального минимума существует, то современные методы глобальной оптимизации в общем случае не гарантируют её нахождение за приемлемое время. Хорошим примером здесь служит задача минимизации вогнутой функции на выпуклом многограннике. Мы не только знаем, что минимум существует, но и где его искать - на множестве вершин. Тем не менее, с вычислительной точки зрения эта задача не- поддаётся решению, например, при числе переменных, превышающем 30. Здесь сказывается отсутствие критерия глобальной оптимальности. Найти вершину многогранника не проблема, проблема в том, чтобы установить является эта вершина глобальным минимумом или нет.

Проблема III. Поиск допустимой- точки. Эта проблема касается только случая невыпуклого допустимого множества X. Если известно, что множество X не пусто, решение данной проблемы облегчается, поскольку появляется аналог критерия оптимальности. Допустим, X = {ж : д{{х) =

О,г = 1 ,.,т}. Для заданной точки х мы вычислим значения gi(x) и сравним их с нулём. Если неизвестно пусто множество X или нет, то задача поиска практически также сложна, как и сама задача глобальной оптимизации.

Проблема IV. Нахождение оценки сверху. Эта проблема непосредственно связана с проблемой нахождения допустимой точки и, следовательно, для задач с выпуклой допустимой областью эффективно разрешима. Если известна допустимая точка х 6 X, то значение f(x) есть оценка сверху неизвестного минимального значения /*: >Г = inf {f(x) : а; £ X}.

В общем случае тривиальная оценка сверху равна +оо.

Проблема V. Нахождение оценки снизу. Пусть известна допустимая точка х G X. Поскольку нет конструктивного критерия глобальной оптимальности, мы не можем проверить является ли точка х точкой глобального минимума. Предположим, что /* > — оо. Попробуем оценить разность f(x) — /*. Проблема нахождения оценки снизу состоит в вычислении величины / : / < /*. Тогда f(x) — f* < f{x) — /. Тривиальное значение / = —оо.

Теория и методы липшицевой оптимизации и d.c. оптимизации предлагают разные подходы к решению указанных проблем.

Липшицевая оптимизация. Пусть / удовлетворяет условию Липшица на множестве X, т.е. существует константа L > 0 такая, что f(x)-f(y)\<L\\x-y\\ Ух,у EX. (0.1.2)

Константу L называют константой Липшица. Из (0.1.2) следует двусторонняя оценка

Ы -L\\x- у\\ < f(x) < f(y) + L\\x - у\\ Ух, уех. (0.1.3)

Поскольку X - компактное множество, то существует конечное Д > 0 такое, что ||ж — у\\ < А Ух, у € X. Тогда из (0.1.3) следует > № ~ LA, (0.1.4) где /* - глобальное минимальное значение целевой функции в задаче (0.1.1). Следовательно, зная величину А и константу Липшица L, достаточно произвести одно вычисление значения функции f(y) в произвольной точке у £ X, чтобы получить оценку снизу f(y)>f*>M-LA. (0.1.5)

Далее, предположим, что X = {х Е Мп : д(х) < 0}, где д(х) - липшицева функция с константой М. Если у ф X, то

В(у) = {х е М" : д{у) - М\\х - у\\ > 0} Р) X = 0, (0.1.6) т.е. по одной точке, не принадлежащей X можно указать открытый шар В (у), каждая точка которого также не принадлежит X. Это свойство может быть использовано при поиске допустимой точки в липишицевой оптимизации: каждый раз, когда попадается недопустимая точка, она исключается из дальнейшего рассмотрения вместе со своей окрестностью. В случае компактности X такая процедура конечна.

Проблема I в рамках липшицевой оптимизации не решена - нет критерия, который, основываясь только на известных константах Липшица, мог установить, является ли заданная точка точкой глобального минимума или нет. Проблема II разработана существенным образом. Созданы многочисленные методы и алгоритмы, комплексы программы, успешно применяемые во многих практических задачах глобальной оптимизации. Термин "практическая задача" здесь является главным, поскольку при решении конкретной задачи максимальным образом учитываются её специфические свойства: разреженность, малое количество так называемых нелинейных переменных и т.д. Размерность п отдельных задач (под которой мы будем понимать количество переменных) глобальной оптимизации, успешно решаемых методами липшицевой оптимизации может доходить до нескольких десятков. В то же время нельзя гарантировать нахождения глобального минимума методами липшицевой оптимизации любой непрерывно дифференцируемой функции на параллелепипеде, например, при п > 5. Решение проблемы III основано на построении внешних аппроксимаций вида (0.1.6) и использует те же идеи, что и методы глобального поиска, следовательно, имеет ту же эффективность. Проблемы IV и V решаются на основе двусторонней оценки (0.1.3) (см. также (0.1.4) и (0.1.5)).

О.с. оптимизация. Представление минимизируемой функции в виде разности двух выпуклых функций или с1.с. декомпозиция предоставляет более широкие возможности для решения основных проблем глобальной оптимизации. Прежде всего необходимо отметить, что существуют теоретические (нетривиальные) критерии глобального оптимума. Теоретичность этих критериев состоит в том, что они сводят проверку глобальной оптимальности к другим задачам, которые на практике так же неразрешимы, как и исходная задача глобальной оптимизации. Например, пусть в задаче минимизации невыпуклой квадратичной функции q(x) на выпуклом многограннике X задана,точка х* £ X. Проверить стационарность этой точки не трудно, для этого достаточно решить задачу линейного программирования

Vq(x*)T(x - х*) min, х 6 X.

Если оптимальное значений этой задачи неотрицательно, то х* -стационарная точка. В противополжность проверки стационарности, проверить глобальную оптимальность х* не представляется практически возможным для размерности п > 10 (для задач меньшей размерности можно осуществить прямой перебор всех стационарных точек). Квадратичную функцию можно представить в виде разности двух выпуклых квадратичных функций. Если использовать критерий глобальной оптимальности Ж.-Б. Ириарта-Уррути, то надо уметь проверять вложимость е>субдифференциала одной выпуклой функции в £-субдифференциал другой Ve > 0, как это осуществить практически неизвестно. Всё же прогресс по сравнению с лиишицевой оптимизацией при решении проблемы I существенен. Проблемы II-V разработаны гораздо глубже. Существующие детально разработанные методы позволяют решать задачи d.c оптимизации специальной структуры с числом переменных, доходящих до нескольких тысяч. Главное достоинство методов d.c. оптимизации - возможность построения выпуклой миноранты невыпуклой многоэкстремальной функции. Разность двух выпуклых функций это сумма выпуклой функции и вогнутой функции. Вогнутую функцию можно заменить аффинной аппроксимацией снизу (например, на симплексе этот приём легко осуществим). Таким способом и получается выпуклая миноранта d.c. функции, т.е. происходит приближённое овыпукление целевой функции. Аналогичным образом можно добиться приближённого овыпукления допустимой области. Оптимальное значение получившейся задачи выпуклого программирования и будет оценкой снизу оптимального значения исходной задачи d.c. оптимизации. Тем не менее теория и методы d.c. оптимизации далеки от совершенства. Для уточнения выпуклой аппроксимации приходится1 разбивать допустимую область на подобласти, что неизбежно приводит к методам ветвей и границ. Как и в случае с липшицевой оптимизацией можно указать задачи d.c. оптимизации малой размерности (п < 10), не поддающиеся практическому решению.

Идея, лежащая в основе исследований, проведённых в работе состоит в следующем.

Пусть задана задача (0.1.1). Любую функцию : X —> М. такую, что /(ж) > ф{х) Уж 6 X, будем называть минорантой функции /(ж) на X. Если существует точка у 6 X такая, что f(y) = ф(у), то функцию ?/>(ж) будем называть минорантой функции /(ж), опорной в точке ?/. Аналогичным образом, с заменой знака > на знак < определяется мажоранта и опорная мажоранта функции /(ж) на X.

С точки глобальной оптимизации интерес представляют вогнутые миноранты. Хорошо известно, что выпуклая функция, конечная в некоторой точке множества X, имеет в этой точке опорную афинную миноранту. Если исследуемая функция не является выпуклой, то данное свойство нарушается. Точнее, если функция /(ж) невыпукла, то опорную афинную миноранту можно построить не во всех точках, а , например, в тех точках, для которых /(ж) = ^(ж), где F(ж) - выпуклая оболочка функции /(ж) на X.

Вогнутую опорную миноранту можно рассматривать как обобщение афинной опорной миноранты на невыпуклый случай. Фактически, функцию, имеющую вогнутую опорную миноранту молено представить как верхнию огибающую (поточечный супремум) некоторого семейства вогнутых функции. Идея о представлении функции в виде верхней огибающей некоторого семейства функций (не обязательно вогнутых) появилась достаточно давно. Такое предстваление можно рассматривать как обобщение выпуклости. По-видимому, первой публикацией 'на эту тему была статья Э. Беккенбаха2. Достаточно общая теория обобщенной выпуклости, использующая свойства опорных функций была разработана С.С. Кутателадзе и A.M. Рубиновым3. В 90-х годах появился ряд публикаций, посвященных обобщенной выпуклости, среди которых следует отметить монографию Д. Паллашке и С. Ролевича4 и монографию И. Зингера5, исследующие вопросы обобщенной выпуклости в бесконечномерных пространствах. Все эти исследования, имея несомненный теоретический интерес, практически были трудно применимы. Главный вопрос: как для заданной функции определить ее нелинейную опорную функцию из некоторого заранее определенного класса функций оставался открытым. Существенный вклад в теорию и методы абстрактной выпуклости внёс A.M. Рубинов. В своей миографии6, а также в ряде статей им предложены*

2E.F. Beckenbach Generalized, convex functions. — Bull. Am. Math. Soc. 43, 1937. - p. 363-371

3C.C. Кутателадзе, A.M. Рубинов Двойственность Мипковского и ее приложения. - Новосибирск, Наука, 1976. - 255 с.

4D. Palaschke, S. Rolewicz Foundations of Mathematical Optimization. Convexity without linearity. - Dordrecht, Kluwer Academic Publishers, 1997

5I. Singer Abstract Convex Analysis. — New York, Wiley and Sons, 1997

6 A.M. Rubinov Abstract Convexity and Global Optimization. — Dordrecht, Kluwer Acad. Publ., 2000. конструктивные методы построения опорных функций и использования их в глобальной оптимизации. В рассмотрение были введены возрастающие, положительно однородные функции первой степени или 1РН-функции (IPH - Increasing Positively Homogeneous of degree one) и возрастающие выпуклые вдоль лучей функции или ICAR-функции (1СAR - Increasing Convex Along Rays). В качестве вспомогательных абстрактных линейных функций использовались min-функции 1(х), имеющие вид

1{х) = тт{1гхг}7. (0.1.7)

1<г<м

Нетрудно видеть, что 1{х) - кусочно-линейная вогнутая функция. IPH-функции применялись для анализа функции параметрического оптимума (или функции оптимального значения) y)=ud{f(x):g{x)<y}, yeW\.

Для минимизации IPH-функций (а также и ICAR-функций) был предложен так называемый метод отсекающего угла, непосредственно связанный с видом абстрактной линейной функции (0.1.7). В целом, абстрактная выпуклость ориентирована на развитие теории двойственности и сопутствующих этой теории направлений. Теория и методы абстрактной выпуклости интенсивно развиваются, но сравнительно с липшицевой и d.c. оптимизацией можно сказать, что абстрактная выпуклость находится на начальном этапе своего развития.

Идея, состоящая в том, что в качестве опорных функций, можно использовать произвольные вогнутые непрерывные функции впервые была высказана в работе В.П. Булатова8 в 1987 г. Там же были приведены первые примеры конструктивного построения вогнутых опорных минорант. В 1992 г. появилась статья В.И. Норкина9, обобщающая метод Пиявского (метод ломанных) на многомерный случай с обоснованием сходимости соответствующих алгоритмов и использованием опорных, в том числе вогнутых функций.

Данная диссертационная работа является продолжением начальных исследований, предпринятых в монографиях и статьях В.П. Булатова, В.И. Норкина и A.M. Рубинова. Главная цель - развитие и обоснование

7В работах A.M. Рубинова для обозначения и функции 1(х), и вектора I = ., /„), определяющего эгу функцию, используется одна и та же буква I.

8В.П Булатов Методы решения миогоэкстремалъных задач (глобальный поиск). — В кн. Методы численного анализа и оптимизации, Новосибирск, Наука, 1987. - с. 133-187

9В.И. Норкин О методе Пиявского для решения общей вадачи глобальной оптимизации - ЖВМ и МФ, т 32, N7, 1992. - с. 992-1006 нового направления в глобальной оптимизации, названного в работе с.т. программированием. Центральная идея с.т. программирования заключается в широком использовании вогнутых опорных функций-минорант и выпуклых опорных функций-мажорант. Отличие от липшицевой оптимизации состоит в более тщательном построении опорных функций и в более гибком их использовании, в частности, не обязательно определение констант Липшица или их оценок. Вогнутые функции-миноранты дают более точную аппроксимацию в окрестности опорной точки по сравнению с выпуклыми минорантами, применяемыми в с1.с. оптимизации, и в большинстве случаев построение опорной вогнутой функции - задача более простая, чем представление заданной функции в виде разности двух выпуклых функций. Основные усилия были направлены на решение проблемы II (поиск точки глобального минимума), упомянутой выше. Проблема I (критерий глобальной оптимальности) не рассматривается. В работе предложена новая методика решения проблем IV (построение оценки сверху) и V (построение оценки снизу). Оценки глобального оптимума, получаемые с помощью опорных функций более точные, что приводит к более быстрой сходимости предлагаемых методов. Кроме того, класс рассматриваемых оптимизируемых функций шире класса липшицевых и с1.с. функций, что позволяет применять методы с.т. программирования для минимизации функций, не являющихся липшицевыми или с1.с. функциями.

Основные результаты, полученные в работе, состоят в следующем.

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

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

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

3. Исследована сходимость методов отсечений в Мп и в Мп+1 для глобальной оптимизации функций с вогнутой минорантой. Предложена и обоснована модификация этих отсечений, основанная на понятии вогнутого продолжения и существенно улучшающая работу методов отсечений. Разработан метод, комбинирующий отсечения в Жп и в Мп+1. Проведено численное тестирование. Предложен новый тип глубоких отсечений для решения задач 0-1 линейного программирования.

4. Разработаны методы ветвей и границ с вогнутыми минорантами, которые: сводят вспомогательные задачи глобальной оптимизации к задачам 0-1 программирования, используют двойственные оценки, а также применяют метод отсечений в Мп+1.

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

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

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

Краткий обзор

В небольшом обзоре невозможно охватить не только существенные, но и главные направления и результаты современной глобальной оптимизации. После издания шеститомной энциклопедии оптимизации (Encyclopedia of Optimization) [164] данная задача упрощается, поскольку информацию по интересующему вопросу, относящемуся к любому разделу оптимизации и её приложениям, можно найти в этой энциклопедии. Предлагаемый ниже краткий обзор, ориентирован в основном на выявлении структурных свойств глобальной оптимизации, служащих причинами того, что во многих случаях делает её "вычислительно нетрактуемой" (computationally intractable10).

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

• липшицевая оптимизация;

• d.c. оптимизация;

• вогнутое программирование;

• обратно-выпуклое программирование;

• полуопределённое программирование (SDP) - SemiDefinite Programming;

• копозитивное программирование;

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

10Обратиое преобразование выражения compulation ally tradable, используемого в современной оптимизации программирования выходит за рамки данного обзора.

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

Начнём обзор с обсуждения использования классических методов поиска экстремума в глобальной оптимизации. Саму задачу будем формулировать в следующем виде: f(x) min, (0.2.1) хвХ, (0.2.2) где / : X —> Rn - полунепрерывная снизу функция, X С R" - компактное множество. Предположение о компактности X может показаться ограничительным, поскольку во многих практически (и теоретически) значимых задачах глобальной оптимизации множество X является неограниченным или даже незамкнутым. Тем не менее, требование компактности допустимой областью не является завышенным. Во-первых, на практике почти всегда существуют пределы изменения переменных х G П = {—оо < Xj < Xj < Wj < +00, j = 1,., 77.}. (0.2.3)

Во-вторых, задачи с компактной допустимой областью чрезвычайно трудны и на данном этапе развития теории и методов глобальной оптимизации само свойство компактности принципиально не облегчает нахождение глобального минимума. В-третьих, при сделанных предположениях условие X ф 0 автоматически влечет за собой существование решения задачи (0.2.1)-(0.2.2) и мы можем сконцентрироваться на проблеме нахождения этого решения.

Многие задачи исключительной практической представимы в виде (0.2.1)-(0.2.2). К ним относятся задачи прогнозирования молекулярных структур в химии и биологии [201]; задачи механики с невыпуклым потенциалом [188]; задачи разработки различных физико- и химико-технических устройств [73], [131], [132], [92]; задачи производственного типа [96]; задачи нелинейной регрессии [34]; задачи моделирования нефтеперерабатывающих и нефтехимических процессов [78]; прикладные задачи энергетики [91], [26]; задачи нелинейного экономического моделирования [189]; задачи оптимального управления [17], [190]; задачи равновесного программирования [8], [52], [97]; задачи двухуровневого программирования [47], [140], [161]; задачи системного анализа [68], [69] и многие, многие другие (например, даже такие, как задача оптимального гранения алмазов [185]).

Исследования по глобальной оптимизации за последние 20 лет существенно усилились. Появился новый специализированный международный журнал "Journal of Global Optimization", выпускаемый издательством Kluwer Academic Publishers. Этим же издательством организована серия публикаций но теме "Nonconvex Optimization and Its Applications" и к настоящему времени издано 90 томов монографий, трудов конференций, сборников статей и т.д. К наиболее существенным мнографиям по глобальной оптимизации, изданным в России, относятся [17], [33], [49], [72], [73], [78], [92], [96], [94], [95], [98], [124]. Кроме того, многочисленные статьи по глобальной оптимизации публикуются в различных центральных журналах у нас и за рубежом. Не будет большим преувеличением сказать, что общее число работ по глобальной оптимизации превышает несколько тысяч. Поэтому, прежде, чем выделить место данной работы в общем потоке публикаций, необходимо в определенной степени систематизировать основные результаты, полученные в глобальной оптимизации к настоящему времени, а также указать принципиальные трудности и практического, ,и теоретического характера.

Начнём со следующего, частного случая задачи (0.2.1)-(0.2.2), а именно будем предполагать, что / G С1, где С1, как обычно, есть множество дифференцируемых функций с непрерывными частными производными, X = П, П определено в (0.2.3), точка глобального минимума х* € mi(n), int(P) - внутренность множества П. Тогда в силу необходимых условий оптимальности

Vf(x*) = О11. (0.2.4)

Большего классическая теория экустремума не дает. Условию стационарности (0.2.4) удовлетворяют и точки, минимума, и точки максимума, и точки перегиба. Принципиально не улучшает ситуацию и требование гладкости любого порядка функции /. Для решения

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

Если в дополнение к сделанным предположениям считать, что / выпуклая функция, а X - выпуклое множество, то задача (0.2.1)-(0.2.2) уже поддаётся решению. В этом случае критерий стационарности (0.2.4) при условии х* G int(X) превращается в критерий глобальной оптимальности. На наш взгляд условие (0.2.4) - важнейшее аналитическое средство, позволяющее в ряде случаев решать задачу (0.2.1)-(0.2.2) без использования итеративных процедур (например, в случае, когда f(x) = xTQx + стх, где Q - положительно определённая матрица). Вообще, возможность решать задачи малой размерности, например, с двумя или тремя переменными "вручную", т.е. используя только карандаш и бумагу, при помощи того или иного критерия глобальной оптимальности является характеристикой эффективности этого критерия. Малая размерность не должна вводить в заблуждение. Примером тому служит функция Шуберта fs(x 1,ж2)= ^У^ г cos [(г + l)si + i]J • i cos [(i + l)x2 + . В области

Us = {(si, x2) : -10 < Xi < 10, г = 1,2} эта функция имеет 760 локальных минимумов, 18 из которых являются глобальными. Применение "вручную" только критерия (0.2.4) для задачи глобальной минимизации функции fs{xi-> ^2) на множестве П5 с последующей отбраковкой точек максимума и перегиба лежит за пределами нормальных человеческих способностей12.

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

12Стоит отметить, что для данного примера "автоматизация" этой процедуры при помощи компьютера — также достаточно трудоёмкой процесс оптимальности? Для прояснения существа вопроса откажемся временно от требования компактности X. Предположим, например, что f(x) дважды непрерывно дифференцируема, имеет единственную стационарную точку х* на Rn и в этой точке выполняются достаточные условия локального минимума второго порядка. Казалось бы, что в этих условиях точка х* обязана быть точкой глобального минимума, ведь других-то стационарных точек нет. Оказывается, что такой вывод справедлив только для функции одной переменной. Пусть (см. [184]) f{xi,x2) = е3*2 - 3a;ieX2 + xf. (0.2.5)

Тогда х* = (1)0) - единственная стационарная точка и матрица вторых производных в этой точке положительно определена, тем не менее функция p(xi) = f{xh0) = l-3xi+xl не ограничена снизу и, следовательно, х* не есть точка глобального минимума. Причина полученного эффекта в том, что точки глобального минимума в данном примере не существует. Для функций одного переменного подобный пример построить не удаётся - чтобы выбраться из "локальной ямы и спуститься ниже" необходимо пройти через точку локального максимума, следовательно, должна существовать вторая стационарная точка. (Рассмотренный пример ещё раз подчёркивает важность свойства компактности допустимой области - в таких задачах решение существует всегда, следовательно, указанного выше эффекта быть не может).

Вернемся к задаче (0.2.1)-(0.2.2) с полунепрерывной снизу функцией / и компактным множеством X. Пусть ArgLocMin(f,X) - множество локальных минимумов рассматриваемой задачи, ArgGlobMin(f, X) -множество глобальных минимумов. Очевидно, что в общем случае ArgLocMin(f, X) Э ArgGlobMin(f,X). Приведем краткое описание класса задач (см. [207], [241], [242]), для которых

ArgLocMin{f, X) = ArgGlobMin(f, X). (0.2.6)

Свойство (0.2.6), присущее задачам выпуклого программирования, позволяет нам оставаться в рамках локального анализа (например, анализа при помощи производных в случае дифференцируемости /). Определим стандартным образом множества е X : f(x) < а},

Gjjc = {а е R : LftX(a) ф 0}.

Точечно-множественное отображение Ljtx называется полунепрерывным снизу в точке а, если х е Lftx(a), oik € GfjX, lim ак = а) (3{жЛ} : ж* € LfiX{otk), lim хк = х) . к—>сх> / \ к—>оо J

Теорему, определяющую условия, при которых выполняется (0.2.6), будем для краткости называть ЛГ-Теоремой (Локально-Глобальной Теоремой).

ЛГ-Теорема ([207],[241]). Равенство (0.2.6) выполняется тогда и только тогда, когда точечно-мноэюественное отображение Lf)X полунепрерывно снизу для любого а б G^X

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

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

Предположим, что для некоторой конкретной задачи вида (0.2.1)-(0.2.2) удалось доказать полунепрерывность снизу точечно-множественного отображения Lfíx■ Тогда по ЛГ-Теореме каждый локальный минимум является глобальным. Возникает вспомогательная задача: как установить, что заданная точка х* является локальным минимумом? Как следует из [216] эта задача может оказаться весьма нетривиальной даже для невыпуклой квадратичной функции /. Если, например, / е С2, х* е int{X), Vf(x*) = О и матрица вторых производных вырождена в х*, то в общем случае гарантирована лишь стационарность ж*. Точка х* может оказаться седловой точкой, а не локальным минимумом. Необходимо ещё иметь в виду, что даже в случае выполнения равенства (0.2.6) рассматриваемая задача может иметь много локальных, изолированных минимумов и все они будут глобальными, простейшим примером тому служит функция f(x) — sin(a;).

Сделаем ещё один шаг в направлении практической применимости условия (0.2.6) в задачах невыпуклого программирования. Перейдем описанию класса задач, в которых каждая стационарная точка будет точкой глобального минимума ([207], [243]). Для упрощения изложения будем предполагать дифференцируемость / и выпуклость X (в [243] приводимая ниже СГ-Теорема доказывается при более общих предположениях). Точечно-множественное отображение Lf x называется строго полунепрерывным снизу, если

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

СГ-Теорема ([207],[243]). Каждая стационарная точка задачи (0.2.1)-(0.2.2) с дифференцируемой функцией / и выпуклым множеством X является точкой глобального минимума тогда и только тогда, когда точечно-множественное отображение Ь^х строго полунепрерывно снизу для любого а е С/^

Геометрическая интерпретация СГ-Теоремы и определения строгой полунепрерывности отображения Ь^х снизу приведена на рис. 0.2. х е Lfjx{oi): a.k е G/д lim dk = а

3{xfc},3/3(a;)>0: xk 6 L^x{oik ~ (3{x)\\xk — ж||), lim xk = x

Рис. 0.2. Геометрическая интерпретация строгой полунепрерывности снизу отображения Lf^x-' а) отображение Lj^x является строго полунепрерывным снизу, последовательность {ж^} сходится к х, функция f(x) не имеет точек перегиба; б) отображение L^x является (нестрого) полунепрерывным снизу, последовательность {а^} не сходится к х, х - точка перегиба f(x).

ЛГ-Теорема и СГ-Теорема характеризуют свойства задачи (0.2.1)-(0.2.2) в терминах свойств соответствующих точечно-множественных отображений. Более привычным на практике является анализ свойств, например, целевой функции на основании её аналитического вида. Перейдем к описанию результата, аналогичному СГ-Теореме, но сформулированному в других терминах. Важнейшим свойством выпуклой дифференцируемой на Мп функции / является выполнение неравенства f(x) - f(y) > Vf(y)T(x - у) Vx, у Е Rn. (0.2.7)

Данное неравенство лежит в основе глобальной оптимальности выпуклых дифференцируемых функций: если Vf(y) = 0, то из (0.2.7) следует, что у -оптимальное решение. Обобщая неравенство (0.2.7) указанным ниже образом (см. [207], [178]), получаем определение инвексной функции. Будем говорить, что дифференцируемая функция / является инвексной если существует вектор-функция т?: X х X —> Rn такая, что W - ш > Vf[y)Tri& у) Vs, У € х. (0.2.8)

Отличие (0.2.7) от (0.2.8) состоит в замене разности х — у вектор-функцией т](х,у). Нетрудно видеть, что в задаче безусловной минимизации инвексной функции каждая стационарная точка является точкой глобального минимума. Вектор-функция может быть недифференцируемой, нелинейной и т.д., важно лишь, чтобы она существовала. Переход от стандартного выражения х — у к вектор-функции г)(х, у) можно связывать с преобразованием переменных, при котором инвекспая функция есть результат "нелинейного преобразования" (или трансформации) некоторой выпуклой функции, отсюда происходит и само название: invex есть сокращение от invariant convex (более подробное описание см. в [207]).

Пусть f{x) = g{W(x)), д : Rm R, W{x) = (wi(x),. . ,wm(x)), W : —j- RTO, g - выпуклая дифференцируемая функция. Тогда f(x) - f(y) = g(W(x)) - g(W(y)) > Vg(W(y)f(W(x) - W(y)). (0.2.9)

Сравнивая (0.2.8) и (0.2.9), видим, что функция / будет инвексной, если существует т)(х, у):

Vg(W(y))T(W(x) - W(y)) = Vf{y)Tri(x,y) = Vg(W(y))TVW{y)Tr1(xiy)i где VW(y) - матрица Якоби вектор-функции W в точке у. Следовательно, если т](х, у) есть решение системы

VW(y)Trj(x,y) = W(x) - W{y) Ух G Rn,Vy G Ж", (0.2.10) то / - инвексная функция.

Рассмотрим в качестве примера функцию Розенброка f{xhx2) = 100(^2 - х\)2 + (.г-! - I)2 = g{W(x)\ гдед(гг) = и\-\-и\, W(x) = (wi(x), w2(x)), wi(x) = 10(x2 - xf), w2(x) = Ж1 — 1. Решением соответствующей системы (0.2.10) будет у)=х 1 - у) = х2 - х\ - у2 + у{ + 2у\{х\ - у{).

Следовательно, функция Розенброка есть инвексная функция.

Для всякой инвексной функции стационарная точка является точкой глобального минимума. Оказывается, инвексная функция удовлетворяет условиям СГ-Теоремы.

Теорема инвексности I ([207]). Дифференцируемая функция / является индексной тогда и только тогда, когда её точечно множественное отображение L/дп является строго полунепрерывным снизу.

Из данной теоремы следует, что класс функций, для которых стационарные точки являются точками глобального минимума состоит из инвексных функция. Известно, что [207] псевдовыпуклые функции также являются инвексными. Функция Розенброка не является псевдовыпуклой -её множества Лебега (или множества уровня) невыпуклы. Следовательно, класс инвексных функций шире класса псевдовыпуклых функций.

Свойство инвексности можно распространить и на задачи с ограничениями. Пусть задана задача с ограничениями-неравенствами fo(x) min, (0.2.11) fi{%) < 0,i = 1,. ,m, • (0.2.12) в которой дифференцируемые функции /¿,г = 0, .,т удовлетворяют условию инвексности (0.2.8) относительно одной и той же вектор-функции V

1г{х) - fi{y) > Vfi(y)Tr)(x, у), i = 0,., т.

Такую задачу будем называть задачей инвексного программирования. В ([178]) доказано следующее утверждение.

Теорема инвексности II. Пусть х* - точка, в которой выполняется какое-либо условие регулярности (например, условие линейной независимости градиентов У/г-(ж*)) и необходимые условия первого порядка. Тогда х* - точка глобального минимума задачи инвексного программирования (0.2.11)-(0.2.12).

Приведём пример (снова из [178]) задачи инвексного программирования: о (ж) = х\ — sin^) —min, fi{x) = sin(a;i) — 4sin(a;2) < 0, f2(x) = 2sin(a;i) + 7sm(x2) + x\ - 6 < 0, /з(ж) = + 2ж2 - 3 < 0, f4{x) = 4xf + 4x1 ~ 9 < 0, /5(ж) = - sin(o;i) < 0, б(ж) = - 8т(ж2) < ОВсе функции г = 0,., 6 удовлетворяют условию инвексности с

В стационарной точке х* = (0, агсйт(|)) вектор функция т](х,х*) определена, следовательно, х* - точка глобального минимума. Геометрическая интерпретация данной задачи приведена на рис. 0.3.

Рис. 0.3. Допустимая область, линии уровня целевой функции и оптимальное решение х* для рассматриваемого примера инвексной задачи.

Условие инвексности (0.2.8) в сочетании с системой (0.2.10) дают определённые конструктивные средства к анализу задач невыпуклого программирования, в которых каждая стационарная точка является точкой глобального минимума. Детальному изучению задач инвексного программирования посвящена монография [207].

Напомним ещё раз, что задачу инвексного программирования можно рассматривать как нелинейное преобразование задачи выпуклого программирования. Однако существование такого преобразования может оказаться очень сильным требованием. Преобразование определяется вектор-функцией г/, единой для для всех функций, описывающих задачу (0.2.11)-(0.2.12), т.е. если даже каждая функция /г инвексна относительно некоторой своей вектор функции вся задача (0.2.11)-(0.2.12) в целом может не быть задачей инвнексного программирования. Ограниченность применения свойства инвексности подчёркивает следующий результат

-I 4

204]: если все функции-ограничения фг,г = 1 , .,т в задаче вида (0.2.11)-(0.2.12) аффипны, то такая задача будет задачей инвексного программирования в том и только том случае, когда целевая функция /о есть дифференцируемая выпуклая функция. В этом случае мы снова не выходим за рамки задач выпуклого программирования.

Упомянем еще одно свойство задач, в которых каждая стационарная точка есть точка глобального минимума. Как показано в [182], [203] связность множеств уровня LfJx{c¿) 6 С^дх есть необходимое свойство таких задач.

Вернёмся к примеру с функцией (0.2.5). Как говорилось выше, причиной того, что единственная стационарная точка, являющаяся точкой строгого локального минимума, не есть точка глобального минимума, служит неограниченность множества X. Существуют и другие примеры подобного рода, в которых множество X ограничено, но открыто. Можно предположить, что в случае компактности множества X единственная стационарная точка, удовлетворяющая достаточным условиям второго порядка, будет точкой глобального минимума. Оказывается кроме компактности множество X должно снова обладать свойством связности. В [28], [29] доказан следующий результат: для того, чтобы в задаче математического программирования с непрерывно дифференцируемой целевой функцией и непрерывно дифференцируемыми ' функциями-ограничениями, определяющими компактную связную допустимую область, каэ/сдая стационарная точка, удовлетворяющая условияль регулярности Эрроу-Гурвица-Удзавы ¡38}, была точкой глобального минимума необходимо и достаточно, чтобы такая точка была точкой локального минимума. На основании этого результата можно предложить следующую схему исследования задачи математичесого программирования. Если удается показать, что каждая стационарная точка является изолированным минимумом (например, при помощи теоремы Мак-Кормика [104]), то, очевидно, эта точка и есть точка глобального минимума.

Рассмотрим следующий пример

Очевидно, что данная задача является невыпуклой. Нетрудно проверить, что ограничения задачи (0.2.13)-(0.2.16) удовлетворяют условиям регулярности тт/(ж) = 4гсх — х\ — 12, ы{х) = 25 - х\ - х\ = О, дг(х) = х'{ - 10.Т1 + х\ - 10ж2 + 34 < О, XI >0, х2 > 0.

0.2.13)

0.2.14) (0.2.15) (0.2.16)

Эрроу-Гурвица-Удзавы. Функция Лагранжа имеет вид

Ь (ж, Ах, (11,112, А*з) = - х\ - 12 + Ах (25 - ж? - я?!) +

4-/11 (ж? - Юж1 + х\ - 10ж2 + 34) - (12хг - (1зх2.

Стационарные точки задачи (0.2.13)-(0.2.16) являются точками, удовлетворяющими условиям дЬ (ж, АI,/1Ъ (12, (1з) дх\ 4 - 2жхАх + /л (2ж1 - 10) -(12 = 0, (0.2.17) дЬ{х,\1(11, (12,ц,) = 2жз 2А1Ж2 + ^ = аж1

И (ж? - 10ж1 + х\ - Юж2 + 34) = 0, (0.2.19)

12 XI = 0, (0.2.20)

13X2 = о, (0.2.21)

АЛ >0,м2>0,/х3>0, (0.2.22)

Ах| + /Л + /¿2 + ^3 ф о. (0.2.23) Матрица вторых производных функции Лагранжа имеет вид

Агх {Х,\х,(1х,(12,(1з) = ^

2Ах + 2//1 О

О -2 - 2А1 + 2(1\

Проведя достаточно аккуратный, но не очень сложный анализ, можно показать, что для любого набора [х\, х*2, ¡1\, (12, (1%), удовлетворяющего условиям (0.2.17)-(0.2.23) и такого, что ж^ > 0 и х2 > 0 справедливо строгое неравенство

2Х[ + 2ц\ > 2.

Следовательно, матрица Ьхх (ж*, А*, (1*) положительно определена, что, в силу теоремы Мак-Кормика, означает, что стационарная точка х* — (ж^, ж2) является точкой строгого локального минимума. Тогда в силу результата, приведённого выше, точка ж есть точка глобального минимума. Множество точек глобального минимума в данном случае должно быть связным, следовательно, ж* - единственная точка глобального минимума. Геометрическая интерпретация данного примера приведена на рис. 0.4.

1(®) = 0 б 4

2 0 О 2 4 б 8

10

12

Рис. 0.4. Геометрическая интерпретация решения задачи (0.2.13)-(0.2.16).

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

Теорема Уитни. Пусть А С Мп - замкнутое множество. Тогда существует функция к 6 С00 такая, что А — {х £ : Н(х) = 0}.

Множество А может быть сколь угодно "безобразным", тем не менее существует бесконечное число раз дифференцируемая функция, точно аппроксимирующая это множество, лишь бы оно было замкнутым. Далее, достаточно от функции к(х) перейти к функции /г2 (ж), чтобы множество А стало множеством точек глобального минимума и в заключение представить в качестве А канторово множество или "ковёр Серпинского". Неотрицательную бесконечно гладкую функцию одной переменной, обращающуюся в ноль на канторовом множеством назовем функцией Уитни канторового множества, а неотрицательную бесконечно гладкую функцию двух переменных, обращающуюся в ноль на "ковре Серпинского" - функцией Уитни "ковра Серпинского".

Пусть в задаче (0.2.1)-(0.2.2) / е С°° и X - выпуклое компактное множество. Предположим, что вычислены значения самой функции /(х) и её производных любого порядка на любом конечном наборе точек из X. Тогда, как указано в [185], невозможно из выбранного набора точек указать такую точку х*, что ж*) > rain{/(i) : х Е X} — 6 хотя бы для некоторого 6 > 0. Причина в том, что всегда найдётся точка у Е X и некоторая окрестность этой точки, в которую не попадает ни одна из точек выбранного ранее набора. Не нарушая свойства дифференцируемости, можно модифицировать функцию f{x) внутри окрестности точки у так, что f(y) будет принимать любое заранее заданное конечное значение. Другими словами нельзя определить даже сколь угодно грубую оценку снизу бесконечно дифференцируемой функции за конечное число испытаний, основываясь только на значениях самой функции и её производных.

Наиболее благоприятным структурным свойством среди нелинейных задач оптимизации является выпуклость. Поэтому естественным является стремление аппроксимировать многоэкстремальные функции выпуклыми. Предположим, что множество X в задаче (0.2.1)-(0.2.2) выпукло. Выпуклой оболочкой функции f(x) на X называется функция F : X —> R такая, что i. F(x) выпукла на X; и. F(x) < f(x), Vx Е X : iii. не существует функции Ф : X —► R, удовлетворяющей ¡., ii. и такой, что F (х) < Ф (ж) для некоторой точки х G X.

Нетрудно показать, что min f(x) — minF(x) хеХ хеХ и arg min F(x) D arg min f(x). x&X x£X

Теоретически функцию F(x) можно всегда построить, используя понятие сопряженной (по Фенхелю) функции: f(y) = sup {yTx-f(x)} (0.2.24) хех

Хорошо известно, что f**(x) = F(x). Однако, в силу (0.2.24) вычисление одного значения сопряженной функции - задача той же сложности, что и исходная задача глобальной оптимизации.

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

П2 - {(х,у) ER2 : а< х <ä, Ь< у <Ц задана функция f(x, у) = ху. Как показано в [133] функция

F(x, у) = max {bx + ау — аЪ, bx + ау — об} является выпуклой оболочкой f(x,y) на Щ. Далее, пусть требуется решить задачу min /(ж, у) = стх + хту + dTy, (0.2.25) х G Пж = {х : а{ < Х{ < щ, г — 1,., п} , (0.2.26) уеИу={у: h < Уг < bh г = 1,. ,п} , (0.2.27) c,d G ]Rn. Задачу (0.2.25)-(0.2.27) можно заменить выпуклой задачей min |F(x, у) = Fi (xi} уг) I, (x,y) G Па, x Пу, где

Fi (х^ yi) = max {Ь{х{ + ацл - а{Ьг) hxi + агуг - а^н) , i = 1,., п.

Существует ещё несколько примеров построения выпуклой оболочки невыпуклой функции (см. [185]), все они носят частный характер и проблема построения выпуклой оболочки для широкого класса функций остаётся открытой.

Структурным свойством обладают дважды непрерывно дифференцируемые функции на компактном множестве X. Такие функции могут быть представлены в виде разности двух выпуклых функций, следовательно являются d.c. функциями. Структурность эта следует из ограниченности второй производной на X. Бесконечно дифференцируемые функции составляют подмножество множества дважды непрерывно дифференцируемых функций. Поэтому, если рассматривать функцию Уитни канторового множества на отрезке [0,1] и функцию Уитни "ковра Серпинского" на квадрате [0,1] х [0,1], то обе эти функции также являются d.c. функциями. Эффект d.c. декомпозиции геометрически изображён на рис. 0.5.

7 • 9(х)

Рис. 0.5. Непрерывной линией показана d.c. функция f(x) = д(х) — h(x); пунктирными линиями показаны функции 7 • д(х) и —7 • h(x); 7 << 1 масштабирующий множитель.

Обнаружение свойств скрытой выпуклости и антивыпуклости (вогнутости) служит мощным стимулом развития теории и методов d.c. оптимизации.

Перейдем к краткому рассмотрению критериев глобальной оптимальности. Пусть f(x) - непрерывная функция. Обозначим через li{M) (лебегову) меру подмножества Мс1"и пусть

Sc = {xeX: f(x) < с} , сек.

Определим величину

0 = -tVT [

Точка х* есть точка глобального минимума /(ж) на X тогда и только тогда, когда

М(/,Л = Г, Г = /(®-). (0.2.28)

Чисто теоретически схема решения задачи глобальной минимизации, основанная па критерии (0.2.28), предложена в [170]. В [244] эта схема комбинируется с методом штрафных функций и приведен численный пример, однако этот подход трудно осуществим для достаточно широкого класса функций из-за сложности вычисления величин ß(S) и М(/, с).

В [96] предложены критерии глобальной оптимальности, основную идею которых кратко опишем на примере для задачи максимизации выпуклой функции /(ж) на компактном мноржестве X С Rn. Если точка х* является глобальным максимумом в данной задаче то

Уу ■■ f(y) = f(x*), Vy* € дf(y) (у*)Т(х ~ У) > 0, Уж 6 X. (0.2.29)

Если в дополнение к условиям (0.2.29)

3v е Rn : f{v) < f{x*) < +00, то следующее условие

Vy : f(y) = Дж*), Зу* е df(y) (jу*)т(х - у) > 0, Уж G X является достаточным условием глобальной оптимальности. В [96] на основе условия (0.2.29) описан ряд вычислительных процедур решения некоторых специальных задач глобальной оптимизации. С теоретической точки зрения условие (0.2.29) можно рассматривать как обобщение известных условий глобальной оптимизации для задач выпуклого программирования. На практике, на наш взгляд, условие (0.2.29) трудно для проверки. В [180] рассматривается задача безусловной d.c. оптимизации min {/(ж) = д{ж) - /г(ж)} , (0.2.30) жеЛТ, где д( ж), h{ ж) - полунепрерывные снизу выпуклые функции и описывается критерий глобального минимума для задачи (0.2.30) в терминах е-субдифференциалов функций д(ж) и h(ж). Напомним, что е-субдифференциалом выпуклой функции д (ж) в точке ж0 называется множество <9е/(ж°) векторов р таких, что д{ж) > д(х°) + рт (ж - ж0) - е, Уж G Rn, а элементы р G def(x°) называются / в точке ж0. При £ = 0 это определение совпадает с определением обычного субдифференциала выпуклой функции. Существенным отличием £-субдифференциала является его нелокальный характер. Этот факт затрудняет, например, определение всех е-субградиентов в данной точке, хотя вычисление отдельного е-субградиента может являться существенно более легкой задачей, чем определение субградиента (см., например, [81]). В [77] показано, что все характеристики выпуклой функции, включая ее значение в произвольной точке пространства могут быть восстановлены по е-субдифференциалу этой функции в некоторой фиксированной точке области ее определения. Свойства £-субдифференциала позволили Л.В. Ншаг^ипт^у сформулировать следующий критерий глобальной оптимальности для задачи (0.2.30): точка х* является точкой глобального минимума в задаче (0.2.30) тогда и только тогда, когда дЕк{х*) э дед(х*), Уе > 0. (0.2.31)

Применение критерия (0.2.31) связано с трудностями определения дек{х*) и д£д(х*). Тем не менее, используя теорию £-субдифференциального исчисления ([179]), критерий можно также использовать при решении некоторых задач глобальной минимизации.

В [185] кратко описаны другие критерии глобальной оптимальности. В настоящее время они могут иметь лишь ограниченное применение для частных случаев задачи (0.2.1)-(0.2.2). Можно поступать и следующим образом. Рассматривая конкретную задачу глобальной оптимизации и используя специфические, только ей присущие, свойства, попытаться применить какой-либо критерий глобальной оптимальности, которой для данной задачи может сработать.

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

Результаты работы процедуры CUT™*1 при е = 10 5 следующие. Было сделано 46 итераций, найденное рекордное значение целевой функции /46 = 49318.017968, w46 = х*, = х\\ = 49312.919922. Абсолютная погрешность /46 — = 5.098, относительная погрешность

46 7 = 0.0001.

46

Таким образом, в пределах указанной точности рекордное решение, приведенное в [167], действительно является глобальным минимумом. Процедура CUT"+1 не только нашла это решение, но и доказала его глобальную оптимальность.

Главное достоинство метода отсечений состоит в том, что фактически решается задача линейного программирования с возможно большим числом ограничений. Одна итерация метода генерирует одно дополнительное ограничение. В данном примере количество итераций равно 46, следовательно, сгенерировано 46 дополнительных линейных ограничений. Количество линейных ограничений в исходной задаче равно 10 (не считая условий неотрицательности). Поэтому, с практической точки зрения решена задача линейного программирования с числом переменных п = 21 и 56 ограничениями-неравенствами.

3.4. Вогнутое продолжение

В данном параграфе описывается методика впервые примененная в [151]. Главная ее идея состоит в следующем. При решении задачи минимизации функции f(x) на компактном множестве X поведение этой функции вне X играет второстепенную роль. На этом факте основаны главные конструкции данного параграфа. Рассматривается задача минимизации вогнутой функции f(x) на выпуклом многограннике X. Основная цель -описать механизм, позволяющий строить более глубокие отсечения в Жп+1. При этом оказывается, что если существует точка безусловного максимума

Хтах фущ<ЦИИ f(x)

Хтах е Argmax{f(x) :жбГ} такая, что хтах ф X, то удается определении вспомогательную вогнутую функцию F(x) совпадающую с f(x) на множестве X и имеющую рецессивные направления даже в том случае, когда исходная функция f(x) рецессивных направлений не имеет. Естественно затем рассматривать задачу минимизации функции F(x) на X и тем самым увеличить глубину отсечений в Rn+1. Сформулируем основную задачу параграфа fix) —» min,

JK J ' (3.4.1) x e X, K ) где f(x) - вогнутая дифференцируемая функция, X - выпуклое компактное множество.

Определение 3.1. Функция\¥(х) называется вогнутым продолжением функции f(x) на множестве X, если выполняются следующие условия

1. W{x) - непрерывная вогнутая функция;

2. W{x) = f{x) Ух G X;

3. W{x) > fix) Ух е Мп.

Множество всех вогнутых продолжений Wix) на X будем обозначать EXT(f, X). Очевидно, что / <Е EXTif, X).

Определение 3.2. Функция Fix) называется максимальным вогнутым продолжением функции fix) на множестве X, если

1. Fe EXTif, X);

2. Fix) > Wix) Ух e Mn, yW g EXTif, X).

Теорема 3.5. Максимальное вогнутое продолжение Fix) вогнутой дифференцируемой функции fix) на выпуклом компактном множестве X определяется следующим образом

Fix) = min {fiy) + Vfiyfix - у)}. (3.4.2) y&X

Доказательство. Пусть т G [0, l],^1,^2 6 X, тогда

Firx1 + (1 - т)х2) = min {fiy) + Vfiy)Tirxl + (1 - т)х2 - у)} = уех mmfrl/M + Vfiyfix1 - у)] + (1 - т)Ш + V f(y)T(x2 - у))} > уех тmm{fiy) + Vfiy^ix1 - у)} + (1 - г) min{/(y) + S7f(y)T{x2 - у)} = уех уех TF(x1) + {l-T)F(a?).

Таким образом, Fix) - вогнутая, конечная в лобой точке пространства функция (следовательно, непрерывная). В силу вогнутости f{x)<f{y) + Vf(y)T(x-y)Vx,y. 170

Поэтому ж) < mm{f(y) + Vf(y)T(x - у)} = F(x) Ух. y&X

Нетрудно видеть, что F(x) ~ fix) при х Е X. Если д Е EXT(f, X) - другая вогнутая функция, то повторив последние два неравенства для д(х), получим д(х) < F(x). □

Введем в рассмотрение множество

D = {d Е Rn : d = Vf{x), х Е X}, которое назовём образом градиентного отображения множества X и co(D) -выпуклую оболочку D.

Теорема 3.6. Предположим, что

О ф int(co(D)). (3.4.3)

Тогда F(x) имеет рецессивное направление.

Доказательство. Пусть ж £ X. В силу вогнутости f(x) и условия Л > О имеем

F(x + Ati) = m m{f{y) + Vf(y)T(x + А и- y)} = yex ${f(v) + V/(y)T(^ - y) + AVf(y)Tu} > (3.4.4) x) + Amin{V/(|/)TM}. yeA

Из (3.4.3) следует существование вектора р такого, что pTd > О Уd Е co(D), следовательно, pTVf{y) > 0 Уу Е X.

Полагая и = р в (3.4.4) и учитывая, что F(x) = f(x) Ух Е X, получаем

F(x + \p) > F{x). (3.4.5)

Известно [86], что если неравенство (3.4.5) справедливо в точке ж, то в силу вогнутости F(ж) оно справедливо Ух Е Мп, что и означает, что р определяет рецессивное направление F(ж). □

К сожалению, в общем случае образ градиентного отображения выпуклого множества не является выпуклым. Примером этому служит функция х 1,*») = ^, приведенная в [86] и рассматриваемая на множестве {(ж^жг) : х2 > 0}. Соответствующий образ градиентного отображения не является выпуклым и представляет собой параболу

X X2

D = {(di, d2) : d2 = -dl di = d2 =

Максимальное вогнутое продолжение имеет смысл в том случае, когда задача (3.4.2) практически разрешима.

Пример 3.4. Функция f(x) - вогнутая квадратичная функция ж) = xTQx,

Q - отрицательно полуопределенная симметричная матрица. Тогда

F(x) = min{yTQy + 2yTQ{x - у)} = min{2yTQx - yTQy}. (3.4.6) жех xex

Следовательно, вычисление функции F(x) в точке эквивалентно решению задаче выпуклого программирования (3.4.6). Кроме того, в силу линейности градиентного отображения квадратичной функции Теорему 3.6 можно уточнить следующим образом. Теорема 3.7. Если

0 ф int{X), (3.4.7) то F(x) имеет рецессивное направление.

Доказательство. В силу условий теоремы существует вектр р £ Rn, р ф 0 такой, что рТу > 0 WyeX.

Градиент квадратичной функции V/(y) = 2Qy. Выражение Wf(y)Tu имеет вид 2yTQu. Определим направление и так, чтобы Qu = р, тогда Vf(y)Tu = 2yTQu > 0. Далее по аналогии с доказательством Теоремы 3.6 и из (3.4.4) следует F(x + Xи) > F(x). □

В случае сильной вогнутости квадратичной функции f(x) условие (3.4.7) эквивалентно тому, что точка безусловного максимума /(ж) не принадлежит внутренности X. п

Пример 3.5. Функция /(ж) = fi{xi) ~ вогнутая дважды

2=1 дифференцируемая сепарабельная функция,

X = {ж Е Шп : ж < ж < ж}

- параллелепипед. В этом случае п П

F(x) = mm{]T Ш + fi(y)(Xi - Vi)} = ]Г Шу) + ~Vi)}. уел . S.iSyiS:Xi

1=1 г=1

Пусть при фиксированном Х{

Ui(yi) = fi{y) + ЛЫО* - Vi)'

Тогда Л(Ю) + Я'ЫО* - У<) - /'fei) = " Vi).

В силу вогнутости f"(yi) < 0. Поэтом, если Xi < xh то ш'(уг) > 0 - функция Lüi(yi) монотонно не возрастает, если Х{ > Х{, то ш'(уг) < 0 - функция Ui(yi) монотонно не убывает. Следовательно, п г=1 где г(ш.г / (х^)(х{ х{), х{ < x^ { лм, & < хг < хг, (3.4.9) г / {Х{)(^Х{ Хг Х{.

В качестве тестовой задачи рассматривалась задача нахождения наиболее удаленной точки выпуклого многогранника X С Ж". Формальная запись этой задачи в виде задачи вогнутого программирования имеет вид = -М2^пип, . гс 6 X = {х е Ж^ : Ах < 6}, V • • ; где А - т х п матрица, Ъ 6 Жт. Очевидно, что целевая функция в (3.4.10)

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

Данные генерировались случайным образом. Результаты вычислений приведены в Таблице 3.1. Обозначения имеют следующий смысл: п - число переменных, т - число линейных ограничений, Д - рекордное значение целевой функции, - полученная оценка снизу, к - число итераций, еавэ

- абсолютная погрешность, £леь - относительная погрешность, fk-xk n+l fk

Если абсолютная погрешность была меньше Ю-3, то вычисления прекращались. Вторым критерием остановки было максимальное количество итераций - 80. Цель вычислительного эксперимента состояла в нахождении наилучшей оценки снизу глобального минимального значения максимум за 80 итераций. п т /к и /у» л, к £лвб £ЯЕЬ

5 10 -72.21713 -72.21716 4 3 ■ ю-5 4 ■ Ю-6

10 12 -948.5131 -948.5132 4 1 - ю-4 1 • ю-6

15 15 -3085.668 -3086.068 80 0.4 0.00001

20 25 -7542.3142 -7542.3149 25 7 • Ю-4 9 • Ю-7

25 20 -1.43259 • 104 -1.45793 • 104 80 253.43 0.018

30 22 -2.47 ■ 104 -2.513 • 104 80 430.78 0.017

35 23 -3.892 • 104 -3.953 • 104 80 608.48 0.016

40 25 -5.699 • 104 -5.869 • 104 80 1700.35 0.03

45 27 -8.343 • 104 -8.389 • 104 80 462.96 0.0055

50 29 -1.18-105 -1.198 • 105 80 1781.1 0.015

55 31 -1.535 • 105 -1.561 ■ 105 80 2667.7 0.017

60 33 -2.066 -105 -2.076 • 105 80 915.9 0.004

65 35 -2.627-105 -2.642 • 105 80 1471.1 0.005

70 37 -3.124 • 105 -3.158 • 105 80 3367.2 0.01

Заключение

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

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

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

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

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

1. Александров А.Д. О поверхностях, представимых разностью выпуклых функций // Изв. АН КазССР. Сер. матем. и механика. 1949. - Вып.З. - С.3-20.

2. Александров А.Д. Поверхности, представимые разностями выпуклых функций // Доклады АН СССР. 1950. - Т.72, №4. - С.613-616.

3. Александров И.А., Анциферов Е.Г., Булатов В.П. К методам цетрированных сечений //В кн.: Тезисы докладов конференции по математическому программированию, Свердловск, 1981. С.72-73.

4. Александров И.А., Анциферов Е.Г., Булатов В.П. Методы центрированных сечений в выпуклом программировании // Препринт СЭИ СО РАН, Иркутск, 1983. 33 с.

5. Антипин A.C. Равновесное программирование: методы градиентного типа II Автоматика и телемеханика. 1997. - №8. - С. 125-137.

6. Антипин A.C. Равновесное программирование: проксимальные методы II Журн. вычисл. матем. и матем. физ. 1997. - Т.37, №11. - С. 13271339.

7. Антипин A.C. Градиентный метод с выбором длины шага для вычисления неподвижных точек равновесных задач // Методы и алгоритмы исследования задач оптимального управления. Тверь, 2000. - С.29-47.

8. Антипин A.C. Градиентный и экстраградиентный подходы в билинейном равновесном программировании (приложения к играм с ненулевой суммой). М.: ВЦ РАН, 2002. - 131 с.

9. Антипин A.C. К построению общей теории равновесных и игровых задач // Методы оптимизации и их приложения. Труды XIII Байкальской международной школы-семинара. Том.1. Математическое программирование. Иркутск, ИСЭМ СО РАН, 2005. - С.3-35.

10. Антипин A.C. Равновесное программирование: модели и методы решения // Изв. Иркутского государственного университета. Сер. математика. 2009. - Т.2, №1. - С.8-36.

11. Анциферов Е.Г., Ащепков Л.Т., Булатов В.П. Методы оптимизации и их приложения // 4.1. Математическое программирование. -Новосибирск: Наука, 1990.

12. Анциферов Е.Г., Даниленко Ю.Я. Об одной модификации метода опорного конуса для решения общей задачи выпуклого программирования // Прикладная математика. Вып.8. Иркутск, СЭИ СО АН СССР, 1978. - С.18-22.

13. Анциферов Е.Г., Булатов В.П. Алгоритм симплексных погружений в выпуклом программировании // Журн. вычисл. матем. и матем. физ. -1987. Т.23, №3. - С.377-384.

14. Апекина Е.В., Хамисов О.В. Модифицированный метод симплексных погруэюений с несколькими секущими плоскостями // Изв. ВУЗов. Сер. матем. 1997. - №12. - С. 16-24.

15. Аржанцев И.В. Системы алгебраических уравнений и базисы Грёбнера.- М.: Макс Пресс, 2002.- 88 с.

16. Базара М., Шетти К. Нелинейное программирование. Теория и методы.- М.: Мир, 1982. 584 с.

17. Булатов В.П. Методы погружения в задачах оптимизации. -Новосибирск: Наука, 1977.

18. Булатов В.П., Касинская Л.И. Об одной интерпретации метода X. Туя решения задачи вогнутого программирования //В кн.: Прикладная математика. Иркутск: СЭИ, 1978. С.206-208.

19. Булатов В.П., Касинская Л.И. Некоторые методы минимизации вогнутой функции на выпуклом многограннике и их приложение //В кн.: Методы оптимизации и их приложения. Новосибирск, наука, 1982.- С.71-80.

20. Булатов В.П., Хамисов О.В. Методы отсечения в Еп+1 для решения задач глобальной оптимизации на одном классе функций // Журн. вычисл. матем. и матем. физ. 2007. - Т.47, №11. - С.1830-1842.

21. Бухбергер Б. Базисы Грёбнера. Алгоритмический метод в теории полиномиальных идеалов //В кн.: Компьютерная алгебра. Символьные и алгебраические вычисления / Под ред. Б. Бухбергера, Дж. Коллинза, Р. Лооса. М.: Мир, 1986. - С.331-372.

22. Васильев Н.С. К отысканию глобального минимума квазивыпуклой функции // Журн. вычисл. матем. и матем. физ. 1983. - Т.23, №2. - С.307-313.

23. Васильев Н.С. О вычислении равновесий по Нэшу в квадратичных играх // Вопросы кибернетики. Вычислительные вопросы анализа больших систем / Под ред. В.Г. Карманова. М., 1989. - С.64-69.

24. Васильев Ф.П. Методы оптимизации. М.: Издательство "Факториал Пресс", 2002. - 824 с.

25. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. - 319 с.

26. Гамм А.З. Статистические методы оценивания ■ состояния электроэнергетических систем. М.: Наука, 1976. - 220 с.

27. Гамм А.З., Таирова Е.В., Хамисов О.В. Нахождение равновесных точек в рыночных моделях ЭЭС // Изв. РАН. Энергетика. 2000. - №6. -С. 57-73.

28. Гасанов И.И., Рикун Л.Д. О необходимых и достаточных условиях одноэктремальности в невыпуклых задачах математического программирования. ДАН АН СССР, 1984. - Т.278, №4. - С.786-789.

29. Гасанов И.И., Рикун Л.Д. О необходимых и достаточных условиях одноэкстремальности в невыпуклых задачах математического программирования // Журн. вычисл. матем. и матем. физ. 1985. -Т.25, №6. - С.815-827.

30. Гергель В.П. Алгоритм глобального поиска с использованием производных // Динамика систем:' Межвуз. тематич. сб. науч. тр. / Под ред. Ю.И. Неймарка. Горький: ГГУ, 1992. - С.161-178.

31. Гергель В.П. Об одном способе учета значений производных при минимизации многоэкстремальных функций // Журн. вычисл. матем. и матем. физ. 1996. - Т.36, №6. - С.51-67.

32. Голынтейн Е.Г. Теория двойственности в математическом программировании и ее прилоэюения. М.: Наука, 1971. - 351 с.

33. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремалъная оптимизация. Н. Новгород: Изд-во ННГУ, 2007.

34. Демиденко Е.З. Оптимизация и регрессия. М.: Наука, 1989. - 296 с.

35. Демьянов В.Ф., Васильев J1.B. Недифференцируемая оптимизация. -М.: Наука, 1981. 384 с.

36. Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений М.: Мир, 1988. - 440 с.

37. Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Журн. вычисл. матем. и матем. физ. 1971. - Т.11, №6. - С.1390-1403.

38. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

39. Евтушенко Ю.Г., Малкова В.У., Станевичюс A.A. Распараллеливание процесса поиска глобального экстремума / / Автоматика и телемеханика. 2007. - №5. - С.45-58.

40. Евтушенко Ю.Г., Малкова В.У., Станевичюс A.A. Параллельный поиск глобального экстремума функций многих переменных // Жури, вычисл. матем. и матем. физ. 2009. - Т.49, №2. - С.255-269.

41. Евтушенко Ю.Г., Посыпкин М.А. Параллельные методы решения задач глобальной оптимизации // Параллельные вычисления и задачи управления. Труды четвертой международной конференции. Москва, 27-28 октября, 2008. - С. 18-39.

42. Евтушенко Ю.Г., Потапов М.А. Методы решения многокритериальных задач // Доклады АН СССР. 1986. - Т.291, №1. - С.25-39.

43. Евтушенко Ю.Г., Ратькин В.А. Метод половинных делений для глобальной оптимизации функций многих переменных // Изв. АН СССР. Техническая кибернетика. 1987. - Т.1'. - С. 119-127.

44. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998. - 248 с.

45. Еремин И.И. Двойственность в линейной оптимизации. -Екатеринбург: УрО РАН, 2001. 200 с.

46. Еремин И.И., Астафьев H.H. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. - 192 с.

47. Ершова М.С. Введение в двухуровневое программирование: учебное пособие. Икутск, Иркутский государственный университет, 2006. - 76 с.

48. Ершов А.Р., Хамисов О.В. Автоматическая глобальная оптимизация // Дискретный анализ и исследование операций. Серия 2. 2004. - Т. 11, т. - С.45-68.

49. Жиглявский A.A., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991. - 247 с.

50. Залгаллер В.А. О представлении функций нескольких переменных разностью выпуклых функций // Зап. научн. сем. ПОМИ. 1997. -Т.246. - С.36-65.

51. Зоркальцев В.И., Хамисов О.В. Равновесные модели в экономике и энергетике. Новосибирск: Наука, 2006. - 221 с.

52. Иванов Д.В., Караулова И.В., Маркова Е.В., Труфанов В.В., Хамисов' О.В. Численное решение задач управления развитием электроэнергетических систем // Автоматика и Телемеханика, 2004. т. - С.125-136.

53. Иванов Д.В., Мокрый И.В., Хамисов О.В. К глобальной оптимизации явно заданных функций // В кн.: Методы исследования и моделирования технических, социальных и природных систем. Новосибирск, Наука, 2003. С.256-269.

54. Иванов Д.В., Хамисов О.В. Численное тестирование методов нулевого порядка в задачах невыпуклого программирования // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", т.1, 2005. С. 221-230.

55. Измайлов А.Ф., Солодов M.B. Численные методы оптимизации. М.: ФИЗМАТЛИТ, 2003. - 304 с.

56. Калиткин H.H. Численные методы. М.: Наука, 1978. - 512 с.

57. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. - 280 с.

58. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. -М.: Мир, 2000. 688 с.

59. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1976. - 544 с.

60. Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании. // Сиб. журн. исслед. операций. 1994. - Т1, №2. -С. 18-39

61. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. -М: Наука, 1969.

62. Кутателадзе С.С., Рубинов A.M. Двойственность Минковского и ее приложения. Новосибирск: Наука, 1976. - 255 с.

63. Кутищев Г.П. Решение алгебраических уравнений произвольной степени. М.: Издательство ЛКИ, 2010. - 232 с.

64. Ландис Е.М. О функциях, представимых в виде разности двух выпуклых // Доклады АН СССР. 1951. - Т.80, №1. - С.9-11.

65. Ларичев О.И., Горвиц Г.Г. Методы поиска локального экстремума овражных функций. М.: Наука, 1990 - 95 с.

66. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985. - 336 с.

67. Левитин Е.С. Оптимизационные задачи с экстремальными ограничениями. I Общие понятия, постановка и основные проблемы // Автоматика и телемеханика. 1995. - №7. - С.3-15.

68. Левитин Е.С. Оптимизационные задачи с экстремальными ограничениями. II Приложения к математическим проблемам системного анализа // Автоматика и телемеханика. 1995. - №12. -С.16-31.

69. Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений // Журн. вычисл. матем. и матем. физ. 1966. - Т.6, №5. - С.787-823.

70. Левитин Е.С., Хранович И.Л. Поиск глобального минимума в задачах невыпуклого программирования с зависимостями бисепарабельными суперпозициями выпуклых функций. - ДАН СССР, 1996. - ТЗ, №2. -С.166-169.

71. Михалевич B.C., Гупал A.M., Норкин В.И. Методы невыпуклой оптимизации. М.: Наука, 1987. - 280 с.

72. Моцкус Й.Б. Многоэкстремальные задачи в проектировании. М.: Наука, 1976. - 215 с.

73. Нечаева М.С., Хамисов О.В. Метод ветвей и границ для мининмизации невыпуклой квадратичной функции при выпуклых квадратичных ограничениях // Дискретный анализ и исследование операций. Серия 2. 2000. - Т.7, №2. - С.74-88.

74. Норкин В.И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журн. вычисл. матем. и матем. физ. -1992. Т.32, №7. - С.992-1006.

75. Нурминский Е.А. Квазиградиентный метод решения задачи нелинейного программирования // Кибернетика. 1973. - №1. -С.122-125.

76. Нурминский Е.А. Численные методы выпуклой оптимизации. М.: Наука, 1991. - 169 с.

77. Островский Г.М., Волин Ю.М. Технические системы в условиях неопределенности. М.: БИНОМ, 2008. - 319 с.

78. Пиявский С.А. Алгоритм глобальноко поиска минимума функции // Теория оптимальных решений. Т.2. Институт Кибернетики, Киев, 1967. - С. 13-24.

79. Пиявский С.А. Один алгоритм отыскания экстремума функции // Журн. вычисл. матем. и матем. физ. 1972. - Т.12, №4. - С.888-896.

80. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

81. Поляк Б.Т. Локальное программирование // Журн. вычисл. матем. и матем. физ. 2001. - Т.41, №9. - С.1324-1331.

82. Попов Л.Д. Введение в теорию, методы и экономические прилоэюения задач о дополнительности // Учебное пособие. Екатеринбург: Изд-во Урал, ун-та, 2001. 124 с.

83. Прасолов В.В. Многочлены. М.: МЦНМО, 2001. - 336 с.

84. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука, 1975. - 320 с.

85. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. - 469 с.

86. Рубинов А.М. Монотонный анализ // В кн: Исследования по функциональному анализу и его приложениям. М.: Наука, 2006. С.167-214.

87. Семеней П.Т. Решение задач выпуклого программирования методом опорного конуса // Методы оптимизации и исследование операций. Иркутск, СЭИ СО АН СССР, 1984. С.104-113.

88. Семеней П.Т. Алгоритмы метода опорного конуса и их использование при решении прикладных задач энергетики. Диссертация на соискание ученой степени кандидата физико-математических наук, Иркутск, СЭИ СО АН СССР, 1990. - 88 с.

89. Семеней П.Т., Хамисов О.В. Об одной модификации метода опорного конуса // Методы математического программирования и программное обеспечение (тезисы докладов). Свердловск, УНЦ АН СССР, 1987. -С.101-102.

90. Сеннова Е.В., Сидлер В.Г. Математическое моделирование и оптимизация развивающихся теплоснабжающих сист,ем. -Новосибирск: Наука, 1987. 222 с.

91. Сергеев Я.Д., Квасов Д.Е. Диагональные алгоритмы глобальной оптимизации. М.: ФИЗМАТЛИТ, 2008. - 352 с.

92. Стенников В.А., Хамисов О.В., Пеньковский А.В. Методы управления теплоснабжением потребителей в условиях рынка // Изв. РАН. Энергетика. 2009. №3. - С.27-36.

93. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. (Информационно-статистические алгоритмы). М.: Наука, 1978.

94. Стронгин Р.Г. Поиск глобального экстремума. М.: Знание, 1990.

95. Стрекаловский A.C. Элементы невыпуклой оптимизации. -Новосибирск: Наука, 2003. 336 с.

96. Стрекаловский A.C., Орлов A.B. Биматричные игры и билинейное программирование. М.: ФИЗМАТЛИТ, 2007. - 224 с.

97. Сухарев А.Г. Минимаксные алгоритмы в задачах численного анализа.- М.: Наука, 1989. 303 с.N

98. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации.- М.: Наука, 1986. 327 с.

99. Таирова Е.В., Хамисов О.В. К решению одной невыпуклой векторной задачи оптимизации // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения", том.1. Иркутск, 1998. - С.238-241.

100. Таирова Е.В., Хамисов О.В. О коалиционном поведении в рыночных моделях электроэнергетических систем // Известия РАН. Энергетика. 2002. Ш. - С.40-47.

101. Туй X. Вогнутое программирование при линейных ограничениях // Доклады АН СССР. 1964. - Т. 159, №9. - С.32-35.

102. Федоров В.В. Численные методы максимина. М.: Наука, 1979. - 280 с.

103. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной оптимизации. М.: Мир, 1972.

104. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления II. М.: Наука, 1970, 800 с.

105. Хамисов О.В. Мет,од ветвей и границ для минимизации вогнутой функции на многограннике // Материалы XXXI конференции молодых учёных. Иркутск, СЭИ, 1991. - С.25-33.

106. Хамисов О.В. Метод отсечений в Еп+1 с ветвлением для решения задачи вогнутого программирования // Тезисы докладов научной конференции. Свердловск, 1991. - С.136-137.

107. Хамисов О.В. Функции с вогнутой минорантой: определение, оптимизационные свойства и сравнение с другими классами функций // Оптимизация, Управление, Интеллект. Иркутск, ИДСТУ. 1995. -№1. - С.61-76.

108. Хамисов О.В. К минимизации бивыпуклой функции // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения", том.1. Иркутск, 1998. - С.208-211.

109. Хамисов О.В. Нахождение вещественных корней полинома на отрезке методом опорных вогнутых функций // Оптимизация, Управление, Интеллект. Иркутск, ИДСТУ. 1999. - №3. - С.167-177.

110. Хамисов О.В. Нахождение корней нелинейных уравнений методом вогнутых опорных функций // Труды XII Байкальской международной школы-семинара "Методы оптимизации и их приложения", том.4. -Иркутск, 2001. С.194-198.

111. Хамисов О.В. Оптимизация и равновесное программирование //В кн.: Методы исследования и моделирования технических, социальных pi природных систем. Новосибирск: Наука, 2003. С.278-292.

112. Хамисов О.В. Некоторые алгебраические и комбинаторные аспекты задачи невыпуклого квадратичного программирования // В кн.: Современные методы оптимизации и их приложения к моделям энергетики. Новосибирск: Наука, 2003. С.229-247.

113. Хамисов О.В. Алгебраическое решение задач невыпуклого квадратичного программирования // Автоматика и Телемеханика.- 2004. №2. - С.63-74.

114. Хамисов О.В. Глобальная оптимизация функций с вогнутой опорной минорантой // Журн. вычисл. матем. и матем. физ. 2004. - Т.47, №11.- С.1830-1842.

115. Хамисов O.B. О построении новых отсечений в целочисленном программировании // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", т.1. Иркутск, 2005.- С.607-612.

116. Хамисов О.В. Численное решение специальных задач невыпуклого квадратичного программирования // Дискретный анализ и исследование операций, Серия 1. 2005. - Т. 12, №4. - С.81-91.

117. Хамисов О.В. Методы ветвей и границ с отсечениями в задачах глобальной и дискретной оптимизации // Материалы российской конференции "Дискретная оптимизация и исследование операций". -Новосибирск: Изд-во Института математики, 2007. С.83-86.

118. Хамисов О.В. Равновесное программирование и методы глобальной оптимизации // Материалы российской конференции "Проблемы оптимизации и экономические приложения". Омск: Изд-во Института математики, 2009. - С.83-86.

119. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. - 534 с.

120. Хансен П., Джамард В., Jly Ш.-Х. Глобальная оптимизация одномерных липшицевых функций // Оптимизация, модели, методы, решения. Новосибирск: Наука, 1992. С.287-317.

121. Хлямков A.B. Замечание о. сходимости метода парабол // Математические заметки. 1998. - Т.63, №2. - С.309.

122. Чичинадзе В.К. Решение невыпуклых нелинейных задач оптимизации.- М.: Наука, 1983. 256 с.

123. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Наука, 1995. - 192 с.

124. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. - 200 с.

125. Шор Н.З. Об одном подходе к получению глобальных экстремумов ■ в полиномиальных задачах математического программирования //

126. Кибернетика. 1987. - №5. - С. 102-106.

127. Шор Н.З., Гершович В.И. Об одном семействе алгоритмов для решения задач выпуклого программирования // Кибернетика. 1979.- ЖА. С.62-67.

128. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. Киев: Наукова думка, 1989. - 204 с.

129. Юдин Д.Б. Вычислительные методы теории принятия решений. М.: Наука, 1989. - 320 с.

130. Adjiman C.S., Androulakis I.P., Floudas С.A. A global optimization method, aBB, for general twice-differentiable constrained NLPs I. Theoratical advances // Computers Chem. Engng. - 1988. - Vol.22, №9. - P. 1137-1158

131. Adjiman C.S., Androulakis I.P., Floudas C.A. A global optimization method, aBB, for general twice-differentiable constrained NLPs II. Implementation and computational results // Computers Chem. Engng. -1988. - Vol.22, №. - P. 1159-1179

132. Al-Khayyal F., Falk J. Jointly Constrained Biconvex Programming // Mathematics of Operations Research. 1983. - №8. - P.273-286.

133. Andramonov M.Y., Rubinov A.M., Glover B.M. Gutting Angle Methods in Global Optimization // Appl. Math. Lett. 1999. - Vol.12, №3. - P.95-100.

134. Antipin A.S. Extra-proximal Methods for Solving Two-person Nonzero-Sum Games // Mathematical Programming. Series B. 2009. - Vol.120, №1 -P.147-177.

135. Aubin J., Ekeland I. Estimates of the Duality Gap in Nonconvex Optimization // Math. Operat. Res., 1976. Vol.1, №3. - P.225-244.

136. Avriel M., Diewert W.E., Schaible S., Zang I. Generalized Concavity // Plenum Press, New York, 1988. 332 p.

137. Balas E. Integer section Cuts A New Type of Cutting Planes for Integer Programming // Math. Operat. Res., 1971. - Vol.19, №1. - p. 19.-39.

138. Balas E., Bowman J.V., Glover F., Sommer D. An Intersection Cut from the Dual of the Unit Hypercube // Math. Operat. Res., 1971. Vol.19, №1.- P.40-44.

139. Bard J. Practical Bilevel Optimization. Dordrecht: Kluwer Academic Publishers, 1998. - 488 p.

140. Baritompa W. Customizing Methods for Global Optimization A Geometric Viewpoint // Journal of Global Optimization. - 1993. - Vol.3, №2. - P. 193212.

141. Baritompa W., Cutler A. Accelerations for Global Optimization Covering Methods Using Second Derivatives // Journal of Global Optimization. -1994. Vol.4, №. - P.329-341.

142. Ben-Tal A., Teboulle M. Hidden Convexity in Some Nonconvex Quadrati-cally Constrained Quadratic Programming // Mathematical Programming.- 1996. Vol.72. - P.51-63.

143. Ben-Tal A., Nemirovski A. Lectures on Modern Convex Optimization // MPS. SIAM Series on Optimization. 2001. - 488 p.

144. Benson H.P. Concave Minimization: Theory, Applications and Algorithms // In: Handbook of Global Optimization, Horst R. and Pardalos P.M. (eds.).- Dordrecht: Kluwer Academic Publishers, 1995. P.43-148.

145. Benson H.P. On the Construction of Convex and Concave Envelope Formulas for Bilinear and Fractional Functions on Quadrilaterals // Computational Optimization and Applications. 2004. - Vol.27. - P.5-22.

146. Bomze I.M., Locatelli M. Undominated d.c. Decomposition of Quadratic Functions and Applications to Branch-and Bound Approaches // Computational Optimization and Applications. 2004. - №28. - P.227-245.

147. Bonnans J.F., Gilbert J.C., Lemarechal C., Sagastizabal C.A. Numerical Optimization. Theoretical and Practical Aspects // Berlin Heidelberg: Springer-Verlag, 2003. 422 p.

148. Brook A., Kendrick D., Meeraus A. GAMS Release 2.25. A user's guide // GAMS Development corporation, 1996.

149. Bulatov V.P. Methods of Simplicial Cuts in Mathematical Programming and Its Applications // Manuscripte fur Operations Research der Universitat Zurich, 1993. 29 p.

150. Bulatov V.P., Khamisov O.V. The Cutting Method in En+1 Through Concave Extension for Solving Global Extremum Problem // 21 JAHRESTAGUNG "Mathematische Optimerung", Berlin, 1989. P. 16-19.

151. Bulatov V.P., Khamisov O.V. The Branch and Bound Method With Cuts in EnH for Solving Concave Programming Problem // Lecture Notes in Control and Information Sciences 180, Springer-Verlag, 1991. P.273-282.

152. Bulatov V.P., Khamisov O.V. On the Reduction of Some Multiextremal Problems to the Convex-Concave Programming Problem // Proceedings of the International Conference "On engineering mathematics and applications", Shenzhen, China, 1992. P. 103-107.

153. Cambini R., Sodini C. A Computational Comparison of Some Branch and Bound Methods for Indefinite Quadratic Programs // CEJOR. 2008. -Vol.16. - P.139-152.

154. Chang M.N., Park Y.C., Lee T.-Y. A New Global Optimization Method for Univariate Constrained Twice-Differentiable NLP Problem // Journal of Global Optimization. 2007. - Vol.39. - P.79-100.

155. Chunchuluun A., Rentsen E., Pardalos P.M. A Numerical Method for Concave Programming Problem. Continuous Optimization. Current Trends and Modern Applications / Ed. by Jeyakumar V., Rubinov A. - Springer Science + Business Media, 2005. - P.251-273.

156. Continuous Optimization. Current trends and Modern Applications // Jeyakumar V., Rubinov A. (eds.) Springer Science+Business Media, Inc., 2005.

157. Craven B. Invex Functions and Constrained Local Optima // Bull. Austral. Math. Soc. 1981. - Vol.24. - P.357-366.

158. Dantzig G.B. Note on Solving Linear Programs in Integers // Naval. Res. Log. Quart. 1959. - Vol.6, Ш. - P.75-76.

159. Dempe S. Foundations of Bileval Programming. Dordrecht: Kluwer Academic Publishers, 2002. - 320 p.

160. Du D.Z., Pardalos P.M. Continuons Version of a Result of Du and Hwang // Journal of Global Optimization. 1994. - Vol.5. - P. 127-130.

161. Ekeland I., Temam R. Convex Analysis and Variational Problems // Elsevier, New York, 1976.

162. Encyclopedia of Optimization (6 volumes). Second Edition. / C.A. Floudas, P.M. Pardalos (eds).- Springer Science+Business Media, 2009.

163. Essays and Surveys in Global Optimization / Audet C., Hansen P., Savard G. (eds.) Springer Science+Business Media, 2005.

164. Evtushenko Yu.G. Fast Automatic Differentiation // Dinamics of Non-homogeneous Systems. Proceedings of ISA RAS, 1997. P. 193-210.

165. Floudas C.A., Pardalos P.M. A Collection of Test Problems for Constrained Global Optimization Algorithms. Berlin: Springer-Verlag, 1990. - 181 p.

166. Floudas C.A., Visweswaran V. Quadratic Optimization // Handbook of global optimizaation. Dordrecht: Kluwer Academic Publishers, 1995. -P.217-263.

167. Fiilop J. Lagrangean Duality of Concave Minimization Subject to Linear and an Additional Facial Reverse Convex Constraint // J.O.T.A. 1996. -Vol.91, №3. - P.617-641.

168. Galperin E., Zheng Q. Nonlinear Observation Via Global Optimization Methods: Measure Theory Approach // J.O.T.A. 1987. - Vol.54, №1. -P. 63-92.

169. GAMS. The solver manuals. OSL. GAMS Development corporation, 1996.

170. Ge R.A. A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables // Math. Program. 1990. - Vol.46, №2 -P. 191-204.

171. Gergel V.P. A Global Optimization Algorithm for Multivariate Function with Lipschitzian First Derivatives // Journal of Global Optimization. -1997. Vol.10, №3. - P.257-281.

172. Global optimization. From theory to implementation. L. Liberti, N. Maculan (eds). - Springer Science+Business Media, 2006. - 420 p.

173. Glover F. Convexity Cuts and Cut Search // Operatins Research. 1973. -Vol.21, №1. - P.123-134.

174. Gomory R.E. An Algorithm for Integer Solution to Linear Programs / Princeton IBM Mathematics Research Project, Technocal Report №1, 1958. - November 17.

175. Hansen P., Jaumard B. Lipschitz Optimization // In: Handbook of global optimization. Dordrecht: Kluwer Academic Publishers, 1995. P.407-494.

176. Hanson M. On Sufficiency of the Kuhn-Tucker Conditions // J.O.T.A. -1981. Vol.50. - P.545-550.

177. Hirriart-Urruty J.-B. Generalized Differentiability, Duality and Optimization for Problems Dealing with Difference of Convex Functions // Lecture Notes in Economics and Mathematical Systems. 1985. Vol.256. - P.37-70.

178. Hirriart-Urruty J.-B. Necessary and Sufficient Conditions for Global Opti-mality // Nonsmooth optimization anf related topics, 1989. P. 219-239.

179. Hirriart-Urruty J.-B., Lemareschal C. Convex Analysis and Minimization Algorithms. Berlin, Springer-Verlag, 1993.

180. Horst R. A Note on Functions Whose Local Minima Are Global (Thechnical Note) // J.O.T.A 1982. - Vol.36, №3. - P.457-463.

181. Horst R., Nast M. Linearly Constrained Global Minimization of Functions with Concave Minorants // J.O.T.A. 1996. - Vol.88, №3. - P.751-763.

182. Horst R., Pardalos P.M., Thoai N.V. Introduction to Global Optimization. Dordrecht: Kluwer Academic Publishers, 1995.

183. Horst R., Tuy H. Global Optimization. (Deterministic Approaches), 3rd, revised and enlarged edition. Berlin: Springer-Verlag, 1996.

184. Jarre F. Interior-point Method for Class of Convex Programs / In: Interior piont methods of mathematical programming, T. Terlaky (ed). Dordrecht: Kluwer Academic Publishers, 1996. - P.255-296.

185. Jaumard B., Meyer C. On the Convergence of Cone Splitting Algorithms with u-subdivisions // J.O.T.A. 2001. - Vol.110, №1. - P.119-144.

186. Journal of Global Optimization. Special Issue Didicated to the memory of Professor P.D. Panagiotopoulos / G.E. Stavroulakis, V.F. Demyanov, P.M. Pardalos (eds). 2000. Vol.17, №1-4. - 411 P.

187. Journal of Global Optimization. Special Issue: Applications to Economucs / J.E. Martinez-Legazyanov (ed). 2001. Vol.20, №3-4. - 393 P.

188. Journal of Global Optimization. Special Issue: Nonconvex Optimization in Control / K.L. Teo, D. Li, W.-Y. Yan (eds). 2002. Vol.23, №3-4. - 425 P.

189. Khamisov O.V. Functions With Concave Minorant. A General View // Manuscripte, Institut fur Opeartions Research der Universität Zurich, 1994. -25 p.

190. Khamisov O.V. On Application of Convex and Concave Support Functions in Nonconvex Problems // Manuscripte, Institut fur Opeartions Research der Universität Zurich, 1998. 16 p.

191. Khamisov O.V. On Optimization Propeiiies of Functions with a Concave Minorant // Journal of Global Optimization. 1999. - №14. - P.79-101.

192. Khamisov O.V. A Global Optimization Approach to Solving Equilibrium Programming Problems // Series on Computers and Operations Research. 2003. - Vol.1, Optimization and Optimal Control. - P. 155-164.

193. Locatelli M., Raber U. On Convergence of the Simplicial Branch-and-Branch Algorithm based on u-subdivisions // J.O.T.A. 2000. - Vol.107, №1. - P.69-79.

194. Locatelli M., Thoai N.V. Finite Exact Branch-and-Bound Algorithms for Concave Minimization over Polytopes // Journal of Global Optimization. -2000. Vol.18. - P. 107-128.

195. Locatelli M., Schoen F. Structure prediction and global optimization // OPTIMA. 2008. - №76. -P. 1-8.

196. Mangasarian O.L. Computable Numerical Bounds for Lagrange Multipliers of Stationary Points of Non-convex Differantiable Non-linear Programs // Operations Research Letters. 1985. - Vol.4, №2. - P.47-48.

197. Martin D. Connected Level Sets, Minimizing Sets, and Uniqueness in Optimization // J.O.T.A. 1982. - Vol.36, №1. - P.71-91.

198. Martin D. The Essence of Invaexity // J.O.T.A. 1985. - Vol.47, №1. -P.65-76.

199. McCormick G.P. Attempts to Calculate Global Solutions of Problems that May Have Local Minima // In: Numerical Methods of Nonlinear Optimization, F. Lootsma (ed.), Academic Press, London and New York, 1972. -P. 209-221.

200. Mine H., Fukushima M. A Minimization Method for the Sum of a Convex and a Continuously Differentiate Function // J.O.T.A. 1981. - Vol.33, №1. - P.9-23.

201. Mishra S.K. , Giorgi G. Invexity and Optimization. Springer-Verlag, Berlin, 2008. - 266 p.

202. Models and algorithms for global optimization. Essays dedicated to Antanas1. V k ** / \

203. Zilinskas on occasion of his 60th birthday. A. Torn, J. Zilinskas (eds). -Springer Science+Business Media, 2007.

204. Nesterov Y., Polyak B.T. Cubic Regularition of Newton Methods and its Global Performance // Math. Program. Series A. 2006. - Vol.108 - P. 177205.

205. Nikaido H., Isoda K. A Note on Noncoopearative Convex Games // Pacific Journal of Mathematics. 1955. - Vol.5, suppl. I. - P.807-815.

206. Oliveira J.B. Evaluating Lipschitz Constants for Functions Given by Algorithms // Computational Optimization and Applications. 2000. - Vol.16.- P.215-229.

207. Palaschke D., Rolewicz S. Foundations of Mathematical Optimization. Convexity without Linearity // Dordrecht: Kluwer Academic Publishers, 1997.

208. Polyak B.T. Convexity of Nonlinear Image of a Small Ball with Applications to Optimization // Set-Valued Analysis. 2001. - №9 - P. 159-168.

209. Pappolardo M. On the Duality Gap in Nonconvex Optimization // Math. Operat. Res., 1986. Vol.11, №1. - P.30-35.

210. Pardalos P.M., Rosen J.B. Constrained Global Optimization: Algorithms and Applications Berlin, Springer-Verlag, 1987.

211. Pardalos P.M., Schnitger G. Checking Local Optimality in Constrained Quadratic Programming is NP-hard // Operations Research Letters. 1987.- №7. P.33-35

212. Porembski M. How to Extend the Concept of Convexity Cuts to Derive Deeper Cutting Planes // Journal of Global Optimization. 1999. - Vol.15.- P.371-404.

213. Porembski M. Finitely Convergent Cutting Planes for Concave Minimization I/ Journal of Global Optimization. 2001. - Vol.20. - P.113-136.

214. Rockafellar R.T. The Theory of Subgradients and its Applications to Problems of Optimization. Convex and Nonconvex Functions // Heldermann Verlag, Berlin. 1981. - 107 p.

215. Rockafellar R.T., Wets R. J.-B. Variational Analysis. Springer-Verlag Berlin 1988, Corrected 3rd printing 2009. - 734 p.

216. Rosen J.B. Iterative Solution of Nonlinear Optimal Control Problems // SIAM J. Control Optim. 1966. - Vol.6. - P.223-244.

217. Rubinov Abstract Convexity and Global Optimization. Dordrecht: Kluwer Academic Publishers, 2000.

218. Sergeev Ya.D. An One-Dimensional Deterministic Global Optimization Algorithm /1 Comput. Maths. Math. Phys. 1995. - Vol.35. - P.705-717.

219. Singer I. Abstract Convex Analysis // New York, Wiley and Sons, 1997.

220. Singer I. Duality for nonconvex approximation and optimization. Springer Science+Business Media, 2006. - 355 p.

221. Stetter H.J. Numerical Polynomial Algebra // SIAM, Philadelphia, 2004. -472 p.

222. Strongin R.G., Sergeev Y.D Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms. Dordrecht: Kluwer Academic Publishers, 2000.

223. Tawarmalani M., Sahinidis N.V. A Polyhedral Branch-and-Cut Approach to Global Optimization // Math. Program. Series B. 2005. - Vol.103 -P. 225-249.

224. Thoai N.V. On the Construction of Test Problems for Concave Minimization Algorithms // Journal of Global Optimization. 1994. - Vol.5, №4. -P.399-402.

225. Thoai N.V. Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization // J.O.T.A. 2002. -Vol.113, №1. - P. 165-193.

226. Tuy H. Global Minimization of a Difference of Two Convex Functions // Mathematical Programming Study. 1987. - Vol.30. - P. 150-182.

227. Tuy H. Convex Programming with an Additional Reverse Convex Constraint 11 J.O.T.A. 1987. - Vol.52. - P.463-485.

228. Tuy H. D.C. Optimization: Theory, Methods and Algorithms // Handbook of Global Opimization. Kluwer Academic Publishers, 1995. - P. 149-216.

229. Tuy H. Convex Analysis and Global Optimization. Dordrecht: Kluwer Academic Publishers, 1998. - 339 p.

230. Tuy H. Concave Programming and DH-point // Preprint, Institute of Mathematics, Hanoi, 2005. 6 p.

231. Tuy H. On Duality Bound Methods for Nonconvex Global Optimization // Preprint, Institute of-Mathematics, Hanoi, 2006. 3 p.

232. Vavasis S. Nonlinear Optimization. Complexity Issues. Oxford, Oxford university press, 1991.

233. Vial J.-F. Strong and Weak Convexity of Sets and Functions // Mathematics of Operations Research, 1983. Vol.8, №2. - P.231-259.

234. Wang X., Chang T.-S. An Improved Univariate Global Optimization Algorithm with Improved Linear Lower Bounding Functions // Journal of Global Optimization. 1996. - Vol.8, №4. - P.393-411.

235. Yamnitsky B., Levin L.A. An Old Linear Programming Algorithms Runs in Polynomial Time // 23rd Annual Symp. Found. Comput. Sei. Chicago III, Selver Spring, 1982. P.327-328.

236. Zang I., Avriel M. On Functions Whose Local Minima are Global // J.O.T.A. 1975. - Vol.16, №3/4. - P.183-190.

237. Zang I., Choo E., Avriel M. On Functions Whose Local Minima are Global (Technical Note) // J.O.T.A. 1976. - Vol.18, №4. - P. 155-159.

238. Zang I., Choo E., Avriel M. On Functions Whose Stationary Points are Global Minima // J.O.T.A. 1977. - Vol.22, №2. - P.155-159.

239. Zhang Lian-sheng An Approach to Finding a Global Minimum with Equality and Inequality Constraints // Journal of Mathematics. 1988. - Vol.6, №4. - P.376-382.