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

• Хамисов, Олег Валерьевич
• доктор физико-математических наук
• 2010

Оглавление диссертации доктор физико-математических наук Хамисов, Олег Валерьевич

ВВЕДЕНИЕ

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

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

ГЛАВА 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

Заключение

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

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

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Хамисов, Олег Валерьевич, 2010 год

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.