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

• Морозова, Елена Юрьевна
• кандидат физико-математических наук
• 2007

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

Введение

Основные обозначения и определения.

ГЛАВА 1. Минимизация негладкой функции нескольких переменных

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

1.1.1. Постановка задачи.

1.1.2. Декомпозиция множеств и функций по сечениям.

1.1.3. Описание алгоритма.

1.1.4. Обоснование алгоритма.

1.1.5. Результаты численных экспериментов.

1.1.5.1. Примеры минимизации негладких функций

1.1.5.2. Контрпример для алгоритма Нелдера-Мида.

1.1.5.3. Пример минимизации функции Денниса-Вуда

1.2. Алгоритм безусловной минимизации непрерывной строго унимодальной функции.

1.2.1. Постановка задачи и описание алгоритма.

1.2.2. Примеры работы алгоритма.

1.2.2.1. Контрпример для алгоритма Нелдера-Мида.

1.2.2.2. Пример минимизации негладкой функции.

1.2.2.3. Пример минимизации функции Денниса-Вуда

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

2.1. Общие свойства задач квазивогнутого программирования

2.2. Постановка задачи и основные утверждения.

2.3. Моделирование равномерного распределения на выпуклой оболочке конечного подмножества векторов евклидова пространства.

2.4. Описание основного алгоритма и его обоснование.

2.5. Вычислительные эксперименты. Примеры.

2.5.1. Пример минимизации вогнутой функции.

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

2.5.3. Пример минимизации квазивогнутой функции.

2.5.4. Определение диаметра выпуклого многогранного множества.

ГЛАВА 3. Методы решения задачи транспортного типа с квазивогнутой функцией стоимости

3.1. Свойства транспортного многогранника.

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

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

3.2.2. Постановка задачи и описание алгоритма.

3.2.3. Решение задачи при вырожденном опорном плане.

3.2.4. Тестовая задача нахождения диаметра многогранника бистохастических матриц.

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

ГЛАВА 4. Алгоритм глобальной минимизации квазивогнутой функции на выпуклом множестве

4.1. Общие замечания.

4.2. Постановка задачи и краткое описание структуры алгоритма

4.3. Описание предварительного этапа.

4.4. Описание и обоснование процедуры построения многогранника, содержащего выпуклое множество.

4.5. Пошаговое описание алгоритма.

4.6. Результаты вычислительных экспериментов.

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

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

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

Введение диссертации (часть автореферата) на тему «Глобальная минимизация квазивогнутых функций на выпуклых множествах»

Активные исследования последнего времени привели к появлению разнообразных методов нахождения глобальных решений нелинейных оптимизационных задач с ограничениями. Для некоторых классов нелинейных задач локальное решение является одновременно и глобальным. Например, в задачах минимизации выпуклой (квазивыпуклой) целевой функции при выпуклых ограничениях, локальный минимум является глобальным [7], [42], [107]. Невыпуклые функции могут иметь много локальных минимумов. Например, вогнутая функция на многограннике может иметь локальный минимум в каждой вершине многогранника. Таким образом, методы локальной оптимизации не дают информацию о глобальном минимуме.

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

->min, xeDczR", (1) где /(х) - вещественнозначная вогнутая функция и D - выпуклое компактное множество, R" - n-мерное евклидово пространство.

Разнообразные важные практические приложения в экономике, промышленности и других областях приводят к необходимости отыскания глобального минимума вогнутой функции на замкнутом выпуклом множестве. Так, например, к формулировке задач такого типа приводят задачи с эффектом масштаба (economies of scale) [59], [90], [91] и задачи фиксированных расходов (fixed charge problems) [36], [76]. В связи с задачами минимизации эксплутационных расходов в зависимости от объёма грузовых железнодорожных перевозок при организации вагонопотоков также возникает необходимость в решении задачи вогнутого программирования [113], [137]. Кроме того, несколько важных задач оптимизации могут быть сформулированы как задачи вогнутой минимизации. Известно [86], что задача целочисленного программирования ноль-единица эквивалентна задаче минимизации квадратичной вогнутой функции при линейных ограничениях. Задача о назначениях с квадратичной целевой функцией может быть сформулирована как задача (1) [64], [11]. Фриз [30] привел 3-мерную задачу о назначениях к задаче билинейного программирования и затем к специальной задаче вогнутого программирования. В общем случае, задачи билинейного программирования эквивалентны задачам вогнутой минимизации [61]. Другая важная задача, линейная задача о дополнительности может быть приведена к вогнутой задаче [69], [115], [132], линейные минимаксные задачи со связанными переменными и линейные многошаговые биматричные игры также приводимы к задаче (1) [26], [57]. Поскольку рассмотренные выше примеры охватывают широкий диапазон случаев, задача глобальной вогнутой минимизации (1) представляет, очевидно, значительный интерес.

С точки зрения вычислительной сложности задача (1) остается NP-сложной задачей даже для таких частных случаев как минимизация квадратичной вогнутой функции на гиперкубе (см. например [70], [31], [37]), в отличие от задачи минимизации выпуклой (квадратичной) функции, которая может быть решена алгоритмами в полиномиально ограниченное время [19], [62].

Все известные методы глобальной оптимизации можно разделить на две категории: детерминированные и стохастические. Детерминированные методы получают глобальное решение посредством исчерпывающего поиска на всем допустимом множестве. Большинство стохастических методов оценивают значение функции цели в случайных точках допустимого множества с последующей обработкой выборки. Как следствие, стохастические методы не гарантируют успех. Описание методов стохастической глобальной оптимизации можно найти в [4], [22], [88].

Самые важные детерминированные подходы вогнутого программирования используют методы перечисления, методы отсечения, симплициальные, прямоугольные и конические методы ветвей и границ, решение аппроксимационных подзадач, методы билинейного программирования или различных комбинаций этих методов. Также специальные методы были предложены для задач, где целевая функция имеет специальную структуру (квадратичная, сепарабельная, факторизуемая и т.д.) [2], [3], [59] или допустимое множество имеет специальную структуру (единичный гиперкуб, сетевые ограничения [1], [34], [35], [48], квадратичные ограничения [1] - [3] и т.д.). Обзоры детерминированных методов можно найти в [15], [33], [25], [29], [45], [56], [80], [81], [87], [105], [120], [130].

