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

Размещено на http://www.allbest.ru/

ГЛОБАЛЬНАЯ МИНИМИЗАЦИЯ КВАЗИВОГНУТЫХ ФУНКЦИЙ НА ВЫПУКЛЫХ МНОЖЕСТВАХ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени

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

Морозова Елена Юрьевна

Санкт-Петербург 2007

Работа выполнена на кафедре прикладной математики Петербургского государственного университета путей сообщения.

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

Официальные оппоненты: доктор физико-математических наук, профессор Демьянович Юрий Казимирович;

доктор физико-математических наук, профессор Шапорев Сергей Дмитриевич

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

Защита состоится 14 марта 2007 г. в 15 часов на заседании диссертационного совета K 212.223.01 при ГОУ ВПО «Санкт-Петербургский государственный архитектурно-строительный университет» по адресу: 190005, Санкт-Петербург, 2-я Красноармейская ул., д. 4, ауд. 505 А.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Санкт-Петербургский государственный архитектурно-строительный университет»

Автореферат разослан « ___ » февраля 2007 г.

Ученый секретарь

диссертационного совета В.А. Фролькис

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 12 работ.

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

Содержание работы

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

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

В разделе 1 рассматривается задача

, (1)

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

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

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

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

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

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

. (2)

Семейство покрывает все пространство и поскольку D - замкнутая ограниченная область, то найдутся значения и такие, что для каждого получим , а для каждого . Имеет место представление

. (3)

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

. (4)

Для доказательства сходимости предлагаемого алгоритма используются следующие утверждения.

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

. (5)

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

Предложение 1.2. Если множество D выпукло, а f - выпуклая функция на D, то функция F выпукла на отрезке .

Предложение 1.3. Если множество D выпукло, а f - строго унимодальная функция на D, то функция F строго унимодальна на отрезке .

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

Имеет место следующий результат.

Теорема 1.1. Если f - непрерывная строго унимодальная функция на n-мерном симплексе S, , - аппроксимация точки минимума, полученная после -й итерации описанного выше алгоритма, то при , .

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

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

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

В разделе 2 главы 1 рассматривается модификация алгоритма из раздела 1 для решения задачи безусловной минимизации вида

, , (6)

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

Предлагаемый алгоритм состоит в последовательном решении задач условной оптимизации вида

, (7)

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

. (8)

Итерационный процесс останавливается, когда точка становится внутренней точкой симплекса .

Построенная последовательность симплексов удовлетворяет следующей теореме.

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

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

В качестве примера эффективности алгоритма для минимизации негладких функций рассмотрим следующий вариант функции Денниса-Вуда:

, (9)

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

На рис. 1 а) показаны линии уровня функции, последовательность симплексов и точки минимума функции на каждом из них. Точка и является решением задачи. На рис. 1 б) представлены значения функции на каждом цикле (симплексе) и на каждой итерации.



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

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

, (10)

при ограничениях

, , (11)

где - квазивогнутая функция, , A - матрица размера .

Относительно матрицы A и вектора b системы (11) будем предполагать, что они содержат только неотрицательные элементы. В этом случае допустимое множество X задачи (если оно не пусто) ограничено и представляет собой выпуклый многогранник. Отметим также, что когда речь идёт о канонической форме записи совокупности линейных ограничений, т.е. о форме (11), то, не нарушая общности, можно считать, что .

Функция , определенная на выпуклом множестве X, называется квазивогнутой, если для каждого вещественного числа c множество выпукло.

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

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

1. Нахождение точки локального минимума , при этом ;

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

3. Усечение исходного множества опорной гиперплоскостью к поверхности текущего уровня целевой функции .

4. Применение шагов 1. 3. к усеченному множеству.



Рис. 2 Графическая иллюстрация метода

Корректность работы алгоритма основывается на следующем утверждении.

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

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

В третьей главе предлагается модификация алгоритма из главы 2 для решения транспортной задачи с квазивогнутой функцией стоимости следующего вида:

, (12)

, (13)

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

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

Алгоритм решения задачи (12) - (13) аналогичен алгоритму решения общей задачи квазивогнутого программирования (10) - (11) из главы 2 с предлагаемой модификацией. Основные шаги алгоритма для невырожденного случая следующие.

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

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

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

Итерационная процедура заключается в последовательном применении шагов 2 и 3. Процесс останавливается тогда, когда все попытки моделирования точки из шага 2 оказываются неудачными.

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

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

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

Рассматривается задача

, (15)

где, - квазивогнутая функция на пространстве , - выпуклая функция, определенная на .

Будем предполагать, что множество ограничено.

Допустим, что , где P и Q - выпуклые многогранные множества, причем вершины множества лежат на границе множества и пусть найдены числа

, (16)

. (17)

Если обозначим через - искомое значение глобального минимума, то , поэтому если для заданного числа выполняется неравенство

(18)

и , то план можно считать -решением задачи (15).

При таком подходе важно, с одной стороны, уметь находить m и M, с другой стороны, в случае нарушения неравенства (18) нужно иметь процедуры расширения множества Q и уменьшения множества P, которые гарантировали бы выполнение неравенства (18) после достаточного числа итераций.

Предлагаемый алгоритм состоит из двух этапов.

На первом этапе решается задача построения симплекса Q, вписанного в множество X и построения оценки сверху M (17) для значения задачи (15).

Второй этап представляет собой итерационную процедуру, включающую следующие шаги:

1) Построение выпуклого множества P, содержащего множество X.

2) Сужение исследуемой области.

3) Получение новой оценки снизу для значения задачи (15).

4) Получение новой оценки сверху для значения задачи (15).

5) Проверка условий (18) остановки алгоритма. В случае невыполнения условия - переход к следующему шагу.

6) модификация многогранника Q.

Наибольшую сложность представляет процедура построения множества P, содержащего выпуклое множество X. Опишем этот шаг подробно.

Пусть в результате выполнения первого этапа имеется симплекс Q, вписанный в множество X и оценка сверху M для значения задачи (15).

Обозначим через - вершины симплекса Q, - грани симплекса Q. Пусть - центр тяжести симплекса Q.

Для каждого рассмотрим симплекс

. (19)

Размерность симплекса равна . Заметим, что если , то

. (20)

Определим

(21)

и пусть (рис. 3).

Рис. 3 Построение многогранника P, содержащего множество X

Рассмотрим функцию

, где . (22)

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

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

, (23)

находим вершины

, . (24)

Обозначим множество вершин через .

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

. (25)

Тогда в качестве оценки снизу для значения задачи (15) можно взять величину (16).

Доказательство сходимости алгоритма основано на следующих фактах.

Если - многогранники, построенные на k-й итерации алгоритма, - часть множества X, оставшаяся на k итерации, то справедливы соотношения: , причем . Тогда расстояние Хаусдорфа при . Поэтому для непрерывной функциии f, начиная с некоторого k, будут выполняться неравенства (18).

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

Основные результаты

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

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

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

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

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

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

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

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.

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

11. Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков А.С. О задаче математического программирования, возникающей в проблеме минимизации эксплутационных затрат при организации вагонопотоков // Аннотации докладов восьмой международной научно-практической конференции “ИНФОТРАНС - 2003”. СПб., 2003. C. 46.

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

Размещено на Allbest.ru

...