Главная >> Диссертации - все темы

Pages: |

| 2 |

«МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДОПОЛНИТЕЛЬНОСТИ И ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ ...»

-- [ Страница 1 ] --

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК

ИНСТИТУТ ДИНАМИКИ СИСТЕМ И ТЕОРИИ УПРАВЛЕНИЯ

СИБИРСКОГО ОТДЕЛЕНИЯ РАН

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

Петрова Елена Геннадьевна

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

ДОПОЛНИТЕЛЬНОСТИ И ДВУХУРОВНЕВОГО

ПРОГРАММИРОВАНИЯ

Специальность 05.13.01 – системный анализ, управление и обработка информации (в технике, экологии и экономике) Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель:

доктор физико-математических наук, профессор А.С. Стрекаловский Иркутск- Оглавление Введение 1 Оптимизационный подход к решению линейной задачи дополнительности 1.1 Постановка задачи. Различные формулировки линейной задачи дополнительности....................... 1.2 Редукция к задаче d.c. минимизации...................... 1.3 Специальный метод локального поиска..................... 1.4 Построение тестовых примеров и апробация алгоритма локального поиска.......................... 1.5 Алгоритм глобального поиска.......................... 1.6 Вычислительный эксперимент.......................... 1.6.1 Выбор аппроксимации поверхности уровня............... 1.6.2 Согласование точностей локального и глобального поиска............................ 1.6.3 Решение серий задач........................... 1.7 Основные результаты главы........................... 2 Поиск оптимистических решений в линейной двухуровневой задаче 2.1 Постановка линейной двухуровневой задачи.................. 2.2 Сведение двухуровневой задачи к задаче с d.c. ограничением....... 2.3 Условия глобальной оптимальности для задачи минимизации с d.c. ограничением-равенством......................... 2.4 Минимизирующие последовательности..................... 2.5 Стратегия глобального поиска.......................... 2.6 Решение возмущенной задачи.......................... 2.7 Локальный поиск в задаче с d.c. ограничением-равенством......... 2.7.1 Генерация тестовых задач........................ 2.7.2 Тестирование метода локального поиска................ 2.8 Глобальный поиск в линейной двухуровневой задаче............. 2.9 Вычислительный эксперимент.......................... 2.9.1 Первый этап. Выбор аппроксимации поверхности уровня...... 2.9.2 Второй этап. Оценка сложности задач................. 2.9.3 Третий этап. Решение задач высокой размерности.......... 2.10 Задача планирования производства в условиях неизвестного спроса.... 2.11 Основные результаты главы........................... 3 Методы решения уравнений с d.c. функциями 3.1 Решение одного уравнения с d.c. функцией.................. 3.2 Доказательство сходимости ПВК........................ 3.3 Вычислительный эксперимент.......................... 3.4 Решение систем нелинейных уравнений..................... 3.5 Особенности решения квадратичных систем уравнений........... 3.6 Численное решение систем уравнений...................... 3.6.1 Квадратичные уравнения......................... 3.6.2 Нелинейные уравнения.......................... 3.7 Основные результаты главы........................... Заключение Список использованной литературы Введение В последние годы круг приложений методов нелинейной оптимизации неуклонно расширяется. Если прежде в задачах планирования и управления экономическими объектами использовалось, как правило, линейное программирование, то теперь все чаще в экономико-математических исследованиях возникают нелинейные экстремальные задачи [60, 63]. При этом, по мнению ряда специалистов, наиболее сложными для решения являются оптимизационные задачи с нелинейными ограничениями-равенствами, в которых зачастую затруднительно нахождение даже допустимой точки [84, 110, 126]. Однако необходимость решения таких задач на практике побуждает исследователей к разработке эффективных численных методов.

Методы решения экстремальных задач с равенствами многочисленны и разнообразны.

Их можно классифицировать как по формальным признакам, так и по содержательным.

Так, выделяются методы нулевого, первого и второго порядков в зависимости от порядка используемых производных [3, 9, 15, 57]. Методы также делятся на прямые (в которых итерации ведутся в пространстве прямых переменных) [3, 4, 9, 57, 84] и двойственные (которые существенно используют двойственные переменные) [5, 9, 57]. Во многих методах на каждом шаге решается некоторая вспомогательная задача, и, с вычислительной точки зрения, удобно вести классификацию по ее типу. Это может быть задача безусловной минимизации, задача минимизации линейной или квадратичной функции при линейных ограничениях и т.д. Кроме того, одни методы направлены на поиск глобального решения задачи, другие же позволяют найти только локальный экстремум. Наконец, сами идеи, лежащие в основе методов, весьма различаются. Выделим основные направления в развитии данных методов.

В задачах небольшой размерности для нахождения стационарных точек, которые могут быть описаны системой Лагранжа [31], можно применять, например, метод Ньютона и его различные модификации [25, 45], а также методы безусловной минимизации [9, 57, 126] после сведения системы к оптимизационной задаче. Принципиальным недостатком такого подхода является то, что при этом пропадает оптимизационная сущность самой задачи, и, в частности, локальные максимумы и минимумы при использовании данного подхода не различаются.

Методы типа приведенных градиентов [15], получающиеся обобщением стандартных подходов к решению задач с линейными ограничениями на нелинейный случай, неплохо работают для задач, ограничения которых "почти линейны". Если же нелинейность ограничений значительна и начальная точка далека от оптимальной, то продвижение к решению будет осуществляться очень малыми шагами.

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

На подобной идее основаны популярные в настоящее время методы последовательного квадратичного программирования (SQP-методы) [15, 31, 126], заключающиеся в решении задач выпуклого квадратичного программирования, аппроксимирующих исходную задачу оптимизации. Правильно выбранная задача квадратичного программирования оказывается достаточно адекватной локальной аппроксимацией исходной задачи. В то же время квадратичная задача достаточно проста, и для нее существуют эффективные методы решения. На сегодняшний день SQP-методы входят в число наиболее эффективных методов условной оптимизации [31, 126].

Другим направлением в решении задач с ограничениями-равенствами являются двойственные методы [57] (например, метод Эрроу-Гурвица), в которых одновременно происходит минимизация функции Лагранжа по x и максимизация по двойственным переменным y. Другим двойственным подходом является метод модифицированной функции Лагранжа [5], который основан на добавлении гладкого штрафного слагаемого к функции Лагранжа минимизируемой функции, в результате чего получается так называемое семейство модифицированных функций Лагранжа.

Однако все утверждения относительно сходимости перечисленных методов носят локальный характер, т.е. гарантируют нахождение лишь локального экстремума. Исключением является метод штрафов и различные его модификации [9, 36, 57, 60, 84, 126], сходимость которых носит глобальный характер. Метод штрафных функций является одним из наиболее простых и широко известных методов решения задач математического программирования. Основная его идея состоит в приближенном сведении задачи минимизации с ограничениями к задаче безусловной минимизации некоторой функции. При этом вспомогательная функция подбирается так, чтобы она совпадала с заданной минимизируемой функцией внутри допустимой области и быстро возрастала вне ее. Здесь все трудности перенесены на этап решения вспомогательных задач безусловной минимизации, которые обычно оказываются невыпуклыми. Основной же недостаток метода состоит в том, что параметр штрафа должен бесконечно увеличиваться, а с ростом параметра задача становится все хуже обусловленной: целевая функция приобретает все более "овражный" характер.

Другой подход в области штрафных функций заключается в таком построении вспомогательных функций, что для соответствующего выбора параметра однократная безусловная оптимизация дает решение исходной задачи. Это так называемый метод точной штрафной функции [22, 26, 27, 28]. Однако точные штрафные функции, как правило, оказываются недифференцируемыми, что придает дополнительную сложность при их минимизации.

Наконец, все большую популярность для поиска глобального решения невыпуклых задач, в том числе задач с равенствами, приобретают методы ветвей и границ, отсечений, аппроксимаций и т.д., идеи которых заимствованы из дискретной оптимизации [63, 116, 124, 129, 139]. К настоящему моменту предложено огромное количество алгоритмов, использующих различные варианты отыскания оценок и построения дерева поиска в задачах с равенствами. Одним из недостатков этих подходов является так называемое "проклятие размерности", которое означает, что с увеличением размерности объем вычислений по этим методам возрастает экспоненциально [129, 139], что не позволяет найти именно глобальное решение.

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

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

1. D.C. минимизация где g(·), h(·) выпуклые функции на некотором открытом выпуклом множестве 2. Экстремальные задачи с d.c. ограничениями, простейшей из которых является задача следующего вида где F (x) = g(x) h(x), x, а h(·), g(·), f (·) являются выпуклыми функциями на выпуклом открытом множестве I n, содержащем множество D, F (·) непрерывная функция на I n.

Отметим, что в случае, когда функция g(·) тождественно равна нулю, то в первом случае получаем задачи выпуклой максимизации [66, 69], а во втором обратно-выпуклые задачи [69, 71].

Понятие d.c. функции (функции, представимой в виде разности двух выпуклых функций) является одним из базовых в невыпуклой оптимизации.

Пионером в изучении свойств d.c. функций является А.Д. Александров [1]. Позже этой проблемой занимались Е.М. Ландис [40] и П. Хартман [105]. Некоторые более поздние работы по d.c. структурам можно найти в [107, 128].

Хотя исследование задач d.c. оптимизации (исключая частный случай выпуклую максимизацию) началось сравнительно недавно, не более 40 лет назад, к настоящему моменту достигнуты определенные успехи. Во-первых, предложены условия глобальной оптимальности [65, 108, 109, 134], использующие современный аппарат выпуклого анализа [37, 59]. Кроме того, разрабатывается теория двойственности [107, 111, 137], а также связанные с характеризацией оптимума и двойственностью задач различные условия регулярности [111, 137].

В частности, на основе предложенных А.С. Стрекаловским условий глобальной оптимальности для представленных выше классов задач [67, 69, 70] были разработаны алгоритмы глобального поиска для решения многих актуальных теоретических и прикладных невыпуклых задач оптимизации [19, 44, 66, 68, 72, 78].

Стратегия глобального поиска состоит из двух основных этапов: а) локального поиска и б) процедуры выхода из локального экстремума (критической точки), включающей в себя построение аппроксимациии поверхности уровня выпуклой функции, задающей базовую невыпуклость в исследуемой задаче, решение линеаризованных задач и ряд других [67, 69, 70].

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

где F (x) = g(x) h(x), g(·), h(·), f (·) выпуклые функции.

В работе предложены алгоритмы глобального поиска в задачах вида (3), базирующиеся на теории глобального поиска А.С. Стрекаловского. [67, 69, 70, 72].

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

Были выбраны следующие объекты диссертационного исследования:

• линейная задача дополнительности;

• линейная двухуровневая задача;

• одно уравнение с d.c. функцией и системы уравнений с d.c. функциями.