Важным свойством задачи (1) является тот факт, что глобальный оптимум, если он существует, достигается в какой-либо крайней точке допустимой области [131]. Поэтому в том случае, когда рассматриваемое выпуклое множество ограничений имеет конечное число крайних точек, т.е. является полиэдральным множеством, задачу можно в принципе решить перебором крайних точек. Однако этот подход оказывается неприемлимым для задач большой размерности. Методы полного перебора крайних точек представлены в [24], [68]. Обзоры и сравнение методов перечисления представлены в [23], [71]. Аспекты эффективности вычислений при использовании алгоритмов упорядочивания крайний точек обсуждались в [17].

Стремление эффективно использовать тот факт, что решение задачи (1) достигается в вершине полиэдра, привлекло к созданию методов отсечения. Задача (1) для случая, при котором допустимая область - многогранник, впервые была рассмотрена Туем в [136]. Предложенный метод базировался на использовании отсечений для исключения областей допустимого множества и процедуре разбиения конуса. Вначале в пространстве R" строится множество конусов, объединение которых содержит допустимую область задачи (под конусом подразумевается выпуклый многогранный конус с вершиной в начале координат, имеющий ровно п направляющих). Затем происходит процесс последовательного разбиения имеющихся конусов на более мелкие и решается последовательность подзадач построения оценок для оптимальных значений функционала на пересечении каждого из конусов.

Зварт в [111] показал расходимость конусного алгоритма, описанного Туем. В этой же статье Зварт привел контрпример для метода Риттера [89], в котором для усечения допустимого множества использовалась последовательность отсекающих плоскостей. Зварт привел пример, в котором потребовалась бесконечная последовательность отсекающих плоскостей.

В [8] и [110] были предложены модификации метода Туя. Алгоритм из [110] является конечным и сходится быстро для задач, имеющих небольшое число локальных минимумов или когда глобальный оптимум существенно отличается от других оптимумов. В [58] приведено доказательство алгоритма типа Туя для общей задачи вогнутой минимизации. В [32] Гловер предложил новый класс отсечений (выпуклые отсечения), обобщив класс осекающих плоскостей Туя.

В [114] Булатовым В. П. разработан и обоснован метод нахождения глобального минимума вогнутых функций на многограннике. Основная идея метода состоит в погружении и надграфика целевой функции и допустимой области в некоторые множества более простой природы. На каждом шаге итеративного процесса решается вспомогательная экстремальная задача, допустимое множество которой содержит исходное множество, а надграфик вспомогательной функции - надграфик целевой функции. По сути метод является обобщением метода Туя [136].

В 1969 году Фолк и Соланд в [27] представили первый алгоритм ветвей и границ для решения задачи глобальной минимизации невыпуклой сепарабельной функции на выпуклом ограниченном множестве. В алгоритме целевая функция заменялась на ее выпуклую огибающую и решалась последовательность подзадач, в каждой из которых целевая функция была линейной или выпуклой. Эти задачи соответствовали последовательным разбиениям допустимого множества, и определяли нижнюю и верхнюю границы для решения задачи. Этот алгоритм был расширен позднее Соландом [93] для задач с сепарабельными невыпуклыми ограничениями.

В [43] Хорст рассмотрел более общую задачу невыпуклого программирования. Отличие подхода, предложенного в [43] по сравнению с [27] состоит в использовании разбиений на компакты общего вида вместо прямоугольных разбиений и не требует использования выпуклых огибающих. Хорст показал, что каждая предельная точка последовательности точек, генерируемой алгоритмом, решает задачу. Хорст использовал идеи конического метода ветвей и границ. Различные модификации алгоритмов для решения этого класса можно найти в [41], [46], [47], [51]. Особый класс задач -минимизация при линейных ограничениях суммы вогнутой функции, определенной на пространстве размерности р и линейной функции, определенной на пространстве размерности q, где q намного больше, чем р рассмотрен в [49], [50].

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

МакКормик в [73] показал, что подход "выпуклых огибающих" может быть применен для факторизуемых функций. Детальное описание факторизуемых функций может быть найдено в [74].

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

Несмотря на существование достаточно большого числа разнообразных методов глобальной минимизации вогнутых функций на выпуклых множествах, возможности применения этих методов для решения конкретных задач ограничены предположениями о принадлежности некоторым специальным классам как оптимизируемых функций, так и допустимых множеств [49], [80], [133]. В работе предлагаются новые методы решения задач вогнутого программирования, не накладывающие дополнительных ограничений на дифференцируемость целевой функции и позволяющие применять их для более общего класса функций - негладких и даже разрывных квазивогнутых функций. Один из предлагаемых в данной работе методов глобальной минимизации квазивогнутой функции на произвольном выпуклом множестве базируется на последовательном применении алгоритма нахождения минимума выпуклой функции на симплексе для вычисления оценок снизу и сверху оптимального значения задачи вогнутой минимизации. Описание этого алгоритма представлено в первой главе. Также представлена модификация этого алгоритма для случая минимизации строго унимодальной функции нескольких переменных в отсутствие ограничении. В настоящее время разработано множество численных методов для решения задачи нахождения минимума функции / Традиционные методы на основе анализа производных различного порядка являются достаточно быстрыми и точными, однако, их применение часто оказывается неэффективным или вовсе невозможным в случае решения задач оптимизации для негладких функций. Предложенный в первой главе алгоритм относится к классу методов прямого поиска, основной особенностью которых является то, что они не требуют вычисления производной целевой функции. Направление минимизации полностью определяется последовательными вычислениями значений функции, что позволяет использовать эти методы для негладких функций. Такие ситуации часто встречаются в практически важных задачах оптимизации, что предопределяет широкое применение этих методов при решении важных прикладных оптимизационных задач. Методы прямого поиска наиболее известны как методы безусловной оптимизации, однако, существуют модификации этих методов и для задач с ограничениями [65], [66]. Ниже приведен краткий обзор методов прямого поиска минимума функции в отсутствие ограничений.

