Исследование и разработка метода и комплекса программ для поиска условного глобального экстремума липшицевой функции на симплексе

• Автор: Спыну, Сергей Константинович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 145 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА I. ИССЛЕДОВАНИЕ МЕТОДА СЕКУЩИХ УГЛОВ ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ И РАЗРАБОТКА ЕГО МОДИФИКАЦИИ

1.1. Метод условной минимизации липшецевых

функций

1.2. Задачи минимизации Липшицевой функции на

симплексе

1.3. Метод секущих углов.

1.4 Вспомогательная задача

1.5 Решение вспомогательной задачи

1.6 Условная задача липшицевого программирования.

1.7 Точная вспомогательная функция
1.8 Метод внешних центров.
1.9 Сходимость метода внешних центров.
Выводы по главе 1
ГЛАВА И. ТЕХНИКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ ПОИСКА
ГЛОБАЛЬНОГО ЭКСТРЕМУМА
2.1. Общая схема работы про1раммного комплекса
2.2. Алгоритм распараллеливания вычислительного
процесса реализованного метода секущих углов.
2.3. Особенности реализации ключевых компонентов
программного комплекса.
Выводы по главе И
ГЛАВА III ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
РАЗРАБОТАННОГО ПРОГРАММНОГО КОМПЛЕКСА И ЕГО ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ В
I
ТЕХНОЛОГИИ МИКРО И НАНОЭЛЕКТРОНИКИ
3.1. Тестирование программного комплекса
3.2. Оптимизация банка данных с виртуальными объектами, описывающими геометрические размеры элементов топологии субмикронного диапазона с использованием разработанного
программного комплекса.
Выводы по главе III
Выводы по работе
Литература


Предложен рекурсивный алгоритм решения вспомогательной задачи метода секущих углов, позволяющий находить все локальные точки минимума. Предложен алгоритм реализации модифицированного метода секущих углов для решения задачи глобальной оптимизации, позволяющий использовать параллельную обработку данных, что приводит к сокращению времени вычислений по сравнению с существующими аналогами. На основе использования полученного программного комплекса проведена оптимизация выбора объектов виртуального банка данных описывающего геометрические размеры элементов топологии ИМС субмикронного диапазона. Практическая ценность работы заключается в созданном программном комплексе позволяющем решать задачи глобальной оптимизации с большой скоростью сходимости и может применяться в различных предметных областях. В работе описано практическое применение построенного алгоритма и комплекса программ при повышении эффективности работы системы измерения геометрических размеров элементов топологии ИМС нанометрового диапазона. Апробация работы. Гагаринские чтения», (Москва, , г. Турция, г. Научной конференции «Современные наукоемкие технологии» (Испания, г. Юбилейной конференции РАЕ «Современные проблемы науки и образования» (Москва, г. ГЛАВА I. Задача условной глобальной оптимизации является одной из наиболее трудных в математическом программировании, поэтому методам ее решения постоянно уделяется много внимания. К настоящему времени разработано большое число различных подходов к решению проблем глобальной оптимизации. Отметим среди них такие методы как методы неравномерного покрытия, метод случайного поиска, различные варианты метода ветвей и границ, метода представления функции в виде выпуклой и вогнутой составляющих, методы основанные на одномерной глобальной оптимизации и многие другие [1]-[9]. В последнее время большую популярность получил предложенный А. М.Рубиновым, М. А.Андрамоновым и Б. Гловсром метод «секущих углов», позволяющий весьма эффективно решать многие сложные задачи выпуклой минимизации, в том числе задачу минимизации возрастающей выпуклой вдоль лучей функции на параллелепипеде, а также задачу минимизации возрастающей положительно однородной функции на симплексе []-[ ]. Метод секущих углов существенным образом использует идеи абстрактного выпуклого анализа (см. В качестве минорант вместо обычных для выпуклого случая линейных функций в методе секущих углов берутся функции специального вида. В близких по идее методах [], [] в качестве минорант применяются вогнутые функции. В настоящей работе рассматривается вариант метода секущих углов предназначенный для решения задачи минимизации липшицевой функции на симплексе при наличии дополнительных линейных ограничений типа неравенства. Метод основан на использовании вспомогательной функции, применяемой в методах внешних центров (методе параметризации целевой функции) (см. Данная вспомогательная функция строится точной, т. Данный метод полностью аналогичен тому, который используется в методе точных штрафных функций []- []. Я++ - его внутренность. Символ 0„ используется для обозначения п-мерного вектора, у которого все компоненты равны 0. Знак неравенства между векторами означает, что данное неравенство выполняется для всех компонент векторов одновременно. Через Б(х) - обозначается диагональная матрица с вектором х на диагонали. Через символ # обозначается конец доказательства. Метод условной минимизации лиишецевых функций. Здесь а=(а а2, . Ь={Ь1, Ь2,. Ьп} - два вектора из Вп. В не пусто, более того, имеет непустую внутренность, т. Ь. Предположим также, что на некоторой области Д содержащей множество В, заданы непрерывные функции /(х) и ? Х = [хеВ:8(х)<0т}. Везде ниже считаем что множество X не пусто. Из ограниченности множества В следует ограниченность X,, поэтому множество X компактно. Непрерывная функция на компактном множестве всегда достигает своего минимума. Точка х. X называется глобальным решением (или просто решением) задачи (1), если /(*,)< /(х) для всех хе X . Наряду с глобальным решением (1) нас будут интересовать локальные решения. X Є X ПД(л*).