Как известно [88, 99, 100], линейная задача дополнительности (ЛЗД) содержит в себе комплементарное ограничение-равенство. Следующий же объект линейная двухуровневая задача может быть проинтерпретирован как некоторое усложнение предыдущей ЛЗД, поскольку после сведения двухуровневой задачи к оптимизационной, мы получаем задачу с линейной целевой функцией и схожими нелинейными комплементарными ограничениями. Для получения же допустимой точки в задачах оптимизации с равенствами требуется нахождение решения уравнения или системы уравнений.

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

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

Далее представим более подробно постановки задач и их особенности.

В первой главе диссертации исследуется линейная задача дополнительности (ЛЗД) [88, 99, 100, 101, 104, 113, 123, 125, 127, 131, 135, 117], состоящая в нахождении пары векторов (x, w), удовлетворяющих следующим условиям:

где x, w I n, а вектор q I n и вещественная, подчеркнем, знаконеопределенная (nn)R R матрица M заданы. Нетрудно видеть, что задачу (4) можно также записать в следующем Теория линейной дополнительности, впервые представленная в работах Коттла [99], Данцига [101], Лемке [122], интенсивно развивается три последних десятилетия, главной причиной чего служит связь ЛЗД с задачами линейного и квадратичного программирования [58]. Исторически задачу ЛЗД можно рассматривать в качестве объединяющей формулировки для задач линейного, квадратичного программирования и биматричных игр [100].

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

Решение ЛЗД в общем случае является нетривиальной задачей. Как известно [97], получение ответа на вопрос, имеет ли решение ЛЗД с целочисленными коэффициентами, оказывается NP-полной задачей [131]. Поэтому наиболее эффективными являются методы, ориентированные на использование свойств матрицы M, т.е. на отдельные классы ЛЗД. Таковыми могут быть, в частности, задачи с матрицами, имеющими неотрицательные главные миноры (или P0 -матрицами) [99, 100]. Другим подобным классом могут быть задачи с матрицами, имеющими неположительные внедиагональные элементы (или Zматрицами). Тогда можно построить эффективные методы решения как для ЛЗД, так и для ее нелинейных обобщений (напр., [104, 135]). Именно поэтому наибольшее количество работ традиционно посвящено методам решения ЛЗД с неотрицательно определенными матрицами и с матрицами, имеющими положительные главные миноры. В качестве приоритетных можно выделить два основных направления развития.

Первое направление это методы крайних точек ("pivoting methods"), являющиеся, по сути, разнообразными модификациями метода Лемке-Хаусона [100]. Процедура поиска решения основана на переборе крайних точек многогранного множества Каждая итерация метода соответствует движению из крайней точки множества S вдоль некоторого его ребра, почти удовлетворяющего условиям дополнительности, т.е. ребра, на котором xi wi = 0 только для одного значения индекса i {1,..., n}.

Этот метод является конечным вследствие конечного (но, возможно, очень большого) числа крайних точек многогранного множества. Однако нахождение решения ЛЗД (в случае его существования) гарантировано только при определенных условиях, налагаемых на матрицу M [58], например, при положительности всех ее главных миноров. Кроме того, данные методы эффективны в основном на задачах малой и средней размерности. С ростом размерности задачи резко увеличивается количество перебираемых вершин (как известно, количество вершин многогранного множества возрастает экспоненциально).

Второй подход к решению ЛЗД (который применяется в диссертационной работе) это вариационный метод, заключающийся в минимизации некоторой целевой функции, например, скалярного произведения x, w на допустимом множестве S. Для решения такой задачи применяются, например, методы внутренних точек [23, 24, 30, 120] и специализированные методы квадратичного программирования [3, 16, 81, 126]. При решении вариационной задачи, как и в первом случае, успешность применяемых методов зависит от свойств матрицы M. Так, в случае знаконеопределенности матрицы M (что порождает невыпуклость в задаче), возникают проблемы с поиском глобального решения, поскольку стандартные методы выпуклой оптимизации в этом случае позволяют найти, в лучшем случае, локальное решение, а чаще лишь стационарную точку, которая может быть далека от глобального оптимума.

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

Пример 0.0.1 Равновесие рынка Рассмотрим следующую модель рыночного равновесия [100]:

Здесь x количество производимого товара, c вектор затрат на производство, неравенство Ax b описывает технологические ограничения, B матрица ограничения на спрос, вектор r задает количество потребления.

Поведение потребителей характеризуется следующим образом:

где p вектор цен, функция Q(p) = Dp+d вектор-функция потребления, описывающая зависимость спроса от рыночных цен.

При этом должны выполняться условия равновесия:

где y двойственный вектор теневых (скрытых) цен, который может быть найден как решение двойственной [10] к (7) задачи, которая имеет следующий вид:

Тогда по теореме двойственности [10] или применив теорему Каруша-Куна-Таккера к задачам (7) и (10), получаем, что нахождение решения задач (7),(10) с учетом (8) эквивалентно решению системы Отметим, что в системе (11) присутствуют нелинейные ограничения-равенства. При этом нетрудно видеть, что система (11) имеет вид ЛЗД с переменной z = (x, v, y)T, где В этом случае свойства матрицы M, в частности, симметричность и положительная определенность, напрямую зависят от вида матрицы D, которая характеризует поведение потребителей и может, вообще говоря, иметь произвольный вид. Таким образом, в общем случае получившаяся ЛЗД имеет знаконеопределенную матрицу M. # Кроме того, к задачам линейной дополнительности часто сводятся различные технические и экономические задачи. В [100] авторы рассматривают следующие постановки:

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

С целью преодоления невыпуклости вариационной задачи в первой главе применяется теория глобального поиска [69], [70] для минимизации целевой функции, представимой в виде разности двух выпуклых функций (d.c. функции).

В §1.1 представлены различные формулировки ЛЗД, показана ее связь с задачами линейного и квадратичного программирования, с биматричными играми. Далее, в §1. производится сведение исходной задачи к задаче d.c. минимизации. Параграфы 1.3–1. посвящены методу локального поиска в задаче линейной дополнительности. В §1.5 предлагается алгоритм глобального поиска, заключающийся в последовательном решении более простых подзадач и основанный на условиях глобальной оптимальности. Наконец, в §1.6 представлены результаты численного эксперимента на серии случайно сгенерированных задач. Здесь решается вопрос выбора аппроксимации поверхности уровня выпуклой функции, позволяющей более эффективно находить глобальные решения, вопрос согласования точностей локального и глобального поиска. Далее проводится вычислительный эксперимент на задачах повышенной размерности.

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

В настоящее время задачи с иерархической структурой, возникающие на практике при исследовании сложноорганизованных систем в технике и экономике, являются весьма популярным объектом для математического исследования [11, 89, 90, 92, 96, 98, 103, 114, 132, 136, 138], популярность которого объяснятеся прежде всего широким полем приложений [90]. С другой стороны, иерархическая структура задач и связанная с ней скрытая невыпуклость даже в простейшем линейном случае [103] вызывают трудности исследования таких задач.

В работе исследуется непрерывная двухуровневая задача с линейными целевыми функциями на верхнем и нижнем уровнях [90, 103]. При этом предполагается, что из всех возможных решений на нижнем уровне выбирается то, которое благоприятствует достижению цели верхнего уровня. Такая постановка двухуровневой задачи носит название оптимистической (кооперативной) [103]. Будем рассматривать линейно-линейную двухуровневую задачу в следующей постановке:

где множество Y (x) определено системой неравенств:

(p m), (q m), (q n) соответственно.

Несмотря на внешнюю простоту, задача (BP)–(13) оказывается весьма сложной для решения. В §2.2 представлен пример, иллюстрирующий невыпуклость линейной двухуровневой задачи в самом простейшем случае.

За три десятилетия интенсивного исследования непрерывных двухуровневых задач различных классов было предложено достаточно много методов их решения (см., например, обзоры [98, 103]).

В линейно-линейном случае двухуровневая задача обладает тем свойством, что хотя бы одно ее глобальное решение достигается в крайней точке допустимого множества, поэтому широкий класс методов решения таких двухуровневых задач базируется на переборе вершин допустимого множества. Первые результаты в этом направлении были опубликованы в [96], а затем получили развитие в [102, 136] и др.

Еще одним интенсивно развивающимся направлением является разработка методов спуска, предназначенных для поиска стационарных точек и локальных минимумов в двухуровневых задачах [132].

Наиболее популярным подходом к решению двухуровневых задач является разработка методов, основанных на замене задачи нижнего уровня ее условиями оптимальности (что возможно в случае выпуклой, в частности, линейной, целевой функции нижнего уровня по своей переменной) [103]. В результате вместо двухуровневой получаем эквивалентную ей одноуровневую задачу, но содержающую в своей структуре невыпуклое ограничениe-равенство, которое и создает сложности при ее решении. В этом случае мы имеем дело с задачей, принадлежащей классу задач с комплементарными ограничениями, специальная структура которых создает трудности ее эффективного численного решения [32]. Тем не менее, учитывая комплементарность множителей Лагранжа и ограничений задачи нижнего уровня, можно предложить различные варианты метода ветвей и границ [89, 130]. Один из подходов в этом случае также составляют так называемые методы релаксации, в которых ограничение-равенство параметрически возмущается так, чтобы получаемая задача могла обладать свойствами регулярности ограничений [32].

Другой подход к решению двухуровневых задач решение последовательности вспомогательных задач линейной дополнительности (см., например, [114]), что, по сути, представляет собой симбиоз методов крайних точек и ветвей и границ.

Кроме того, при использовании подхода, основанного на сведении двухуровневой задачи к одноуровневой, для решения последней часто применяется метод штрафов [94], хотя в силу невыпуклости оштрафованной целевой функции, такой подход обоснован только лишь для поиска локальных экстремумов [95]. В то же время уже удалось успешно использовать данный метод для численного поиска глобального решения [79, 80] в двухуровневых задачах с квадратичной целевой функцией на верхнем и линейной целевой функцией на нижнем уровнях.

Насколько можно судить по доступной литературе, размерность, которую приводят авторы публикаций при тестировании предлагаемых алгоритмов, является недостаточной для решения практических задач. Эффективно решаются только линейно-линейные задачи средней размерности. Так, в [89] приведены результаты решения таких задач с суммарным числом переменных до 130, а в [130] до 200.

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

Пример 0.0.2 Планирование производства в условиях неизвестного спроса [90] Предположим, что производитель желает определить, в каких объемах ему следует производить n товаров в каждый из рассматриваемых T периодов. Вектор объемов производства обозначим через x I nT. Задача производителя только с одним потребителем (например, производство комплектующих деталей для последующей сборки автомобилей на автозаводе). Вектор спроса в t-й момент не известен точно, а лежит во множестве Yt, границы которого зависят от его затрат на рекламу, которые выражаются вектором v I nT.

В модели будем использовать следующие обозначения.

Параметры aijt количество ресурса i, необходимого для производства единицы продукции j в bit количество ресурса i, доступное в момент t;

pjt цена продажи продукта j в момент t;

cjt стоимость производства продукта j в момент t;

hjt цена хранения единицы продукта j в момент t;

sjt цена производства единицы продукта j по субконтракту в момент t;

dj место, требуемое для хранения единицы продукции j;

lt свободное место под хранение, имеющееся в момент t.