В настоящее время одним из наиболее популярных методов прямого поиска минимума функции является метод Нелдера-Мида [79], являющийся развитием метода Спендли, Хекста и Химсворта [94]. Идея метода состоит в сравнении значений функции в {п +1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры, использующей три основных операции: отражения, растяжения и сжатия. Теоретическое исследование этого метода в настоящее время далеко от завершения. Так, в [63] получен ряд результатов о сходимости, в частности, доказано, что оригинальный метод Нелдера-Мида сходится для строго выпуклых функций одной переменной, кроме того, доказано, что в случае двух переменных диаметр симплекса сходится к нулю. Однако, вопрос о сходимости алгоритма к единственной точке даже для строго выпуклых квадратичных функций двух переменных (например, для таких функций, как f(x,y) = x2 + уг) остается открытым. МакКиннон [72] сконструировал семейство функций в R2, для которого алгоритм Нелдера-Мида со специальным выбором начальной конфигурации симплекса сходится к точке, не являющейся точкой минимума, даже в случае, когда семейство параметризовано так, что функции являются строго выпуклыми и имеют непрерывные производные до третьего порядка. При этом происходит эффект внутреннего сжатия, когда симплексы, генерируемые алгоритмом Нелдера Мида стягиваются к прямой линии, ортогональной направлению наискорейшего спуска и не содержащей точки минимума (см. раздел 6.2). Подобного рода примеры представлены также в [96]. Тем не менее, метод Неледра-Мида продолжает активно использоваться на практике (реализация этого метода имеется в пакете Matlab, приложение Optimization Toolbox), что, в свою очередь, способствует появлению его многочисленных модификаций [14], [60], [78], [85], [99], [106].

Более ясной представляется ситуация с теоретическим обоснованием другого класса методов прямого поиска - методов поиска по шаблону, включающих такие классические алгоритмы прямого поиска, как алгоритмы координатного поиска [98], алгоритм эволюционного действия, предложенный Боксом [16], алгоритм поиска по образцу Хука и Дживса [40] и сравнительно недавно предложенные методы мультинаправленного поиска [20], [97]. Методы поиска по шаблону основаны на выборе некоего набора точек, называемых шаблоном, который расширяется или сжимается, в зависимости о того, имеет или нет какая-либо точка данного шаблона меньшее значение целевой функции, чем текущая точка. Поиск заканчивается после того, как будет достигнут минимальный размер рассматриваемого шаблона. Методы прямого поиска считались эвристическими и не имеющими строго математического анализа до появления в 1991 году работы Торзон [97], в которой методы мультинаправленного поиска рассматривались в контексте параллельных вычислений и сопровождались анализом сходимости, основанным на предположении о непрерывной дифференцируемости минимизируемой функции. Исследования последних 15 лет привели к появлению целого ряда публикаций, посвященных теоретическому исследованию класса методов поиска по шаблону [6], [20], [65], [66], [67], [98]. Основным результатом этих исследований является доказательство глобальной сходимости методов к стационарной точке в случае, когда целевая функция является гладкой. Остается открытой проблема эффективности этих методов при решении задач большой размерности. Реализации методов поиска по шаблону содержатся в последних версиях пакета MatLab (приложение Direct Search Toolbox). Известно, что для функций, которые являются негладкими, либо дифференцируемыми всюду, но не имеющими непрерывных производных, алгоритмы поиска по шаблону могут приводить к ошибочным результатам. В [97] проведено исследование причин возникновения таких ошибок, а также проведен анализ локальной сходимости методов, объясняющий причины возможной медленной асимптотической сходимости.

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

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

Задачи диссертационного исследования.

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

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

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

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

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

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

Научная новизна полученных результатов.

Все результаты, включенные в диссертацию, являются новыми.

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

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

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

Практическая ценность работы определяется возможностью использования полученных результатов в ряде прикладных областей экономики, промышленности, транспорта и других, в частности, в задаче минимизации эксплутационных расходов в зависимости от объёма грузовых железнодорожных перевозок при организации вагонопотоков, в задаче с эффектом масштаба (economies of scale), в задаче фиксированных расходов (fixed charge problems) и других задачах, приводящих к минимизации вогнутой функции на выпуклом множестве.

Апробация работы. Результаты диссертации докладывались на научных семинарах кафедры прикладной математики ПГУПС, на Третьем Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2002), на Восьмой международной научно-практической конференции "ИНФОТРАНС - 2003" (СПб, 2003), на Четвертом (весенняя сессия -Петрозаводск, 2003), (осенняя сессия - Сочи, 2003), Шестом (весенняя сессия -СПб, 2005), (осенняя сессия - Сочи, 2005), и Седьмом (Кисловодск, 2006), Всероссийских симпозиумах по прикладной и промышленной математике.

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

1. Морозова ЕЛО. Рекурсивный алгоритм прямого поиска минимума функции нескольких переменных // Обозрение прикладной и промышленной математики. - 2006. - Т. 13. - Вып. 5. - С. 783-796.

2. Баушев А.Н., Морозова ЕЛО. Метод статистических испытаний в задаче квазивогнутого программирования // Обозрение прикл. и промышл. матем. -2004.-Т. 11.-Вып. 1.-С. 34-40.

3. Морозова Е.Ю. Об алгоритме безусловной минимизации негладкой функции нескольких переменных // Обозрение прикладной и промышленной математики. - 2006. - Т. 13. - Вып. 3. - С. 524-525.

4. Баушев А.Н., Морозова Е.Ю. Об алгоритме бисекции для нахождения минимума выпуклой функции на симплексе // Обозрение прикладной и промышленной математики. - 2005. - Т. 12. - Вып. 3. - С. 699-700.

