Сравнение методов одномерной безусловной оптимизации. Алгоритм пассивного поиска минимума. Анализ методов поиска, основанных на аппроксимации целевой функции. Программная реализация сравнения методов оптимизации. Описание процесса отладки программы.
Аннотация к работе
МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РЕСПУБЛИКИ УЗБЕКИСТАН МЕХАНИКО - МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ для получения академической степени магистра по специальностиВ безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Одним из сравнительных показателей качества метода является количество значений функции, которое нужно вычислить для решения задачи с заданной погрешностью. При решении конкретной задачи оптимизации, прежде всего, выбирается математической метод, который приводил бы к конечным результатом с наименьшими затратами на вычисления или же давал возможность получить наибольший объем информации об искомом решении. Выбор того или иного метода в значительной степени определяется постановкой оптимальной задачи, а также используемой математической моделью объекта оптимизации. Как правило, нельзя рекомендовать какой либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике.Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Разумеется, все эти решения человек принимает без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.Поиск экстремума функций одной переменной имеет самостоятельный интерес, так как является составной частью многих методов многомерной оптимизмации. От правильной организации одномерного поиска существенно зависит успех решения всей задачи. Кроме того, одномерная оптимизация, будучи простой по формулировке задачей, позволяет легко войти в общию проблематику оптимизационных задач [14-16]. Далее, для конкретности, мы будем рассматривать задачи оптимизации на примеры задачи минимизации в силу эквивалентности двух типов оптимизационных задач (максимизации и минимизации).Точки, в которых необходимо провести эксперименты, определяются следующим образом: · Если_ - нечетное, то =а ; =1,2,3,… Среди вычисленных значений {f( =)} (), ищется точка ,в которой достигаются минимум: Найденная точка принимается за приближенное решение задачи = .В алгоритмах активного поиска очередная точка, в которой производится эксперимент, выбирается с учетом информации, полученной в предыдущих опытах. При этом вычисления в точках объедини в блоке, в каждом из которых проводится одновременно n , экспериментов, общее число экспериментов, будет N), т.е. блок-это совокупность из нескольких экспериментов, которые проводятся одновременного (пассивный поиск). Проводим эксперименты в остальных точках блока: находим точку , в которой достигается минимум среди вычисленных значений: следовательно точное значение минимума содержится на отрезке []. Если заданная точностъ достигнута после m итераций, т.е. после экспериментов в m блоках, то длина отрезка неопределенности после всех n вычислений Так как пассивная составляющая алгоритма, т.е. блок, содержит четное число экспериментов, то оптимальный выбор точек в которых необходимо провести эксперименты, будет неравномерным, в отличие от предыдущих алгоритмов, где число экспериментов в блоке было нечетным и. соответственно, расположение точек равномерным.Суть этих методов заключается в том, что по полученной в ходе вычислений информации строится аппроксимирующая функция и ее минимум принимается за точку очередного вычисления. Пусть [a,b] - отрезок неопределенности и - результаты вычислений в точках По этой информации строится аппроксимирующая функция, представляющую из себя кусочно-линейную функцию, состоящую из касательной Полученная аппроксимирующая функция есть ломаная, состоящая из прямой () на [] и () на[ ], где с - точка пересечения касательных (см. рис 2). Пусть имеются три точки, для которых выполняется Так как [отрезок неопределенности и - унимодальная функция, то найти такую точку с нетрудно. Если оказалось, что условимся в качестве точке очередного вычисления выбирать точку Итак, следующее вычисление проводится в точке x=В практических задачах методы оптимизации предназначены для нахождения критериев оптимальности, это оптимальное проектирование - выбор наилучших номинальных технологических режимов, элементов конструкций, структуры технологических цепочек, условий экономической деятельности, повышение доходности и т.д.
План
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. СРАВНЕНИЕ МЕТОДОВ ОДНОМЕРНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ
1.1 Постановка задачи одномерной безусловной оптимизации
1.2 Алгоритм пассивного поиска минимума
1.3 Алгоритм активного поиска минимума
1.4 Методы поиска, основанные на аппроксимации целевой функции
ГЛАВА 2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СРАВНЕНИЯ МЕТОДОВ ОПТИМИЗАЦИИ
2.1 Назначение и анализ использования разработки
2.2 Постановка задачи. Входная и выходная информация