Переменные xjt количество продукта j, производимого в момент t;

vjt затраты на рекламу продукта j в момент t;

zjt нехватка продукта j в момент t;

wjt избыток продукта j в момент t;

Множества Vj ограничения на рекламные расходы на продукт j;

Yt (v) множество, содержащее вектор спроса yt в момент t.

Таким образом, задача верхнего уровня имеет следующий вид:

в то время как задача нижнего уровня формализуется следующим образом:

Неравенства (16) задают ресурсные ограничения. Ограничения на рекламные затраты заданы в (18) и влияют на спрос посредством (23). Уравнение (20) отражает материальный баланс. Начальные запасы полагаются нулевыми (формула (22)). Если Vj и Yt многогранные множества, задача (15)–(23) является задачей линейного двухуровневого программирования.

В диссертационной работе производится разработка эффективного метода линейной двухуровневой оптимизации, позволяющего численно решать задачи высокой размерности. Для этого используется подход, основанный на редукции двухуровневой задачи в оптимистической постановке к задаче оптимизации с билинейным ограничениемравенством. Как известно, билинейная функция может быть представлена в виде разности двух выпуклых функций [44, 78], поэтому для решения получившейся задачи оптимизации в работе применяется теория глобального поиска для задач с d.c. ограничениемравенством.

В §2.1 дается постановка задачи и обсуждается ее так называемая скрытая невыпуклость. В §2.2 производится сведение двухуровневой задачи к оптимизационной задаче с d.c. ограничением-равенством. §2.3 посвящен условиям глобальной оптимальности для задач с d.c. равенством в общем виде. Затем §2.4 обобщает условия глобальной оптимальности на случай минимизирующих последовательностей. В §2.5–§2.6 описаны общие концепции глобального поиска для задачи с d.c. ограничением.

В §2.6 обсуждается возможность применения предложенной выше теории для решения линейной двухуровневой задачи. Для выполнения условий регулярности вводится возмущенная задача и изучается ее связь с исходной двухуровневой задачей.

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

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

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

Третья глава посвящена поиску точек, удовлетворяющих ограничениям равенствам.

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

выпуклые на I n функции. Необходимость решения одного уравнения со многими неизвестными возникает, например, в случае построения допустимой точки в задаче оптимизации с ограничением-равенством (см. §2.3). При этом разработанный метод позволяет находить специальную допустимую точку, наиболее подходящую, с точки зрения целевой функции. В одномерном случае это означает нахождение минимального корня уравнения, что находит широкое приложение во многих прикладных задачах: фазового детектирования, частотно-временного анализа, теории фильтров (см., например, [62]).

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

ставится задача поиска всех корней системы уравнений. Результаты по решению задачи в такой постановке можно найти, например, в [6, 7].

Несмотря на широкий спектр методов [4, 12, 25, 45], разработанных в этой области, проблема численного поиска решений систем нелинейных уравнений остается весьма актуальной.

Так, при применении методов типа Ньютона возникает трудность, заключающаяся в выборе подходящего начального приближения, обеспечивающего сходимость к решению [4, 9, 45, 64, 83]. Причем с ростом размерности системы сложность поиска стартовой точки многократно возрастает. Большие трудности при применении Ньютоновских методов также создает наличие в системе кратных корней [8].

В случае же использования вариационных методов, мы имеем дело с невыпуклой экстремальной задачей, а для ее решения неприемлемы стандартные методы выпуклой оптимизации, имеющие свойство отыскивать в лучшем случае лишь локальные решения или стационарные точки, которые могут быть весьма далеки от глобального решения [9, 57, 69, 81].

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

В последние десятилетия разработаны и успешно применяются на практике интервальные методы для доказательного глобального решения уравнений и систем уравнений [86], однако непреодолимым ограничением в этом случае является размерность систем.

Третья глава посвящена решению нелинейных уравнений и систем нелинейных уравнений. В §3.1 предлагается процедура выпуклой комбинации (ПВК) для решения одного уравнения со многими неизвестными, задаваемого d.c. функцией. В §3.2 доказываются теоремы сходимости предложенного алгоритма, а в §3.3 проводится численное тестирование.

В §3.4–§3.6 рассматривается решение систем нелинейных уравнений. В §3.4 приведена постановка задачи. Как и линейная задача дополнительности в главе 1, система уравнений сводится к задаче d.c. минимизации, для которой предлагается алгоритм глобального поиска. В §3.5 уточняется выбор параметров алгоритма на случай квадратичных уравнений, а в §3.6 проводится вычислительный эксперимент.

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

Основные результаты диссертационной работы являются новыми и заключаются в следующем:

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

2. Для линейных двухуровневых задач разработаны алгоритмы локального и глобального поисков оптимистических решений, позволяющие решать задачи высокой размерности (до 500 переменных на каждом уровне). Предложенные алгоритмы базируются на взаимосвязях линейных двухуровневых задач и невыпуклых задач математического программирования с нелинейными ограничениями-равенствами, а также теории глобального поиска в задачах с d.c. ограничениями.

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

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

Апробация работы. Основные результаты диссертации опубликованы в работах [20, 42, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 73, 74, 75, 76], из них три статьи [20, 42, 54] опубликованы в журналах, рекомендованных ВАК РФ. Также результаты работы докладывались на ежегодных школах-семинарах молодых ученых "Математическое моделирование и информационные технологии" (Иркутск–Ангасолка, 2005–2007, 2010); XIII, XIV Байкальских международных школах-семинарах "Методы оптимизации и их приложения" (Иркутск-Северобайкальск, 2005, 2008); Всероссийской конференции "Математика, информатика, управление" (Иркутск, 2005); ежегодных конференциях "Ляпуновские чтения и презентация информационных технологий" в ИДСТУ СО РАН (Иркутск, 2006, 2008, 2009); II Всероссийской конференции с международным участием "Инфокоммуникационные и вычислительные технологии и системы"(Улан-Удэ–Байкал, 2006); III, IV Всероссийских конференциях "Проблемы оптимизации и экономические приложения" (Омск, 2006, 2009); II Международной конференции по оптимизации и оптимальному управлению (Монголия, Улан-Батор, 2007); Российской конференции "Дискретная оптимизация и исследование операций" (Владивосток, 2007).

Результаты работы обсуждались на семинарах отделения Системного анализа и оптимизации ИДСТУ СО РАН, объединенном семинаре ИДСТУ СО РАН, семинаре факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова.

Глава Оптимизационный подход к решению линейной задачи дополнительности В данной главе рассматривается известная линейная задача дополнительности (ЛЗД) со знаконеопределенными матрицами. Производится редукция поставленной задачи к невыпуклой задаче математического программирования. Для решения последней используется стратегия глобального поиска, основанная на условиях глобальной оптимальности [69, 70], одним из ключевых моментов которой является специальный метод локального поиска [69]. Для задачи линейной дополнительности конкретизированы и реализованы основные этапы стратегии глобального поиска (построение аппроксимации поверхности уровня, выбор параметров счета, и т.д.). На этой основе разработан алгоритм глобального поиска решения ЛЗД. Проведено тестирование разработанного алгоритма на достаточно широком спектре случайно сгенерированных задач и дан подробный анализ вычислительного эксперимента.

1.1 Постановка задачи. Различные формулировки линейной задачи дополнительности Рассматривается линейная задача дополнительности [88], состоящая в нахождении пары векторов (x, w), удовлетворяющих следующим условиям:

где x, w I n. Вектор q I n и вещественная знаконеопределенная (n n)-матрица M считаются заданными.

Несложно видеть, что задачу (LCP)–(1.1.1) можно записать в следующем равносильном виде:

Исторически ЛЗД можно рассматривать в качестве объединяющей формулировки для задач линейного, квадратичного программирования и биматричных игр [100]. Различным способам формулировки ЛЗД соответствуют разные подходы к ее решению, упомянутые во введении. Рассмотрим, как связана задача (LCP)–(1.1.1) с некоторыми задачами математического программирования.

1. Задачи линейного программирования.

где x I n, y I m, A (m n)-матрица, можно переписать в виде При этом, согласно теории двойственности в ЛП [10], решение задач (1.1.3) сводится к поиску x, y, удовлетворяющих (1.1.4), таких, что Далее, введем новые обозначения:

Тогда, переписав (1.1.4)–(1.1.5) в новых обозначениях, получаем в точности задачу (LCP)– (1.1.1).

2. Квадратичные задачи.

Нетрудно видеть, что (LCP)–(1.1.1) выражает необходимые условия оптимальности для квадратичной задачи Действительно, если z локальный минимум задачи (1.1.7), то при выполнении условий регулярности найдется такой ненулевой вектор, что для пары (z, ) будут выполнены условия Каруша-Куна-Таккера:

что может быть в точности записано как ЛЗД (LCP)–(1.1.1).

Однако решать задачу (1.1.7) вместо (LCP)–(1.1.1) не представляется возможным, поскольку в случае знаконеопределенности матрицы M функция f (x) из (1.1.7) может оказаться неограниченной снизу.

В этом случае предпочтительнее рассматривать следующую задачу:

Нетрудно видеть, что в задаче (1.1.8) целевая функция всегда ограничена снизу нулевым значением. Если некоторый вектор является решением задачи (LCP)–(1.1.1), то он обращает в нуль функцию F (·), а следовательно, является решением задачи (1.1.8). Обратно, если z глобальный минимум задачи (1.1.8), то в случае, когда F (z) = 0, вектор z является также и решением (LCP)–(1.1.1). Если же F (z) > 0, то соответствующая ЛЗД не имеет решения. Таким образом, задача (LCP)–(1.1.1) может быть сведена к задаче (1.1.8).

Рассмотрим теперь произвольную квадратичную задачу:

симметричная (n n)-матрица, A I mn, и покажем ее связь с ЛЗД.

По теореме Каруша-Куна-Таккера [9] найдутся такие ненулевые векторы y I m и u I n, что выполнены следующие условия:

Выразим, учитывая вид функции f (x), из первого равенства вектор u:

Несложно видеть, что, в силу неотрицательности векторов, входящих в скалярные произведения и равенства (1.1.11), систему (1.1.10) можно переписать в следующем виде:

т.е. получаем линейную задачу дополнительности, в которой В случае же, когда условия положительной определенности матрицы Q не выполнены, на решении данной ЛЗД выполняются лишь необходимые условия оптимальности в задаче (1.1.9).

3. Биматричные игры.

Рассмотрим биматричную игру (A, B). Без ограничения общности можем считать, что все элементы матриц A и B положительны: aij > 0, bij > 0, i = 1,..m, j = 1,..., n.

Пусть (x, y ) Sm Sn ситуация равновесия по Нэшу в биматричной игре (A, B).

Тогда выполнены условия оптимальности [78]:

и соотношения дополняющей нежесткости:

Для того, чтобы найти ситуацию равновесия по Нэшу в биматричной игре, необходимо и достаточно отыскать пары (x, ) и (y, ), удовлетворяющие условиям (1.1.12) и (1.1.13).

Преобразуем систему (1.1.12). Введем вспомогательные переменные u I m, u 0 и v I n, v 0. Тогда можно записать:

С учетом соотношений дополняющей нежесткости 1.1.13 на вспомогательные переменные u и v нужно наложить дополнительные условия Далее, поскольку все элементы матриц A и B положительны, а компоненты равновесных стратегий x и y неотрицательны, из (1.1.12) получаем, что > 0 и > 0.

новые переменные:

В новых переменных система (1.1.14), (1.1.15) запишется следующим образом:

В результате получаем классическую форму линейной задачи дополнительности (LCP)– (1.1.1), где c дополнительными условиями (1.1.17).

4. Вариационные неравенства.

Рассмотрим вариационное неравенство, заключающееся в нахождении такого вектора x K, что Вектор x является решением вариационного неравенства тогда и только тогда, когда доставляет решение задаче линейного программирования Тогда из теории двойственности в линейном программировании следует, что найдется вектор u, являющийся решением двойственной задачи При этом пара (x, y ) удовлетворяют следующим условиям:

В случае, когда f (x) = Cx + d аффинное отображение, (1.1.21) представляет собой линейную задачу дополнительности:

5. Кусочно-линейные функции Для решения линейной задачи дополнительности часто используется ее формулировка в виде минимизации кусочно-линейной функции [100]:

Задача (1.1.22) представляет собой задачу негладкой вогнутой минимизации.

Аналогично можно записать ЛЗД в виде системы уравнений:

где операция min(a, b) означает взятие минимума двух векторов покомпонентно.

1.2 Редукция к задаче d.c. минимизации Как упоминалось в §1.1, задача (1.1.1) может быть сформулирована как задача математического программирования [131]:

Для случая выпуклой задачи (1.2.1) (неотрицательной определенности матрицы M ) разработано большое количество методов выпуклой оптимизации [3, 9, 81, 126]. Ситуация меняется принципиальным образом, если M знаконеопределенная, поскольку в этом случае прямое применение известных методов выпуклой оптимизации к задаче (1.2.1), как известно [9, 31, 34, 36], вообще говоря, не приводит, глобальному решению, а чаще всего лишь к стационару.

С развитием методов выпуклой оптимизации [57, 59, 60, 126], вычислительных технологий и созданием многочисленных решателей линейных и выпуклых квадратичных задач (например, известные пакеты прикладных программ CPLEX [141], Xpress-MP [140] и т.д.) решение выпуклых задач даже повышенной размерности не представляет, как правило, больших проблем. Вопрос в этом случае состоит не столько в нахождении самого решения, сколько в скорости работы того или иного алгоритма. Иначе дело обстоит с невыпуклыми задачами, поскольку, как будет показано ниже, готовые пакеты прикладных программ, основанные на методах выпуклой оптимизации, как правило, с ними не справляются.

В работе рассматривается задача (1.2.1) именно со знаконеопределенной матрицей M, т.е. задача с невыпуклой целевой функцией. Как было показано во введении, для невыпуклой задачи (1.2.1) может быть применен алгоритм глобального поиска (АГП) [69, 70], основанный на условиях глобальной оптимальности для задачи с целевой функцией, представимой в виде разности двух выпуклых функций, т.е. d.c. функции.

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

Как известно, знаконеопределенная матрица M может быть представлена в виде разности двух положительно определенных матриц:

Существуют различные схемы получения такого разложения. Ниже представлен один довольно простой прием [69] конструирования матриц M1, M2.

Известно, что матрица с неотрицательными элементами и строго доминирующей диагональю является положительно определенной [82]. Именно в таком виде и будем искать матрицы M1 и M2 на основе заданной матрицы M = {mij }.

Прежде всего представим матрицу в виде разности матриц с неотрицательными компонентами: M = D1 D2, D1 = {dij }, D2 = {dij }, где диагональной матрицы 1 = {ij } вычисляются по формулам Здесь Si dij сумма внедиагональных элементов i-ой строки матрицы D1, > некоторое фиксированное число. Заметим, что элементы обеих матриц F1 и F2 остаются при этом неотрицательными, а матрица F1 оказывается положительно определенной.

Аналогичным образом построим положительно определенные матрицы M1 и M2 :

где Ti = fij сумма внедиагональных элементов i-ой строки матрицы F2. Нетрудно проверить, что M = M1 M2.

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

С использованием вышеприведенного метода декомпозиции получаем следующее d.c.

представление целевой функции в задаче (1.2.1):

где являются сильно выпуклыми функциями. Следовательно, возникает следующая задача d.c. минимизации:

где допустимое множество S, определенно следующим образом:

Далее, для решения задачи (1.2.3) будем применять алгоритм глобального поиска [69, 70], основными этапами которого являются локальный поиск и процедура выхода из критической точки, полученной на этапе локального поиска.

Замечание 1.2.1 Для сведения ЛЗД к задаче минимизации вместо формулировки (1.2.1) можно использовать (1.1.22). В этом случае необходимо искать минимум негладкой вогнутой функции. Отметим, что эффективность алгоритма глобального поиска напрямую зависит от эффективности решения вспомогательных задач. Поэтому в данной работе был выбран первый подход, поскольку он дает возможность применения для решения выпуклых гладких подзадач современных решателей (см. [140], [141]).

1.3 Специальный метод локального поиска Локальный поиск является одним из основных модулей алгоритмов решения невыпуклых задач, основанных на теории глобального поиска [18, 44, 69, 78, 71]. Целью локального поиска обычно является отыскание критических (стационарных) точек в рассматриваемой невыпуклой задаче. При этом понятие критической точки зависит от структуры конкретной задачи и соответствующего локального метода.

Поскольку, как было показано в §1.2, задача (1.2.3) является задачей d.c. минимизации, то для ее решения будем применять специальный метод локального поиска (СМЛП), заключающийся в решении последовательности выпуклых частично линеаризованных задач. Приведем описание этого метода.

Пусть задано некоторое начальное приближение x0 S. Далее, если известна допустимая точка xs S, то следующее приближение xs+1 будем искать как приближенное решение линеаризованной в точке xs задачи Более точно это означает, что точка xs+1 удовлетворяет неравенству где последовательность s такова, что Отметим, что задача (1.3.1) оказывается уже выпуклой и поэтому может быть решена посредством современных пакетов и библиотек программ методов выпуклой оптимизации. Для численного решения этой задачи в работе применялся известный решатель Xpress-MP [140], предназначенный, в частности, для решения выпуклых квадратичных задач и задач линейного программирования.

В силу ограниченности снизу целевой функции F на допустимом множестве S и непрерывной дифференцируемости функции H(x) = M2 x, x, справедлива следующая теорема сходимости данного алгоритма.

Теорема 1.3.1 [69] i) Последовательность {xs }, генерируемая по правилу (1.3.2) удовлетворяет условию ii) При этом последовательность {xs } сходится, кроме того ее предел x является решением следующей линеаризованной задачи:

iii) Кроме того, из (1.3.5) следует классическое условие стационарности Доказательство. Из (1.3.2) в силу сильной выпуклости H(·) вытекает где µ константа сильной выпуклости функции H(·). Таким образом, получена числовая последовательность {F (xs )}, для которой F (xs+1 ) F (xs ) + s, т.е. почти монотонно убывающая последовательность. Поэтому в силу ограниченности снизу функции F (·) на D, а также с учетом (1.3.3), существует конечный предел lim F (xs ) = F. Поэтому из цепочки (1.3.7) следует справедливость условия (1.3.4).

Далее, из (1.3.7) получаем Переходя к пределу при s получаем существование предела lim xs = x. Тогда в силу непрерывности G(·) и H(·) из (1.3.4) получаем Введем определение.

щуюся решением линеаризованной задачи:

т.е. линеаризация происходит в самой этой точке z.

ii) Приближенно критической называется точка z, являющаяся -решением задачи В качестве критерия останова для метода локального поиска можно использовать одно из следующих неравенств [69]:

где > 0 заданная точность.

Нетрудно показать, что если выполнен один из критериев останова (1.3.9) или (1.3.10), то в этом случае точка, в которой произошел останов, является -критической в задаче (1.2.3). Действительно, из (1.3.7) следует Следовательно, если s, то точка xs является -решением задачи (PLs ).

Похожая технология нахождения критических точек в задачах d.c. минимизации предложена в публикациях [117, 118]. Однако разработанный в указанных работах метод предназначен для задач безусловной минимизации.

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

1.4 Построение тестовых примеров и апробация алгоритма локального поиска В литературе можно встретить достаточно много практических примеров линейных задач о дополнительности (см. введение), а также тестовых задач [88, 123, 131] для проверки работы алгоритмов. К сожалению, большинство из них оказываются либо выпуклыми, с неотрицательно определенной матрицей M и поэтому решабельными посредством существующих пакетов прикладных программ (например, пакетами для решения выпуклых квадратичных задач [140] или специализированных пакетов для ЛЗД [142]), либо имеют небольшую размерность, что позволяет эффективно использовать методы перебора крайних точек допустимого множества [100].

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

Элементы матрицы M случайно выбирались из отрезка [n, n], где n размерность задачи. Далее задавалось решение задачи для каждого i = 1,..., n, удовлетворяющее одному из условий:

Затем из соотношений (1.4.1) вычислялись компоненты вектора q. Выбор варианта 1) или 2) для i-й компоненты происходил случайным образом. Для сгенерированных задач размерностей от 2 до 100 выбиралось 3 различные стартовые точки, что, позволило, с одной стороны, рассмотреть поведение метода в различных начальных условиях, а с другой найти подходящие (не сразу приводящие к глобальному решению) начальные точки для дальнейшего тестирования глобального поиска.

Отметим, что в силу теоремы 1.3.1, линеаризованные задачи в методе локального поиска можно решать на его начальных шагах с достаточно низкой точностью, постепенно увеличивая затем точность решения линеаризованных задач s. Поэтому точность решения линеаризованных задач выбиралась следующим образом: 0 = 0.1, s+1 = 0.5s, s = 0, 1,....

Все программы, реализующие алгоритмы, представленные в данной главе, были написаны в системе Visual C++, счет производился на компьютере Pentium 4, 3.00 Ghz с 1 Gb оперативной памяти. Выпуклые вспомогательные линеаризованные задачи решались с помощью решателя Xpress-MP [140] барьерным методом Ньютона.

В табл. 1.1, представленной ниже, использовались следующие обозначения: n размерность задачи; Nx0 номер стартовой точки; F0 начальное значение целевой функции; Floc полученное локальным поиском значение функции; P L количество решенных линеаризованных задач; Tloc время счета (в секундах).

Напомним, что точка глобального решения задачи (1.2.3) обращает целевую функцию в ноль, поэтому 0 в колонке Floc означает, что найдено глобальное решение с точностью 104.

Для сравнения в каждой задаче вначале была предпринята попытка нахождения глобального минимума задачи (1.2.1) с помощью прямого применения решателя Xpress-MP к задаче (1.2.3). В колонке FX приведены полученные в этом случае значения целевой функции или прочерки при невозможности решить задачу указанным пакетом программ.

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

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

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