5. Баушев А.Н., Морозова Е.Ю. О задаче минимизации квазивогнутой функции при выпуклых ограничениях. // Обозрение прикл. и промышл. матем. - 2005.-Т. 12.-Вып. 1.-С. 109-110.

6. Баушев А.Н., Морозова Е.Ю. Об алгоритме поиска глобального минимума квазивогнутой функции на транспортном многограннике. // Обозрение прикл. и промышл. матем. - 2005. - Т. 12. - Вып. 1. - С. 110.

7. Морозова Е.Ю. Об алгоритме решения транспортной задачи с квазивогнутой функцией стоимости // Известия ПГУПС. - 2005. - Вып. 1. - С. 194-199.

8. Баушев А.Н., Морозова Е.Ю., Осьминин А.Т. О математической модели минимизации эксплуатационных затрат при организации вагонопотоков // Вестник ПГУПС. - 2004. - Вып. 2. - С. 39-43.

9. Морозова Е.Ю. Об определении диаметра конечного множества точек в евклидовом пространстве // Известия ПГУПС. - 2004. - Вып. 1. - С. 126-130.

Ю.Баушев А.Н., Морозова Е.Ю. О транспортной задаче с квазивогнутой функцией стоимости // Обозрение прикл. и промышл. матем. - 2004. - Т. 11.-Вып. 1.- С. 96.

11.Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков А.С. О задаче математического программирования, возникающей в проблеме минимизации эксплутационных затрат при организации вагонопотоков //

Аннотации докладов восьмой международной научно-практической конференции "ИНФОТРАНС - 2003". - СПб., 2003. - С. 46.

12. Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков А.С. О задаче квазивогнутого программирования и ее применении к проблеме оптимизации железнодорожных перевозок // Обозрение прикладной и промышленной математики. - 2003. - Т. 10. - Вып. 3. - С. 603-604.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 135 страницах машинописного текста, содержит 32 рисунка, 3 таблицы и 137 библиографических ссылок на литературу.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Морозова, Елена Юрьевна

Результаты работы алгоритма по итерациям Таблица 4.1. шага, к пк Г- X Новые верш, множества и / Pk э X Вершины множества M к m Af*

0 F1 (4.1865,1.8271) F2 (4.9202, 0.8899) F5 (3.6779,0.1779) f3.6779' [o.l779, - - - -Inf -1.6653

1 F4 (4.6000,1.9596) f5.0000") (4.1217, 2.5705) (5.488 1, 0.8252)

Г5 (3.0888,0.5893) "Г6 (5.0000,0.0000) [o.oooo, •(4.0288, 3.6378) «(2.4522,-1.4751) «(6.2819, 0.7347) «(2.4714,-1.4492) 3 2 -3.1449 -2.5000

3.5689, 0.0309)

2 ♦F7 (4.3330,0.0447) F8 (3.0404,0.4000) К9 (3.5036,1.3270) ♦F10 (4.9800,0.4466) f5.0000' [o.oooo, ( 2.8697, 0.5 192) (4.1 65 1 , 2.0728) ( 2.7545, 0.4823) «(3.6476, 0.1 370) «(5.0384,-0.0503) ♦(4.9405,0.8876) «(5.0227,-0.0297) 4 2 -2.5697 -2.5000

5.0090,-0.0 1 1 8)

3 *F" (4.6657 0.0112) F'2 (4.0033 0.1004) ♦Г" (4.9950 0.2233) Vй (4.9550 0.6690) f5.0000" [o.oooo, «( 4.3339, 0.0334 ) (3.6706, 0.1 680) ( 4.3339, 0.033 1) «(5.0053,-0.0070) «(4.9852, 0.4429) (4.9253,0.8893) (4.9856,0.4426) 4 2 -2.5163 -2.5000

4.3332,0.04 19)

4 V" (4.4990,0.0252) *У16 (4.8328,0.0028) V" (4.9888,0.3350) *F'"(4.9988,0.1113) (5.00004) [o.oooo J (4.6670,0.0083) «(5.0022,-0.0029 ) «(4.6669,0.0083) (4.98 1 3, 0.4457 ) (4.9964,0.2220) «(5.00 1 3,-0.00 1 7 ) «("4.9963.0.2220"» 4 2 -2.5040 -2.5000

4.6660, 0.0 1 05)

5 *F" (4.9166,0.0007) *F2° (4.9997,0.0551) Г21 (4.9972,0.1671) V" (4.7490,0.0063) '5.0000' ,0.0000J (4.8332, 0.002 1) «(5.0005,-0.0007) «(4.8332, 0.002 1 ) (4.9953 , 0.2230) «(4.999 1 , 0.1 1 09 ) «(5.0003,-0.0004) (4.9991,0.1 1 09) 4 2 -2.5010 -2.5000

4.8329, 0.0026)

6 *F23 (4.9579,0.0002) *F24 (4.9999,0.0263) F"(4.8754,0.0015) F26 (4.9993.0.0832) '5.0000") ,0.0000J (4.9 1 67, 0 .0005) «(5.0001,-0.0002) «(4.9 1 67, 0.0 005 ) (4.99 88, 0.1 1 1 2) « (4.9998, 0.0550) • (5.000 I ,-0.000 l) (4.9998,0.0550) 4 2 -2.5002 -2.5000

4.9 1 66, 0.0007 )

7 V" (4.9358,0.0004) F2'(4.9797,0.0000) F29 (4.9998,0.0409) F3° (5.0000,0.0104) '5.0000") ,0.0000J (4.95 79, 0.0 00 1) (5.0000,-0.000 0 ) (4.95 79, 0.000 1) (4.9997, 0.05 5 0 ) (5.0000, 0.0 263 ) (5.0000,-0.00 00 ) (5.000 0,0.026 3 ) 0 0 -2.5000 -2.5000

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

В качестве тестовой рассмотрим задачу из [80]. f(x,y) = -(х- 20)2 - {у - ю)2 -> min, (4.37) при ограничениях:

X:

2у-х-20<0, х2 +(<у-10)-500<0, -х<0,

-у< о.

