Методы оптимизации. Методы безусловной минимизации функций
 Скачать 377.08 Kb.
|
|
МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра МО ЭВМ ОТЧЕТ по лабораторной работе №1 по дисциплине «Методы оптимизации» Тема: Методы безусловной минимизации функций
Санкт-Петербург 2022 Цели работы: Решение задачи безусловной минимизации функций с помощью стандартной программы. Исследование и объяснение полученных результатов. Постановка задачи. Минимизировать функцию F(x1,x2,a) = (x2 - x12)2 + a(x1 - 1)2 с точностью до 10-5 ( abs ( F(x1k,x2k,a) - F(x1*,x2*,a) ) < 10-5 ) предложенными в задании методами. Оценить скорость и порядок сходимости методов. Провести сравнительный анализ эффективности методов в зависимости от предложенных параметров (начальной точки, величины шага, параметра а>0). Краткие общие сведения  - порядок сходимости метода, где Δk=||xk-x*||ϕ(xk)-ϕ(x*)<const⋅qk – геометрическая скорость сходимости, где q<1 ϕ(xk)-ϕ(x*)<const⋅q2k – квадратичная скорость сходимости, где q<1 Для проведения лабораторной работы составлена программа, обеспечивающая решение задачи безусловной минимизации при задании с терминала исходных значений. Постановка задачи. Описание всех заданных в работе методов минимизации и их характеристик. Задание. 8. Минимизировать функцию F(x1,x2,a) = (x2 - x12)2 + a(x1 - 1)2 с точностью до 10-5 ( abs ( F(x1k,x2k,a) - F(x1*,x2*,a) ) < 10-5 ) градиентными методами - методом с дроблением шага и методом наискорейшего спуска. Оценить скорость и порядок сходимости обоих методов. Провести сравнительный анализ эффективности методов в зависимости от начальной точки и параметра а>0. Выполнение работы. Формальная постановка задачи – описание всех заданных в работе методов минимизации и их характеристик. Итак, будем рассматривать задачу:  (безусловная минимизация),предполагая, что функция ϕ(x) непрерывно дифференцируема на Rn, т.е. ϕ(x)∈C1(Rn). По определению дифференцируемой функции  , (1)где  . Метод с дроблением шага. Ещё один адаптивный способ выбора коэффициентов αk. Выбираются некоторые const β >0 и 0 < λ < 1 (обычно λ = ½). Для коэффициента α = β проверяется выполнение условия  . Если оно выполняется, то полагают αk= α. Если нет, то производится дробление шага, т.е. принимается α = λβ, и т.д. до тех пор, пока не выполнится требуемое неравенство. Процесс дробления не может продолжаться бесконечно, поскольку −ϕ′(x) – направление убывания функции. Первое α, при котором условие выполнено и принимается за αk. Как показывает следующая лемма, с помощью описанного процесса дробления шага можно добиться выполнения неравенства. (1) Лемма 3. Пусть функция ϕ дифференцируема на Rn. Тогда для  найдется такое α0 > 0, что при ∀α∈(0, α0] выполнено условие .Если необходимое неравенство оказывается выполненным при начальном значении α = β, то иногда полезно увеличить шаг, взяв α = μβ, где μ > 1. Так можно продолжать до тех пор, пока значения функции не перестанут уменьшаться. Последнее α, при котором произошло уменьшение, и берется в этом случае за αk. Метод наискорейшего спуска. На луче  , направленном по антиградиенту, введем функцию одной переменной  и определим αk из условий  .Другими словами αk выбирается так, чтобы ϕ(xk+1) в заданном направлении была наименьшей для чего на любом шаге необходимо решать задачу одномерной минимизации функции ψ (α), например, с помощью  .Обоснование выбора перечня вариантов запуска программы (количество начальных точек, начальных шагов, значений параметра а).
Оценим эффективность методов в зависимости от начальной точки и параметра a. Для этого рассмотрим 6 различных начальных точек, которые отличаются расстоянием от x*. Будем работать с тремя различными параметрами a и одним начальным шагом для двух методов. Исследуем зависимость скорости сходимости и порядка сходимости от начальной точки и параметра a.
Выберем следующие параметры a.
Начальный шаг возьмём одним для 2-х методов для всех комбинаций h = 0.03. Результаты решения задачи с помощью готовой программы. Обозначения:  - начальная точка;k* - шаг, на котором достигается заданная точность -  .3.1. Метод с дроблением шага.
|