При увеличении размерности, картина качественно меняется. Так для размерностей 6 и 10 со всех начальных точек алгоритм попадает в точки, близкие к решению, но тем не менее не являющиеся глобальным экстремумом, а на размерностях, равных 8, 15 и 25, глобальное решение удается найти только из одного начального приближения, что еще раз подчеркивает сложность решения невыпуклых задач.

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

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

Следует также отметить, что с помощью метода локального поиска, предназначенного, по сути, только для нахождения критических точек, во многих случаях (например, на размерностях 2, 4, 8, 15, 25) удалось получить решение задачи. При этом СМЛП уступил решателю Xpress-MP только в задачах с шестью и десятью переменными. Во всех остальных случаях прямое применение пакета программ Xpress-MP оказалось неэффективным, что говорит о трудности и невыпуклости сгенерированных задач. В то же время специальный метод локального поиска позволил найти критические точки со значительно меньшим, по сравнению с исходным, значением функции, для всех размерностей, что говорит о возможности его применения в алгоритме глобального поиска.

1.5 Алгоритм глобального поиска В результате численного тестирования специального метода локального поиска, проведенного в предыдущем параграфе, было установлено, что локальный поиск, вообще говоря, не обеспечивает достижения глобального решения, даже в задачах небольших размерностей. Поэтому далее предлагается рассмотреть для решения ЛЗД алгоритм глобального поиска (АГП) [69], который фактически состоит из двух основных этапов: a) локального поиска и б) процедуры выхода из полученной локальным поиском критической точки.

Теоретической основой АГП являются следующие условия глобальной оптимальности.

Теорема 1.5.1 [69, 70] Если допустимая точка z S является глобальным решением задачи (1.2.1), то Если, кроме того, выполнено условие то условия (1.5.1) становятся и достаточными для того, чтобы допустимая точка z Используя d.c. разложение целевой функции F из §1.2, в соответствии с теорией глобального поиска [69], можно декомпозировать задачу (1.2.1) на несколько более простых задач.

Пусть известна некоторая приближенно критическая точка zk, полученная методом локального поиска, со значением целевой функции F (zk ) := k. Тогда производится следующая цепочка операций [69, 70].

M1 x, x + q, x и строится некоторая аппроксимация Вопрос построения аппроксимации является ключевым в реализации АГП и, вообще говоря, зависит от вида целевой функции и допустимого множества задачи. Ниже будут рассмотрены несколько способов построения аппроксимации поверхности уровня в задаче (1.2.1).

2) Для всех точек v i аппроксимации Rk проверяется неравенство следующее из условий глобальной оптимальности для задач d.c. программирования [69].

Если неравенство (1.5.3) выполнено, то точка аппроксимации будет использоваться дальше. Если же (1.5.3) нарушено, то согласно теории точка v i является бесперспективной с точки зрения улучшения с ее помощью текущей критической точки.

3) Исходя из точек v i ( M2 v i, v i = k ) аппроксимации (которые не обязательно выбирать допустимыми, что удобно при проведении вычислительного эксперимента), осуществляется локальный поиск, доставляющий приближенно критические точки ui, 4) Далее, значение целевой функции в каждой точке ui сравнивается со значением целевой функции в текущей критической точке z k. Если в какой-либо полученной точке значение целевой функции лучше, чем в текущей, происходит обновление последней, и весь процесс повторяется.

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

Пусть заданы начальная точка x0 S, и +, числовые последовательности {k } и Шаг 1. Начиная с xk S, посредством специального метода локального поиска построить k -критическую точку z k, положить k := F (z k ).

решение задачи.

Шаг 3. Построить точку v i аппроксимации поверхности уровня функции H Шаг 4. Если G(v i ) > +, то положить i := i+1 и перейти на шаг 3. Иначе перейти на шаг 5.

Шаг 5. Начиная с точки v i, построить специальным методом локального поиска k критическую точку ui S.

Шаг 6. Если F (ui ) <, то Stop. ui приближенное решение задачи.

Шаг 7. Если F (ui ) k, i < N, то положить i := i + 1 и вернуться на шаг 3.

на шаг 3.

Шаг 9. Если F (ui ) < k то положить z k+1 := ui, k := k + 1, i := 1, := и перейти на шаг 2.

решение задачи.

Замечание 1.5.1 1. Поскольку в рассматриваемой задаче в точке глобального решения значение целевой функции равно 0, в АГП вводятся дополнительные критерии останова (на шагах 2, 6), которые отсутствует в АГП для произвольной d.c. функции. Это позволяет, в случае получения решения, прекратить перебор по и точкам аппроксимации, а значит, сократить время работы алгоритма.

2. Параметр m отвечает за разбиение отрезка одномерного поиска по на различное количество частей. С помощью параметра можно изменять точность выполнения неравенства (1.5.3), вытекающего из условий глобальной оптимальности для задач d.c.

программирования, (с целью уменьшить влияние машинных ошибок округления) [44, 78]. Управляя этими двумя параметрами, можно изменять время работы алгоритма.

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

3. Заметим, что в качестве можно выбрать 0, так как G(x) = M2 x, x x S. Поскольку выпуклая квадратичная функция G(x) оказывается неограниченной сверху на множестве S, то верхняя граница + вводится искусственно.

1.6 Вычислительный эксперимент Вычислительный эксперимент по тестированию алгоритма глобального поиска в задаче (1.2.1) проходил в несколько этапов.

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

1.6.1 Выбор аппроксимации поверхности уровня При численном решении, с учетом опыта ранее решенных задач [18, 19, 44, 69, 80], использовались три аппроксимации.

Первый набор точек аппроксимации наиболее часто используется при решении невыпуклых задач в силу простоты вычисления и имеет следующий вид [18, 19, 69]:

где ei = (0,..., 1,..., 0) вектор из стандартного базиса, µi число, которое находится из уравнения Поскольку H в рассматриваемой задаче является квадратичной и сильно выпуклой, то уравнение (1.6.1) разрешается аналитически:

Достоинством такого набора является простота построения векторов y i.

Одним из способов изменения точек аппроксимации в зависимости от итерации является добавление текущей критической точки z k в определение y i [18, 44, 80]:

где µi также находится аналитически из квадратного уравнения H(z k ± µi ei ) =.

Далее, учитывая структуру задачи в исходной постановке, а именно, тот факт, что глобальное решение обязательно достигается в вершине допустимого множества S, точками третьей аппроксимации R3 были выбраны векторы где в качестве di для i = 1,..., n использовались решения следующих задач линейного а dn+1 находилось как решение аналогичной задачи где en вектор, состоящий из единиц, en = (1, 1,..., 1, 1).

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

Для проведения первого этапа вычислительного эксперимента были выбраны следующие параметры алгоритма. Точность работы локального поиска k выбиралась равной 5·105 на каждой итерации, точность глобального поиска (по значению целевой функции) = 104 (в соответствии с теоремой сходимости АГП [69], [70], условия на согласование точностей имеют вид 2k ). Параметр, участвующий в проверке условия на шаге брался равным 104. Для вычисления шага по отрезок [, + ] делился на 10 частей (m = 10), а в случае, если решение не было найдено, происходило разбиение отрезка на 50 частей. В качестве стартовой выбиралась та из трех точек, участвовавших в тестировании специального метода локального поиска, начиная с которой было получено наихудшее значение целевой функции.

Ниже в табл. 1.2 представлены результаты сравнения работы АГП с применением трех описанных аппроксимаций.

Здесь St количество итераций алгоритма, или, что то же самое, число пройденных критических точек; Fglob полученное значение целевой функции. Время T приводится в минутах, секундах и долях секунд.

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

Однако на размерностях 8, 20 и 30 аппроксимация R2 выигрывает по числу решенных линеаризованных задач, а следовательно, и по времени счета. Третья аппроксимация в этом случае выглядит предпочтительнее первой, за исключением примера размерности 15, где пришлось решить достаточно много линеаризованных задач.

Начиная с размерности 40, вторая аппроксимация теряет свои преимущества: число линеаризованных задач увеличивается слишком быстро, а в задачах, где n > 60 глобальное решение получить не удается. В данном случае использование дополнительной информации (текущей точки z k ) не дает преимуществ.

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

Это можно видеть на размерностях 70 и 90. Единственным случаем, когда третий набор точек оказывается хуже, является пример с n = 80.

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

На графике (рис. 1.6.1) приведены сравнительные данные о количестве решенных линеаризованных задач с использованием первой и третьей аппроксимаций на всех размерностях от 6 до 50.

Несмотря на несколько примеров, в которых аппроксимация R1 требует решения меньшего числа линеаризованных задач, третья аппроксимация выглядит более выигрышной. Заметим к тому же, что суммарное число решенных линеаризованных задач на всех размерностях при использовании третьей аппроксимации составило 9947 против 17865 с применением первой аппроксимации.

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

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

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

Как и следовало ожидать, при переменной точности (уменьшающемся k ) во всех примерах было решено меньшее число линеаризованных задач. Следствием этого стало увеличение числа найденных критических точек в задачах размерности 8, 25, 40, 50 и 80. В остальных случаях с уменьшением числа линеаризованных задач, число итераций метода не увеличилось. Возможно, это объясняется наличием в алгоритме глобального поиска на шагах 2 и 6 дополнительных критериев останова по значению функции, в связи с чем не возникает необходимости каждый раз уменьшать точность локального поиска k до необходимого значения k.

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

Таблица 1.3: Изменение точности локального поиска 1.6.3 Решение серий задач Для выявления общих свойств метода далее были рассмотрены серии задач, генерация которых происходила ранее описанным образом. Одновременно была увеличена размерность рассматриваемых задач.

Для сравнения эффективности алгоритма глобального поиска, те же серии задач были предложены для решения известной процедуре quadprog (Matlab 6.5 [143]), реализующей метод активных множеств для задач квадратичного программирования [126], и решателю PATH [142], специально предназначенному для решения линейных задач дополнительности. Отметим, что с помощью quadprog решались задачи математического программирования (1.2.1), а решателю PATH предлагались ЛЗД в исходной постановке (LCP)–(1.1.1).

Ниже в табл. 1.4 производится сравнение численной эффективности известных пакетов прикладных программ и программного комплекса, разработанного в диссертации.

В табл. 1.4 использовались следующие обозначения: N число протестированных задач соответствующей размерности, LocSol число задач, решенных только специальным методом локального поиска, без использования процедур глобального поиска, LP и St среднее количество решенных линеаризованных задач и пройденных критических точек соответственно, потребовавшихся для нахождения глобального решения в одной задаче из серии, T среднее время решения одной задачи алгоритмом глобального поиска.

Для сравнения в колонках с названиями Quadprog и P AT H приведено число задач из серии, в которых получено глобальное решение с помощью решателей quadprog и PATH соответственно.

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

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

Что касается результатов работы quadprog и PATH, то данные решатели оказываются эффективны на небольших размерностях. Однако с ростом числа переменных, увеличивается число нерешенных (глобально) задач. Для решателя PATH резкий скачок уменьшения количества решенных задач происходит при переходе к размерности 40, для quadprog после размерности 50. Отметим еще раз, что алгоритм глобального поиска справился со всеми предложенными задачами, т.е. нашел в них глобальное решение.