4.38)

Для нахождения оптимального решения х* = (0,0), /(х')=-500 и выполнения критерия остановки Мк -тк <0.0001 алгоритму потребовалось 4 итерации. Рис. 4.9 иллюстрирует процесс разбиения симплексов на всех итерациях и сходимость алгоритма к точке минимума. График, представленный на рис. 4.10 показывает поведение оценок снизу и сверху для значения задачи в течение четырех итераций. Максимальное число симплексов, остающихся после отбраковки, равно 2.

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

Рассмотрим задачу из [104], когда оптимальное решение достигается в точке, лежащей на границе только одного из ограничений, определяющих допустимое множество: х„х2) = -129х,2 + 242х,х2 - 129х22 + 1258х, - 1242х2 min, (4.39)

Рис. 4.9. Сходимость алгоритма к точке минимума х* (0,0)

-500 юоо

1500

2000

2500

3000

3500 м шшмшвтш»,

1*. к тК

VW*

Итерации, к

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

X:

-х1-Х2-2< О,

-4хх+Х2 - 8<0,

16xj2 ~Ъ2хх +25*2 -384 <0.

4.40)

Для нахождения оптимального решения х* =(-1,2),/(х;*) = -4871 и для выполнения критерия остановки Мк -тк <0.0001 алгоритму потребовалось 11 итераций. Рис. 4.11 иллюстрирует процесс разбиения симплексов на всех итерациях и сходимость алгоритма к точке минимума. График, представленный на рис. 4.12 показывает поведение оценок снизу и сверху для значения задачи в течение всех итераций. Максимальное число симплексов, остающихся после отбраковки, равно 3. 3

-6 -4 -2 0 2 4 6 8 10 12

Xl ./ ч

Рис. 4.11. Сходимость алгоритма к точке минимума х (-1,2) х ю

-0.5

-1

-1.5

-2

-2.5

X Мк в,»« х-. т iii1 lIU

8 9 10 11

Итерации, к

Рис. 4.12. Поведение оценок снизу и сверху для значения задачи в течение всех итеоапий

Заключение.

Сформулируем основные результаты, полученные в работе.

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

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

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

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

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

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

Основное содержание диссертации изложено в работах [112], [113], [127], [128], [129].

Список литературы диссертационного исследования кандидат физико-математических наук Морозова, Елена Юрьевна, 2007 год

1. Al-Khayyal F. A. Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming // Annals of Operations Research. 1992. - Vol. 34. - P. 125-147.

2. Al-Khayyal F. A. and Falk J. E. Jointly constrained biconvex programming // Mathematics of Operations Research. 1983. - Vol. 8. - № 2. May. - P. 273-286.

3. Al-Khayyal F. A. and Larsen C. Global optimization of a quadratic function subject to a bounded mixed integer constraint set // Annals of Operations Research. 1990.-Vol. 25.-P. 169-180.

4. Ali M., Torn A., Viitanen S. Stochastic Global Optimization: Problem, Classes and Solution Techniques // J. of Global Optimization. 1999. - Vol. 14. p. 437-447.

5. Arrow, Kenneth J., and Alian C. Enthoven. Quasi-Concave Programming // Econometrica. 1961. - Vol. 29. - P. 779-800.

6. Aude C. Dennis J.E. Analysis of Generalized Pattern Searches // SIAM J. Optim. 2003. - Vol. 13. - №3. - P. 889-903.

7. Avriel M. Nonlinear Programming: Analysis and Methods. Prentice-Hall Inc., Englewood Cliffs. NJ, 1976.

8. Bali S. Minimization of a concave function on a bounded convex polyhedron. Ph. D. dissertation, Univ. California. Los Angeles, 1973.

9. Ban Vu Thien. A finite Algorithm for Globally Minimizing a Concave Function under Linear Constraints and its Applications. Preprint Series. №4. Hannoy: Institute of Mathematics, 1983.

10. Barber C.B., Dobkin D.P., Huhdanpaa H.T. The Quickhull Algorithm for Convex Hulls // ACM Transactions on Mathematical Software. 1996. -Vol. 22. - №. 4, Dec. - P. 469-483.

11. Bazara M. S. and Sherali H. D. On the use of exact and heuristic culling plane methods for the quadratic assignment problem // J. Oper. Res. Soc. -1982.-Vol. 15.-P. 991-1003.

12. Benson H. P. On the convergence of two branch and bound algorithms for nonconvex programming problems // JOTA. 1982. - Vol. 36. - P. 129-134.

13. Benson H. P. On the convergence of two branch-and-bound algorithms for nonconvex programming problems // Journal of Optimization Theory and Applications. 36(1), January 1982. Technical Note.

14. Bertsekas D.P. Nonlinear programming, 2th edition. Athena Scientific. Belmont, 1999.

15. Bomze I.M., Csendes Т., Horst, R., Pardalos P.M., eds. Developments in Global Optimization. London, Kluwer, 1997.

16. Box G. E. P. Evolutionary operation: A method for increasing industrial productivity //Appl. Statist. 1957. - Vol. 6. - P. 81-101.

17. Burdet С A. Generating all the faces of a polyhedron, SIAM J. Appl. Math., 26, 1974, pp.72-89.

18. Calvete, H. I. and Gale, C. On the quasiconcave bilevel programming problem // Journal of Optimization Theory and Applications. 1998. - Vol. 98,- P. 613-622.

19. Chung S. J. and Murty K. G. Polynomially bounded ellipsoid algorithms for convex quadratic programming, in Nonlinear Programming 4, 0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds. Academic Press. New York, 1981.-P. 439-485.

20. Dennis J.E. and Torczon V.J. Direct search methods on parallel machines // SIAM J. Optim. 1991. - Vol. 1. - P. 448-474.

21. Dennis J. E., Woods Jr. and D. J. Optimization on microcomputers: The Nelder-Mead simplex algorithm, in New Computing Environments:

22. Microcomputers in Large-Scale Computing, A. Wouk, ed., SIAM. -Philadelphia, 1987. P. 116-122.