На рис. 1.6.3 представлены графики, показывающие характер изменения среднего числа решенных линеаризованных задач (P L), найденных критических точек (St) и среднего времени (T ) решения одной задачи с увеличением размерности. Поскольку показатели средних величин могут отражать реальное поведение алгоритма только при большом числе решенных задач, для графиков использовались данные из таблицы до размерности 60. Как можно видеть из рисунка, наибольшей скоростью роста обладает кривая времени. Рост числа линеаризованных задач имеет почти линейную скорость. Число итераций алгоритма возрастает незначительно, о чем уже говорилось выше. Итак, можно сказать, что в ходе численного эксперимента представленный выше алгоритм глобального поиска показал высокую эффективность на (невыпуклых) задачах ЛЗД со знаконеопределенной матрицей M вплоть до размерности n = 400, обойдя по количеству решенных глобально задач решатели PATH и quadprog.

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

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

Для решения данной задачи можно избрать две стратеги [100, 127]: работать напрямую с нелинейным ограничением-равенством [122, 123] или решать оптимизационную задачу [117, 131]. В диссертации был выбран второй путь. В данной главе была разработана методика решения линейных задач дополнительности со знаконеопределенными матрицами, основанная на теории глобального поиска из [69, 70] для d.c. целевой функции. Разработаны новые алгоритмы локального и глобального поиска для данной задачи. Результаты тестирования демонстрируют эффективность предложенного подхода на достаточно широком поле невыпуклых задач высокой размерности.

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

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

2.1 Постановка линейной двухуровневой задачи Рассмотрим двухуровневую задачу с линейными целевыми функциями на верхнем и нижнем уровнях [11, 89, 90, 92, 96, 98, 103, 114, 132, 136, 138]. Предположим, что из всех возможных решений на нижнем уровне выбирается то, которое благоприятствует достижению цели верхнего уровня. Такая постановка двухуровневой задачи носит название оптимистической [90, 103] и может быть записана, например, следующим образом:

размера (p m), (q m), (q n) соответственно.

(BP)–(2.1.1).

(H1) : Функция f (x, y) ограничена снизу на непустом множестве (H2) : Функция d1, y ограничена снизу на множестве Y (x) для всех x X, так что Несмотря на внешнюю простоту, разработка эффективных численных методов решения линейных двухуровневых задач большой размерности является весьма сложной проблемой. Этот факт объясняется, в частности, тем, что иерархическая структура задачи порождает так называемую скрытую невыпуклость. Следующий пример иллюстрирует неявную невыпуклость линейных двухуровневых задач.

Пример 2.1.1 [103] Рассмотрим линейную двухуровневую задачу со скалярными переменными на верхнем и нижнем уровнях соответственно:

На рис. 2.1 представлена графическая иллюстрация этой задачи. Множество М определяет совокупность пар (x, y), удовлетворяющих ограничениям верхнего и нижнего уровня. Минимизируя функцию нижнего уровня на допустимом множестве при каждом фиксированном x, получаем ломаную AED, которая представляет собой допустимое множество задачи верхнего уровня:

Нетрудно видеть, что допустимое множество верхнего уровня оказывается невыпуклым, и целевая функция верхнего уровня f (x, y) на нем принимает следующий вид:

Задача заключается в минимизации кусочно-линейной функци f (x, y(x)) по x. Нетрудно видеть, что глобальное решение этой задачи дает точка D = (6, 2), значение целевой Из представленного примера нетрудно видеть, что даже в самом простом линейном случае двухуровневая задача обладает невыпуклой структурой, а, как известно, разработка эффективных методов решения невыпуклых задач высокой размерности является одной из актуальных проблем современной теории и методов оптимизации [12, 15, 31, 69, 110, 126]. Для решения сформулированной двухуровневой задачи далее предлагается подход, который использует ее сведение к задаче математического программирования с билинейным ограничением-равенством.

2.2 Сведение двухуровневой задачи к задаче с d.c.

В данном параграфе будет показано, каким образом двухуровневая задача (BP)–(2.1.1) может быть сведена к одноуровневой задаче с билинейным ограничениемравенством.

С этой целью для нижнего уровня двухуровневой задачи (BP)–(2.1.1), который представляет собой следующую задачу параметрического линейного программирования:

запишем двойственную задачу [10], считая x X заданным параметром:

Нетрудно проверить [10], что на допустимых векторах x, y, v (т.е. таких, что y Y (x), v V ) выполнено следующее неравенство:

Кроме того, с учетом сделанных предположений (H1) (H2), взаимодвойственные заF(x))–(2.2.1) и (DF(x))–(2.2.2) при фиксированном x X разрешимы, а значит дачи по теореме двойственности [10] найдутся векторы y I n и v I q такие, что тройка (x, y, v) удовлетворяет системе Заменяя в задаче (BP)–(2.1.1) экстремальное ограничение эквивалентной ему системой (2.2.4), получим следующую невыпуклую задачу математического программирования: где Нетрудно видеть, что невыпуклость в задаче (P)–(2.2.5) порождается билинейным ограничением-равенством, более точно, наличием произведения A1 x, v, при этом множество S выпукло. Кроме того, при переходе от задачи (BP)–(2.1.1) к (P)–(2.2.5) увеличивается ее размерность: появляется вектор переменных v I q. Взаимосвязь задач (P)–(2.2.5) и (BP)–(2.1.1) устанавливается следующей теоремой.

Теорема 2.2.1 [90, 103]. Для того, чтобы пара (x, y ) являлась решением двухуровневой задачи (BP)–(2.1.1), необходимо и достаточно существования вектора v такого, чтобы тройка (x, y, v ) была решением задачи (P)–(2.2.5).

Доказательство. Пусть (x, y ) Sol(BP), тогда очевидно найдется вектор v, являющийся решением задачи, двойственной к задаче нижнего уровня (DF(x )) задачи (BP).

При этом тройка (x, y, v ) будет удовлетворять системе (2.2.4), т.е. является допустимой в задаче (P).

Пусть теперь существует тройка (, y, v ) допустимая в задаче (P) такая, что f (, y ) f (, y ) < f (x, y ), что противоречит тому, что (x, y ) Sol(BP). Доказательство доx статочности проводится аналогично.

Таким образом, для отыскания решения в двухуровневой задаче (BP)–(2.1.1) можно решать невыпуклую задачу оптимизации (P)–(2.2.5), а затем использовать ее решение (x, y, v ) для построения решения (x, y ) задачи (BP)–(2.1.1).

Одним из стандартных подходов к решению задач с ограничениями типа равенства является применение метода штрафов [9, 36, 57, 60, 84, 126]. В этом случае невыпуклость задачи (билинейное ограничение-равенство) переходит в целевую функцию и возникает дополнительный штрафной параметр [90, 94, 95, 138]. В частности, существуют программные реализации стратегии глобального поиска для задач минимизации функции, представимой в виде разности двух выпуклых функций (d.c. функции), для решения линейно-квадратичных двухуровневых задач методом штрафов [79, 80].

В работе предлагается решать задачу (P)–(2.2.5) напрямую, с использованием теории глобального поиска для задач с d.c. ограничением [18, 72]. Действительно, билинейное ограничение в задаче (P)–(2.2.5) можно представить в виде разности двух выпуклых функций, например, следующим образом:

где g(x, y, v) = Таким образом, задача (P)–(2.2.5), в которой билинейное равенство представлено в виде (2.2.7), оказывается задачей с d.c. ограничением-равенством (z = (x, y, v)) Для ее решения будем применять теорию глобального поиска [69] в задачах с d.c. ограничением. Теоретическое обоснование подхода к решению задачи с d.c. равенством представлено в следующих параграфах.

2.3 Условия глобальной оптимальности для задачи минимизации с d.c. ограничением-равенством Рассмотрим следующую задачу с d.c. ограничением-равенством в общем виде:

где функция F (x) представима в виде разности двух выпуклых функций g(x) и h(x):

В [67, 72] разработана теория решения задач c d.c. ограничением-неравенством вида Предполагается, что ограничение-неравенство в задаче (DCC)–(2.3.2) активно на ее решении. В противном случае задача (DCC)–(2.3.2) теряет особенность, связанную с невыпуклым ограничением.

Нетрудно показать, что в случае активности ограничения-неравенства значение задачи (DCC)–(2.3.2) совпадает со значением задачи (P0 )–(2.3.1). Более того, справедлива следующая лемма.

Лемма 2.3.1 Если z Sol(DCC) и F (z) = 0, то z Sol(P0 ).

Доказательство. Поскольку допустимое множество задачи (DCC) с ограничением-неравенством содержит допустимое множество задачи (P0 ) : D(P0 ) D(DCC), то V(DCC) V(P 0 ).

Тогда, если z Sol(DCC) и, что важно, F (z) = 0, то f (z) V(P 0 ). Но очевидно, что z является допустимой в (P0 ). Поэтому f (z) = V(P 0 ), что и требовалось доказать.

Далее, нетрудно видеть, что в силу леммы 2.3.1 всякое достаточное условие глобальной оптимальности в задаче (DCC)–(2.3.2) для точки z S, F (z) = 0 окажется достаточным для того, чтобы точка z была и решением задачи (P0 )–(2.3.1).

В частности для задачи (P0 )–(2.3.1) будут справедливы достаточные условия глобальной оптимальности, доказанные для задачи (DCC)–(2.3.2) [67], которые сформулированы ниже.

Теорема 2.3.1 [67] Пусть выполнены следующие условия регулярности:

Если z S, F (z) = 0 и, кроме того, справедливо условие Доказательство теоремы полностью повторяет доказательство теоремы из [67] и поэтому здесь не приводится.

Далее рассмотрим вопрос о необходимых условиях глобальной оптимальности для задачи (P0 )–(2.3.1).

Теорема 2.3.2 Пусть выполнено предположение Тогда, если z Sol(P0 ), то Доказательство. Пусть (E1 )–(2.3.7) нарушено:

Тогда из выпуклости h(·) следует Итак, нашелся элемент u такой, что u S, f (u) f (z), F (u) < 0. Теперь из (H1 )–(2.3.6) вытекает существование ]0, 1[: F (x()) = 0, где x() = u + (1 )v.

При этом, в силу выпуклости S и f (·), имеем: x() S, и, поскольку f (v) < f (z), Таким образом, нашелся допустимый элемент x() S, F (x()) = 0, лучший по значению целевой функции, чем z : f (x()) < f (z). Это противоречит тому, что z Sol(P0 ).

Следовательно, при предположении (H1 )–(2.3.6) условие (E1 )–(2.3.7) оказывается и необходимым для того, чтобы точка z была решением задачи (P0 )–(2.3.1).

Замечание 2.3.1 Отметим, что в случае ограничения-равенства можно предполагать выполнение условия регулярности (H1 )–(2.3.6), не ограничивая общности. Действительно, в случае его невыполнения можно рассмотреть ограничение-равенство в F (x) = 0. Тогда либо условие регулярности будет выполнено для функции виде F (x) F (x) (которая также является d.c. функцией: достаточно лишь поменять местами функции g и h в d.c. разложении), либо получаем, что Последнее означает, что решение задачи (P0 )–(2.3.1) совпадает с решением релаксированной задачи и ограничение F (x) = 0 можно не принимать во внимание. Другими словами, теряется особенность, связанная с ограничением-равенством.

В теории глобального поиска [69] ключевую роль играет функция, задающая (в d.c.

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

В задаче (DCC)–(2.3.2) такой функцией является функция h(·), поскольку при h(x) 0 получаем выпуклую задачу. Для выполнения условия регулярности (H1 )–(2.3.6) в задаче (P0 )–(2.3.1) выбирается ограничение типа равенства в виде g(x)h(x) = 0 или h(x)g(x) = 0. И, соответственно, линеаризация в УГО происходит либо по функции h(·), либо по функции g(·). При этом в задаче с ограничением-равенством говорить о функции, задающей базовую невыпуклость, вообще говоря, нельзя, поскольку обе функции g(·) и h(·) порождают невыпуклость, если не являются аффинными.

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

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

(P0 )–(2.3.1) эквивалентна задаче (DCC)–(2.3.2).

(DCC)–(2.3.2). Тогда ясно, что z S, F (z) 0 и Покажем, что F (z) = 0. Пусть это не так, т.е. F (z) < 0.

Поскольку по условию (H1 )–(2.3.6) F (v) > 0 и функция () := F (x ), где силу выпуклости функции f (·) имеем Таким образом, получили допустимую в (P0 )–(2.3.1) точку x, для которой f (x ) < V(P 0 ), что невозможно. Значит, F (x ) = 0, и тогда z Sol(P0 ).

2. Пусть теперь z Sol(P0 ). Предположим, что z Sol(DCC), так что u S :

Ясно, что в этом случае F (u) < 0, иначе бы u являлась допустимой в (P0 ) и лучшей, чем z, что противоречит предположению. Так же, как и в пункте 1 получаем, что ]0, 1[:

С учетом результата теоремы 2.3.3 понятие базовой невыпуклости в задаче (P0 )–(2.3.1) можно проинтерпретировать следующим образом. Пусть в задаче (P0 )–(2.3.1) выполнены условия регулярности (H1 )–(2.3.6). Предположим, что h(x) 0, тогда получаем следующую задачу: При этом условия регулярности (H1 )–(2.3.6) запишутся следующим образом:

В этом случае из теоремы 2.3.3 вытекает следующий результат.

Следствие 2.3.1 Пусть выполнено (H1 )–(2.3.11). Тогда всякое решение задачи (P 0 )–(2.3.10) является решением задачи Обратно, всякое решение задачи (CP) является решением задачи (P 0 )–(2.3.10). # Таким образом, получаем, что при h(x) 0 решение задачи (P 0 )–(2.3.10) сводится к решению выпуклой задачи (CP). Другими словами, можно считать, что именно функция h(x) задает базовую невыпуклость в задаче (P0 ).

Заметим далее, что, как и для задачи (DCC)–(2.3.2), необходимые условия глобальной оптимальности обладают так называемым алгоритмическим (конструктивным) свойством, которое заключается в следующем: если (E1 )–(2.3.7) нарушено, то существует возможность построить точку лучшую, чем исследуемая.

Действительно, пусть найдется тройка (y,, u) такая, что и на которых неравенство из (E1 )–(2.3.7) нарушено, т.е.

Отсюда, в силу выпуклости функции h(·), немедленно следует что Значит точка u удовлетворяет условиям С другой стороны, в силу условия регулярности (H1 )–(2.3.6) существует выпуклая комбинация точек u и v При этом, в силу выпуклости функции f (·), Иными словами, имеется возможность улучшить значение целевой функции f (·), построив точку, удовлетворяющую всем ограничениям задачи, в том числе F (x) = 0. В третьей главе (см. §3.1) представлен численный метод построения такой точки.

2.4 Минимизирующие последовательности В этом параграфе будет произведено обобщение условий глобальной оптимальности на минимизирующие последовательности в задаче (P0 )–(2.3.1).

Определение 2.4.1 Последовательность {z k } назовем минимизирующей в задаче (P 0 )–(2.3.1), если выполнены три следующих условия:

Множество всех минимизирующих последовательностей в задаче (P 0 )–(2.3.1) будем обозначать через M = M(P0 ).

Теперь введем следующую функцию Поскольку при x = y = z S и = 0 = h(z) тройка (x, y, 0 ) удовлетворяет ограничениям в определении (2.4.4) и, кроме того, то получаем Теорема 2.4.1 Пусть выполнено условие регулярности (H1 )–(2.3.6), а функция f (·) непрерывна на открытом множестве S. Кроме того, пусть множество X = {x S| f (x) V(P0 )} непусто и ограничено.

Тогда для любой последовательности {z k } M(P 0 ) справедливо равенство:

Доказательство. Пусть последовательность {z k } является минимизирующей, но условие (EM )–(2.4.6) нарушено. Тогда с точностью до подпоследовательности можно считать, что По определению функции (·) найдется тройка (xk, y k, k ) такая, что k = 1, 2,...

и при этом Итак, для последовательности {xk } справедливы следующие соотношения:

Поскольку z k M(P 0 ), то lim f (z k ) = V(P0 ). В силу непрерывности функции f (·) мноk жество Лебега функции f (·) замкнуто, а в силу ограниченности множества X = {x S| f (x) V(P0 )}, ограничено [9]. Тогда последовательность {xk } сходится с точностью до подпоследовательности к некоторой предельной точке x S, причем Кроме того, из (2.4.8) получаем, что Теперь для точек x и v из предположения (H1 )–(2.3.6) построим выпуклую комбинацию такую, что F (x ) = 0, ]0, 1[, x S. При этом в силу выпуклости f (·) так что f (x ) < V(P 0 ) в допустимой точке x, что невозможно. Полученное противоречие Утверждение теоремы обратимо при выполнении условий регулярности из теоремы 2.3.1 о достаточных условиях глобальной оптимальности.

Теорема 2.4.2 Пусть в задаче (P0 )–(2.3.1) функция f (·) полунепрерывна сверху на открытом множестве S, и выполнены условия регулярности (2.3.3) и (2.3.4). Пусть для некоторой последовательности {z k } S выполнено условие (EM )–(2.4.6) и имеет место равенство lim F (z k ) = 0. Тогда последовательность {z k } оказывается минимиk Как и в случае с теоремой 2.3.1, доказательство данной теоремы аналогично доказательству соответствующей теоремы для задачи (DCC)–(2.3.2) с ограничением-неравенством и в работе не приводится.

2.5 Стратегия глобального поиска Данная задача совпадает с задачей, возникающей в случае d.c. ограничения-неравенства.

Следовательно, при выполнении дополнительных условий регулярности для нахождения глобального минимума задачи (P0 )–(2.3.1) необходимо выполнить те же шаги, что и для задачи с d.c. ограничением-неравенством [72]. А именно, задачу (2.5.1) предлагается разбить на несколько более простых этапов.

a) Пусть задано число такое, что и точка z, полученная некоторым методом локального поиска. Тогда для поверхности уровня выпуклой функции h(·) построим некоторую конечную аппроксимацию b) Теперь для каждого y i A() решим линеаризованную задачу:

Пусть ui (приближенное) глобальное решение задачи (2.5.3).

c) Затем для каждого i {1,..., N } найдем (приближенное) глобальное решение wi задачи уровня:

d) Далее формируем величину () := + (), где Если () > 0, то в силу выпуклости h(·) и равенства h(wi ) =, имеем Действительно, в качестве точки (, y, v ) может быть взято решение релаксированной заx F (, y, v ) = 0 или f (, y ) = V(P), то задача с равенством не представляет интереса для дальнейшего рассмотрения, поскольку тогда ограничение-равенство не влияет на решение задачи.

Для того, чтобы обеспечить выполнение условия (2.6.4), далее будем рассматривать следующую возмущенную задачу:

где > 0. При этом, чтобы в задаче (P ) условие (H1 )–(2.3.6) также было выполнено, параметр возмущения должен удовлетворять условию Напомним, что функция F (·) представляет собой невязку двойственности в задаче нижнего уровня исходной задачи (BP)–(2.1.1). Поэтому одновременно рассмотрим возмущенную двухуровневую задачу, в которой задача нижнего уровня решается приближенно с точностью :

где Y (x) = {y I n | A1 x + B1 y b1 }. Между задачами (P )–(2.6.6) и (BP )–(2.6.8) установлена следующая взаимосвязь.

Теорема 2.6.1 Пусть тройка (x, y, v ) решение задачи (P )–(2.6.6). Тогда пара (x, y ) является решением двухуровневой задачи (BP )–(2.6.8).

Рассмотрим прямую и двойственные задачи нижнего уровня для (BP )–(2.6.8) при фиксированном x :

В силу теоремы двойственности [10], Тогда из (2.6.9) и (2.6.12) следует откуда получаем, что y -Sol(F(x )). Следовательно, точка (x, y ) допустимая в задаче (BP )–(2.6.8).

Покажем теперь, что (x, y ) решение задачи (BP )–(2.6.8). Пусть это не так и существует допустимая в задаче (BP )–(2.6.8) точка (, y ), в которой значение целевой функции верхнего уровня меньше:

Тогда Пусть v Sol(DF()), y Sol(F()). В этом случае откуда заключаем, что Далее возможны два случая.

a) Если последнее неравенство выполняется как равенство, то сразу приходим к противоречию, поскольку получаем допустимую в задаче (P )–(2.6.6) точку, в которой значение целевой функции меньше, чем f (x, y ) = V(P ).

б) Пусть теперь F (, y, v ) < 0. При достаточно малом, удовлетворяющем (2.6.7), из (2.6.5) следует, что Тогда, в силу выпуклости S, найдется такая выпуклая комбинация (x, y, v ) S, ности функции f (·), а также (2.6.13) и (2.6.15), Таким образом, для отыскания оптимистического решения двухуровневой задачи (BP)–(2.1.1) предлагается вместо задачи (P)–(2.6.1) решать возмущенную задачу (P )–(2.6.6), в которой выполнены условия регулярности. При этом параметр должен выбираться достаточно малым, чтобы выполнялись условия (2.6.15) и точность решения задачи нижнего уровня была приемлемой для рассматриваемой задачи (BP)–(2.1.1).

Pages: |

| 2 |

Главная >> Диссертации - все темы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«Никитина Мария Юрьевна КОНЦЕПТУАЛИЗАЦИЯ МИЛОСЕРДИЯ: ОБЩЕЯЗЫКОВОЙ И ИДИОСТИЛЕВОЙ АСПЕКТЫ (речевые реализации в синхронии и диахронии) Специальность 10.02.01 – русский язык Диссертация на соискание ученой степени кандидата филологического наук Научный руководитель : доктор филологических наук профессор Борисова М. Б....»