23. Dixon L.C.W., Szego G.P. (eds). Towards Global Optimization 2. North-Holland, 1978.

24. Dyer M. E. The complexity of vertex enumeration methods // Math. Oper. Res. 1983. - Vol. 8. - P. 381-402.

25. Dyer M. E. and Proll L. G. An algorithm for determining all extreme points of a convex polytope // Math Progr. 1977. - 12. - P. 81.

26. Evtushenko Yu. G., Potapov M. A., Korotkich V. V. Recent Advances in Global Optimization. Prinston, Princeton University Press, 1992. - P. 274297.

27. Falk I. E. A linear max-min problem // Math. Progr. 1973. - Vol. 5. - P. 169-188.

28. Falk I. E. and Soland R. M. An algorithm for separable nonconvex programming problems // Management Sci. 1969. - Vol. 15. - P. 550-569.

29. Floudas C. A. and Pardalos P. M. A Collection of Test Problems for Constrained Global Optimization Algorithms // Lecture Notes in Computer Science. Springer-Verlag, 1990. Vol. 455.

30. Floudas C.A., Pardalos P.M. (eds). Recent Advances in Global Optimization. Prinston, USA, Printon University Press, 1992.

31. Frieze A. M. A bilinear programrningjormulation of the 1-dimensional assignment problem // Math. Progr. 1974. - Vol. 7. - P. 376-379.

32. Garey M. R., Johnson D. S. and Stockmeyer L. Some simplified NP-complete problems // Theoret. Сотр. Sci. 1976. - Vol. 1. - P. 237-268.

33. Glover F. Convexity cuts and cut search // Oper. Res. 1973. - Vol. 21. - P. 123-134.

34. Gray P., Hart W.E., Painton L., Phillips C., Trahan M., Wagner J. A Survey of Global Optimization Methods. Sandia National Laboratories, 1998.

35. Guisewite G.M., Pardalos P.M. Algorithms for the single-source uncapacitated minimum concave-cost network flow problem // Journal of Global Optim. 1991. - Vol.3. - P. 245-266.

36. Guisewite G.M., Pardalos P.M. A polynomial time solvable concave network flow problem // Network. 1993. - Vol. 23. - P. 143-147.

37. Hadley G. Nonlinear and Dynamic Programming. Addison-Wesley, Reading, MA, 1964.

38. Hammer P L. (TvANESCU). Some network flow problems solved with pseudo-boolean programming // Oper. Res. 1965. - Vol. 13. - P. 388-399.

39. Hoffman K. L. A method for globally minimizing concave functions over convex sets // Mathematical Programming. 1981. - Vol. 20. - P. 22-32.

40. Hoffman K. L. A successive underestimating method for concave minimization problems: Ph.D. thesis. Giorge Washington Univ., Washington, DC, 1975.

41. Hooke R. and Jeeves T. A. "Direct search" solution of numerical and statistical problems // J. Assoc. Comput. Mach. 1961. - Vol. 8. - P. 212229.

42. Horst R. A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization // Journal of Optimization Theory and Applications. 1986. - Vol. 51. - № 2. November. -P. 271-291.

43. Horst R. A note on functions, whose local minimum are global // JOTA. -1982.-Vol. 36.-P. 457-463.

44. Horst R. An algorithm for nonconvex programming problems // Math. Progr. 1976.-Vol. 10.-P. 312-321.

45. Horst R, Muu L.D., Nast M. Branch-and-Bound Decomposition Approach for Solving Quasiconvex-Concave Programs // Journal of optimization theory and applications. 1994. - Vol. 82. - № 2. - P. 267-293.

46. Horst R., and Pardalos P.M., Editors. Handbook of Global Optimization, Klewer Academic Publishers, Dordrecht, Netherlands, 1995.

47. Horst R., Phong T.Q., Thoai N.V. and De Vries J. On solving a d.c. programming problem by a sequence of linear programs // Journal of Global Optim.-1991.-Vol.1.-P. 183-204.

48. Horst R. and Thoai N. V. A decomposition approach for the global minimization of biconcave functions over polytopes // Journal of Optimization Theory and Applications. 1996. - Vol. 88. - P. 561-583.

49. Horst R. and Thoai N. V. An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks. // OR Spektrum. 1998. - Vol. 20. - P. 47-53.

50. Horst R. and Thoai N. V. Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems // Journal of Optimization Theory and Applications. 1992. - Vol. 74. - № 3. September. - P. 469-486.

51. Horst R. and Thoai N. V. Constraint decomposition algorithms in global optimization // Journal of Global Optimization. 1994. - Vol. 5. - P. 333— 348.

52. Horst R., Thoai N. V, and Benson H. P. Concave minimization via conical partitions and polyhedral outer approximation // Mathematical Programming. 1991.-Vol. 50.-P. 259-274.

53. Horst R. and Thoai N. V, and J. de Vries. A new simplicial cover technique in constrained global optimization // Journal of Global Optimization. 1992. - Vol. 2.-P. 1-19.

54. Horst R. and Thoai N. V, and J. de Vries. On geometry and convergence of a class of simplicial covers // Optimization. 1992. - Vol. 25. - P. 53-64.

55. Horst R., Tuy H. Global Optimization, Deterministic Approaches, 3rd Edn. -Springer, Berlin Heidelberg New York, Verlag, 1996.

56. Horst R., Tuy H. On the convergence of global methods in multiextremal optimization // Journal of Optimization Theory and Applications. 1987. -Vol. 54. - № 2. August. - P. 253- 271.

57. Huyer W., A. Neumaier. Global Optimization by Multilevel Coordinate Search // J. of Global Optimization. 1999. - Vol. 14. - P. 331-355.

58. Ivanilov Y. I. and Mukhamediev В. M. An algorithm for solving the linear max-min problem // Izv Akad, Nauk SSSR, Tekhn. Kibernitika. 1976. - № 6.-P. 3-10.

59. Jacobsen S. E. Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints // Appl. Math. Opt. -1982.-Vol. 7.-P. 1-9.