«Саутин Максим Евгеньевич ПАТОГЕНЕТИЧЕСКИ НАПРАВЛЕННАЯ ФАРМАКОТЕРАПИЯ ПСОРИАЗА И АТЕРОСКЛЕРОЗА АТОРВАСТАТИНОМ С УЧЕТОМ ОБЩИХ МОЛЕКУЛЯРНЫХ ФАКТОРОВ 14.03.06 - клиническая фармакология Диссертация на соискание ученой степени кандидата медицинских наук НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор медицинских наук, профессор А.Л. Пирузян КОНСУЛЬТАНТ: кандидат...»

«П А С Т У Х О В Александр Гавриилович ИДЕОЛОГИЧЕСКИ МАРКИРОВАННАЯ ЛЕКСИКА В НЕМЕЦКОМ ПОДЪЯЗЫКЕ ФИЛОСОФИИ Специальность 10.02.04 – германские языки ДИССЕРТАЦИЯ на соискание ученой степени кандидата филологических наук Научный руководитель – доктор филологических наук, профессор С.Д.БЕРЕСНЕВ К И Е В – 1996 СОДЕРЖАНИЕ ВВЕДЕНИЕ ГЛАВА 1. ПРИНЦИПЫ СТРАТИФИКАЦИИ ЛЕКСИКИ В СОВРЕМЕННОЙ ЛИНГВИСТИКЕ. ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ...»

«ГУЩИНА Дарья Юрьевна МОДИФИКАЦИЯ ЭЛЬ-НИНЬО В УСЛОВИЯХ МЕНЯЮЩЕГОСЯ КЛИМАТА: МОНИТОРИНГ, ПРИЧИНЫ, УДАЛЕННЫЙ ОТКЛИК 25.00.30 – метеорология, климатология, агрометеорология диссертация на соискание ученой степени доктора географических наук Москва, 2014 2 Содержание ВВедение ГлаВа 1. Эль-ниньо – Южное колебание и Внутрисезонная тропическая изменчиВость: мониторинГ и механизмы формироВания 1.1....»

«КОРОВЧЕНКО ПАВЕЛ ВЛАДИСЛАВОВИЧ РАЗРАБОТКА АЛГОРИТМА ЭКВИВАЛЕНТИРОВАНИЯ СИСТЕМЫ ЭЛЕКТРОСНАБЖЕНИЯ ЭЛЕКТРОТЕХНИЧЕСКОГО КОМПЛЕКСА ПРЕДПРИЯТИЯ С НЕЛИНЕЙНОЙ НАГРУЗКОЙ Специальность 05.09.03 – Электротехнические комплексы и системы ДИССЕРТАЦИЯ на соискание ученой степени...»

«СТАРКОВСКИЙ Борис Николаевич РАЗРАБОТКА АГРОПРИЕМОВ ПРИ ВОЗДЕЛЫВАНИИ КИПРЕЯ УЗКОЛИСТНОГО НА КОРМОВЫЕ ЦЕЛИ Специальность 06.01.12 — кормопроизводство и луговодство ДИССЕРТАЦИЯ на соискание ученой степени кандидата сельскохозяйственных наук Научный руководитель : кандидат сельскохозяйственных наук, доцент Н.И. Капустин Вологда СОДЕРЖАНИЕ ВВЕДЕНИЕ 1. Роль новых видов кормовых...»

«Джаграева Милена Левоновна Коммуникативно-прагматические особенности фразеологической деривации 10. 02. 19 – Теория языка Диссертация на соискание ученой степени кандидата филологических наук Научный руководитель доктор филологических наук, доцент С.В. Серебрякова Ставрополь 2005 2 Содержание Введение.. 4 Глава 1. Теоретические основы исследования динамических процессов в сфере...»

«Буреломова Анастасия Сергеевна СОЦИАЛЬНО-ПСИХОЛОГИЧЕСКИЕ ОСОБЕННОСТИ ЦЕННОСТЕЙ СОВРЕМЕННЫХ ПОДРОСТКОВ 19.00.05 – Социальная психология (психологические наук и) Диссертация на соискание ученой степени кандидата психологических наук Научный руководитель : доктор психологических наук, профессор, академик РАО Собкин В.С. Москва – 2013 СОДЕРЖАНИЕ ВВЕДЕНИЕ Глава 1. Социально-психологические особенности ценностных...»

«ВЛИЯНИЕ ПСИХОФИЗИЧЕСКОЙ РЕАБИЛИТАЦИИ НА КАЧЕСТВО ЖИЗНИ ПАЦИЕНТОВ ПОЖИЛОГО ВОЗРАСТА, ПЕРЕНЕСШИХ ИНФАРКТ МИОКАРДА 14.01.05 – кардиология Диссертация на соискание учной степени кандидата медицинских наук Научный руководитель : Заслуженный деятель науки РФ, доктор...»

«УДК 632. 954: 631.417 Анисимова Марина Анатольевна ДЕТОКСИЦИРУЮЩАЯ СПОСОБНОСТЬ ПОЧВ И ВЫДЕЛЕННЫХ ИЗ НИХ ГУМИНОВЫХ КИСЛОТ ПО ОТНОШЕНИЮ К ГЕРБИЦИДАМ (Специальность 03.00.27-почвоведение) Диссертация на соискание ученой степени кандидата биологических наук Научные руководители: кандидат биологических наук, доцент Г.Ф. Лебедева кандидат химических наук, старший научный сотрудник И.В. Перминова...»

«ТЕРЕЩЕНКО АЛЕКСАНДР ВЛАДИМИРОВИЧ СОВРЕМЕННАЯ СИСТЕМА ДИАГНОСТИКИ, ЛЕЧЕНИЯ И ОРГАНИЗАЦИИ ВЫСОКОТЕХНОЛОГИЧНОЙ ОФТАЛЬМОЛОГИЧЕСКОЙ ПОМОЩИ ДЕТЯМ С АКТИВНЫМИ СТАДИЯМИ РЕТИНОПАТИИ НЕДОНОШЕННЫХ 14.01.07. – глазные болезни Диссертация на соискание ученой степени доктора медицинских наук Научный...»

«ПЕРЕВОЗЧИКОВА ЕЛЕНА ГЕННАДЬЕВНА ФОРМИРОВАНИЕ ТАРИФОВ НА ПЕРЕВОЗКИ КРУПНОГАБАРИТНЫХ И ТЯЖЕЛОВЕСНЫХ ГРУЗОВ Специальность: 08.00.05 – Экономика и управление народным хозяйством (ценообразование) ДИССЕРТАЦИЯ на соискание учёной степени кандидата экономических наук Научный руководитель : к.э.н., проф. Маховикова Г.А....»

«ГАНЕБНЫЙ СЕРГЕЙ АЛЕКСАНДРОВИЧ АДАПТИВНОЕ УПРАВЛЕНИЕ В ЗАДАЧАХ С НЕИЗВЕСТНЫМ УРОВНЕМ ДИНАМИЧЕСКОЙ ПОМЕХИ 05.13.18 математическое моделирование, численные методы и комплексы программ ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Научный руководитель : кандидат физико-математических наук В.С. Пацко Екатеринбург Оглавление Введение Список обозначений 1 Метод адаптивного...»

«Федосеева Лариса Абрамовна Экспрессия ключевых генов ренин-ангиотензиновой системы у гипертензивных крыс НИСАГ 03.02.07 – генетика ДИССЕРТАЦИЯ на соискание ученой степени кандидата биологических наук Научные руководители: д.б.н., проф. А.Л.Маркель д.б.н., проф. Г.М.Дымшиц Новосибирск 2 ОГЛАВЛЕНИЕ СПИСОК СОКРАЩЕНИЙ..................»

«Каслова Анастасия Александровна Метафорическое моделирование президентских выборов в России и США (2000 г.) 10.02.20 – сравнительно-историческое, типологическое и сопоставительное языкознание Диссертация на соискание ученой степени кандидата филологических наук Научные руководители: Заслуженный деятель науки РФ, доктор филологических наук,...»

«Мухаммед Ариж Абделькаримовна ИССЛЕДОВАНИЕ ГИПОЛИПИДЕМИЧЕСКИХ СВОЙСТВ ВЕЩЕСТВ ПРИРОДНОГО ПРОИСХОЖДЕНИЯ НА ОСНОВЕ ЧЕСНОКА, РАСТИТЕЛЬНЫХ МАСЕЛ И ПИЩЕВЫХ ВОЛОКОН (Экспериментальное исследование) 14.03.06 – фармакология, клиническая фармакология Диссертация на...»

«САЛКИНА Ольга Анатольевна ВАКЦИНОПРОФИЛАКТИКА ПНЕВМОКОККОВОЙ ИНФЕКЦИИ У ДЕТЕЙ ГРУПП РИСКА 14.03.09 – клиническая иммунология, аллергология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : доктор медицинских наук Снегова Надежда Федоровна Москва - 2012 2 ОГЛАВЛЕНИЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.. ВВЕДЕНИЕ.. ГЛАВА 1. ЛИТЕРАТУРНЫЙ ОБЗОР. ПНЕВМОКОККОВАЯ ИНФЕКЦИЯ: ЭТИОЛОГИЯ, ПРОБЛЕМЫ, СОВРЕМЕННЫЕ...»

«ЛАПАТИН ВАДИМ АЛЬБЕРТОВИЧ АБСУРД КАК ФЕНОМЕН В ЕВРОПЕЙСКОМ СОЦИОКУЛЬТУРНОМ ПРОСТРАНСТВЕ XX ВЕКА Специальность: 09.00.13 – философская антропология, философия культуры Диссертация на соискание ученой степени кандидата философских наук Научный руководитель доктор философских наук, доцент Сурова Екатерина Эдуардовна Санкт-Петербург 2014 СОДЕРЖАНИЕ.. ВВЕДЕНИЕ ГЛАВА I. Логическое измерение абсурда.. §1. Две...»

«Дейнега Алексей Вадимович ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ И КОМПЬЮТЕРНЫЙ ДИЗАЙН ОПТИЧЕСКИХ СВОЙСТВ НАНОСТРУКТУРИРОВАННЫХ МАТЕРИАЛОВ Специальность 01.04.05 оптика Диссертация на соискание учной степени е кандидата физико-математических наук Научный руководитель кандидат физико-математических наук доцент Потапкин Б. В. Москва 2010 2 Оглавление Введение 1 Развитие метода решения уравнений Максвелла в конечных разностях 1.1 Обзор литературы...»

«ВОРОНА ЮРИЙ СЕРГЕЕВИЧ ПРИМЕНЕНИЕ МЕМБРАН АУТОПЛАЗМЫ, ОБОГАЩЕННОЙ ТРОМБОЦИТАМИ, С ЦЕЛЬ Ю НАПРАВЛЕННОЙ РЕГЕНЕРАЦИИ ТКАНЕЙ В ОБЛАСТИ ГЛОТОЧНЫХ ШВОВ ПОСЛЕ ОПЕРАЦИЙ НА ГОРТАНИ, ГЛОТКЕ И ПОЛОСТИ РТА (14.01.17 – хирургия) Диссертация на соискание ученой степени кандидата медицинских наук Научный...»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)