60. Kalantari B. and Rosen J. B. Algoritnm for large-scale global minimization of linearly constrained concave quadratic functions // Math, of Oper. Research. 1987. - Vol. 12. - P. 544-561.

61. Kelly C.T. Iterative Methods for Optimization. SIAM, Philadelphia, PA, 1999.

62. Konno H. A cutting plane algorithm for solving bilinear programs // Math. Progr. 1976. - Vol. 11. - P. 14-27.

63. Kozlov M. K., Tarasov S. P. and Khachian L. G. Polynomial solvability of convex quadratic programming // Soviet Math. Dokl. 1979. - Vol. 20. - P. 1108-1111.

64. Lagarias J.C., Reeds J.A., Wright M.H. and Wright P.E. Convergence properties of the Nelder Mead simplex algorithm in low dimensions // SIAM

65. J. Optim. 1998. - Vol. 9. - P. 112-147.

66. Lawler E. L. The quadratic assignment problem // Manag. Sci. 1963. - Vol. 9.-P. 586-599.

67. Lewis, Robert Michael and Virginia Torczon. Pattern Search Algorithms for Bound Constrained Minimization // SIAM J. Optim. 1999. - Vol. 9. - № 4. -P. 1082-1099.

68. Lewis, Robert Michael and Virginia Torczon. Pattern Search Methods for Linearly Constrained Minimization // SIAM J. Optim. 2000. - Vol. 10, № 3. -P. 917-941.

69. Lewis R. M., Torczon V., and Trosset M. W. Direct search methods: Then and now // J. Comput. Appl. Math. 2000. - Vol. 124. - P. 191-207.

70. Manas M. and Nedoma J. Finding a vertices of a convex polyhedral set // Numer. Math. 1974. - Vol. 9. - P. 35-39.

71. Mangasarian O. L. Characterization of linear complementarity problems as linear programs // Math. Progr. Study. 1978. - Vol. 7. - P. 74-87.

72. Mangasarian O. L. and Shiau Т. H. A variable complexity norm maximization problem // Computer Science Dept., Univ. Wisconsin Tech. Report 568, Univ. Wisconsin, Madison, 1984.

73. Matheissand Т. H., Rubin D. S. A survey and comparison of methods for finding all vertices of convex polyhedral sets // Math. Oper. Res. 1980. -Vol. 5.-P. 167-185.

74. McKinnon K.I.M. Convergence of the Nelder-Mead simplex method to a non-stationary point // SIAM J. Optim. 1998. - Vol. 9. - P. 148-158.

75. McCormick G. P. Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems // Mathematical Programming. 1976. - Vol. 10. - P. 147-175.

76. McCormick G. P. Nonlinear Programming, Theory, Algorithms, and Applications. John Wiley & Sons, 1983.

77. Migdalas A., Pardalos P.M. and Storoy S. Parallel Computing in Optimization. Kluwer Academic Publishers, 1997.

78. Murty K. Solving the fixed charge problem by ranking the extreme points // Oper. Res. 1969. - Vol. 16. - P. 268-279.

79. Muu L. D. and Oettli W. Combined branch-and-bound and cutting plane methods for solving a class of nonlinear programming problems // Journal of Global Optimization. 1993. -3. - P. 377-391.

80. Nazareth L. and Tseng P. Gilding the lily: A variant of the Nelder-Mead algorithm based on golden-section search // Comput. Optim. Appl. 2002. -Vol. 22. - P. 133-144.

81. Nelder J.A. and Mead R. A simplex method for function minimization // Computer Journal. 1965. - 7. - P. 308-313.

82. Pardalos P.M., Rosen J.B. Constrained Global Optimization: Algorithms and Applications // Berlin, Springer Verlag, Lecture Notes in Computer Science Vol. 268, 1987.

83. Pinter J.D. Global Optimization in Action. London, Kluwer, 1996.

84. A. T. Phillips and J. B. Rosen. A parallel algorithm for constrained concave quadratic global minimization. Journal of Optimization Theory and Applications. 1988. - Vol. 42. - P. 421^148.

85. A. T. Phillips and J. B. Rosen. Guaranteed s -approximate solution for indefinite quadratic global minimization // Naval Research Logistics. 1990. -Vol. 37.-P. 499-514.

86. Powell M. J. D. An efficient method for finding the minimum of a function of several variables without calculating derivatives // Comput. J. 1964. - Vol. 7.-P. 155-162.

87. Price C. J., Coope I. D. and Byatt D. A convergent variant of the Nelder-Mead algorithm // J. Optim. Theory Appl. 2002. - Vol. 113. - P. 5-19.

88. Raghavachari M. On connections between zero-one integer programming and concave programming under linear constraints // Oper. Res. 1969. -Vol. 17.-P. 680-684.

89. Ratchek H., Rokne J. New Computer Methods for Global Optimization. -Chichester, Ellis Horwood, 1988.

90. Rinnoy Kan A.H.G., Timmer G.T. Stochastic Global Optimization Methods // Mathematical programming. 1987. - Vol. 39. - P. 27-78.

91. Ritter K. A method for solving maximum problems with a nonconcave quadratic objective function // Z. Wahrsch. Verw. Geb. 1966. - Vol. 4. - P. 340-351.

92. Rosen J.B. Parametric Global minimization for large-scale problems // Technical Report 83-11, Computer science department. University of Minnesota, 1983.

93. Rosen J.B. and Pardalos P.M. Global Minimization of large-scale constrained concave quadratic problems by separable programming // Math. Programming. 1986. - Vol. 34. - P. 163-174.

94. Rosenbrock H. H. An automatic method for finding the greatest or least value of a function // Comput. J. 1960. - Vol. 3. - P. 175-184.

95. Soland R.M. An algorithm for separable nunconvex programming problems II: nonconvex constraints // Manag. Sci.- 1971. Vol. 17. - P. 759-773.

96. Spendley W., Hext G.R. and Himsworth F.R. Sequential applications of simplex designs in optimization and evolutionary operation // Technometrics. 1962.-Vol. 4.-P. 441-461.

97. Thoai N.V. and Tuy H. Convergent algorithms for minimizing a concave function // Math. Oper. Res. 1980. - Vol. 5. - P. 556-566.

98. Torczon V. Multi-Directional Search: A Direct Search Algorithm for Parallel Machines: Ph.D. thesis, Department of Mathematical Sciences, Rice

99. University, Houston, TX, 1989; available as Tech. Rep. 90-07, Department of Computational and Applied Mathematics, Rice University, Houston, TX,1990.

100. Torczon V. On the convergence of the multidirectional search algorithm // SIAMJ. Optim.- 1991. -Vol. l.P. 123-145.

101. Torczon V. On the convergence of Pattern Search Algorithms // SIAM J. Optim. 1997. - Vol. 7. - № 1. - P. 1-25.

102. Tseng P. Fortified-descend simplicial search method: a general approach // SIAMJ. Optim.-2000.-Vol. 10. P. 269-288.

103. Tuy H. Concave minimization under linear constraints with special structure // Optimization. 1985. - Vol. 16.3 - P. 335-352.

104. Tuy H. Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms // Journal of Global Optimization.1991.-Vol. 1. № l.-P. 23-36.

105. Tuy H. Global minimization of the difference of two convex functions // Mathematical Programming Study. 1987. - Vol. 30. - P. 150-183.

106. Tuy H., Migdalas A., and V'arbrand P. A quasiconcave minimization method for solving linear two-level programs // Journal of Global Optimization. -1994.-Vol. 4.-P. 243-263.

107. Tuy H, Thieu T.V. and Thoai NG.Q. A conical algorithm for globally minimizing a concave function over a closed convex set. // Preprint Series. -Vol. 10.-№3. Hanoi: Institute of Mathematics,1985.

108. Torn A., Zilinskas A. Global Optimization. Berlin, Springer Verlag, 1989.

109. Walters F.H., Parker L.R., Morgan S.L., and Deming S.N. Sequential Simplex Optimization. CRC Press, Boca Raton, FL, 1991.

110. Zangwill W. I. A note on functions whose local minima are global // JOTA. -1976.-Vol. 18.-P. 556-559.

111. Zangwill W. I. Minimizing a function without calculating derivatives // Comput. J. 1967. - Vol. 10. - P. 293-296.

112. Zangwill W.L. Minimum concave cost flows in certain networks // Management Science. 1968. - Vol. 14. - №7. - P. 429-450.

113. Zwart P.B. Global maximization of a convex function with linear inequality constraints // Oper. Res. 1974. - Vol. 22. - P. 602-609.

114. Zwart P.B. Nonlinear programming: Conterexamples to two global optimization algorithms. // Oper. Res. 1973. - Vol. 21. - P. 1260-1266.

115. Баушев A.H., Морозова Е.Ю. Метод статистических испытаний в задаче квазивогнутого программирования // Обозрение прикл. и промышл. матем. 2004. - Т. 11. - Вып. 1. - С. 34-40.

116. Баушев А.Н., Морозова Е.Ю., Осьминин А.Т. О математической модели минимизации эксплуатационных затрат при организации вагонопотоков // Вестник ПГУПС. 2004. - Вып. 2. - С. 39-43.

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

118. Буй Тхе Там, By Тхиен Бан. Минимизация вогнутой функции при линейных ограничениях // Экон. и матем. мет. 1985. - Т. XXI. - Вып. 4. -С. 709-714.

119. Дамбраускас А.П. Симплексный поиск. М.: Энергия, 1979. - 176 с.

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

121. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.-368 с.

122. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники. Графы. Оптимизация. М: Наука, 1981. - 344 с.

123. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремум. М.: Наука, 1991. - 248 с.121.3айченко Ю.П. Исследование операций. Киев. Вища школа, 1975. -320 с.

124. Канторович JI. В., Гавурин М К. Применение математических методов в вопросах анализа грузопотоков // Проблемы повышения эффективности работы транспорта. М.: Издательство АН СССР, 1949. - С. 110-138.

125. Карманов В.Г. Математическое программирование. М.: Физматлит, 2001.-264 с.

126. Кендалл М., Моран П. Геометрические вероятности М.: Наука, 1972. -192 с.

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

128. Магарил-Ильяев Г.Г., Тихомиров В.М. Выпуклый анализ и его приложения. М.: Эдиториал УРСС, 2000. - 176 с.

129. Морозова Е.Ю. Об алгоритме решения транспортной задачи с квазивогнутой функцией стоимости // Известия ПГУПС. 2005. - Вып. 1.-С. 194-199.

130. Морозова Е.Ю. Об определении диаметра конечного множества точек в евклидовом пространстве // Известия ПГУПС. 2004. - Вып. 1. - С. 126-130.

131. Морозова Е.Ю. Рекурсивный алгоритм прямого поиска минимума функции нескольких переменных. // Обозрение прикл. и промышл. матем. 2006.-Т. 13.-Вып. 5.-С. 783-796.

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

133. Рокафеллар Р.Т. Выпуклый анализ/Пер. с англ. М.: Мир, 1973. - 470 с.

134. Тхоаи Н. В., Туй X. Решение линейной задачи о дополнительности, используя вогнутое программирование // Журнал вычислит, матем. и матем. физики. 1983. - Т. 23. - Вып. 3. - С. 602-608.

135. Уткин C.JL, Хачатуров В.Р., Туй Хоанг. О конусных алгоритмах для решения задачи вогнутого программирования и некоторых ее обобщений // Ж. вычисл. матем. и матем. физики. 1988. - Т. 28. - С. 992-999.

136. Фихтенгольц Г.М. Основы математического анализа. Т. 1. М.: ФИЗМАТЛИТ, 2002. - 416 с.

137. Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. -М.: Наука, 1985.-416 с.

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

139. Шульга A.M., Смехова Н.Г. Себестоимость железнодорожных перевозок. М: Транспорт, 1985. - 280 с.