ВОПРОСЫ К ЭКЗАМЕНУ
МЕТОДЫ ОПТИМИЗАЦИИ
Математическая постановка задачи оптимизации.
Понятие о численных методах оптимизации. Прямые методы. Методы
поиска нулевого, первого и второго порядков. Пассивные и активные
(последовательные) методы поиска.
Конечно шаговые и бесконечно шаговые методы поиска. Сходимость
методов. Условия останова методов поиска.
Теорема существования решения оптимизационной задачи.
Необходимые условия экстремума первого и второго порядков
(гладкие функции одной переменной).
Достаточные условия экстремума (гладкие функции одной
переменной).
Необходимые условия экстремума первого порядка (гладкие функции
многих переменных).
Одномерная безусловная оптимизация. Унимодальная функция. Лемма о свойстве унимодальных функций.
Пассивные методы поиска экстремума.
Метод перебора.
Алгоритм оптимального пассивного поиска.
Теорема об оптимальности пассивного поиска.
Последовательные методы поиска экстремума.
Поразрядный поиск.
Метод дихотомии.
Метод деления отрезка пополам.
Метод золотого сечения.
Метод чисел Фибоначчи.
Метод касательных.
Метод средних.
Метод хорд.
Метод Ньютона.
Многомерная безусловная оптимизация. Методы спуска.
Поиск по образцу.
Метод конфигураций.
Метод симплекса.
Метод циклического покоординатного спуска.
Градиент. Градиент и направление роста целевой функции. Градиент и линия уровня.
Градиентные методы.
Градиентный метод с постоянным шагом.
Градиентный метод с дроблением шага.
Метод наискорейшего спуска.
Методы покоординатного спуска.
Метод покоординатного спуска с постоянным шагом.
Метод покоординатного спуска с дроблением шага.
Метод Гаусса-Зейделя.
Постановки задач линейного программирования.
Способы перехода от одной формы задачи ЛП к другой.
Базисное решение задачи ЛП.
Связь базисных решений с угловыми точками (вершинами) множества допустимых решений.
Графический метод решения задачи ЛП.
Симплекс-метод решения задачи ЛП.
Метод искусственных переменных.
Расчетные задания на тестирование
Вычисления Nрасч по заданной точности для методов:
Метод перебора.
Алгоритм оптимального пассивного поиска.
Метод дихотомии.
Метод деления отрезка пополам.
Метод золотого сечения.
Метод чисел Фибоначчи.
Вычисления расчетной точности Ерасч по заданному N для методов:
Метод перебора.
Алгоритм оптимального пассивного поиска.
Метод дихотомии.
Метод деления отрезка пополам.
Метод золотого сечения.
Метод чисел Фибоначчи.
Ответы
1. Математическая постановка задачи оптимизации.
Задача общего вида: f(x)→min/max, x∈A
Если стоит задача минимизировать f(x) при ограничениях:
hk(x)=0, k=1, ..., K,
gj(x) 0 j=1, ..., J,
xi^(u) xi xi^(l), i=1, ..., N
то это называется задачей оптимизации с ограничениями или задачей условной оптимизации. Задача, в которой нет ограничений, т.е.
J=K=0;
xi^(u)= - xi (l) = ∞, i=1, ..., N,
называется оптимизационной задачей без ограничений или задачей безусловной оптимизации.
2. Понятие о численных методах оптимизации. Методы поиска нулевого, первого и второго порядков. Пассивные и активные (последовательные) методы поиска.
Любой численный метод (алгоритм) решения задачи оптимизации основан на точном или приближенном вычислении ее характеристик (значений целевой функции, функций, задающих допустимое множество, а также их производных). На основании полученной информации строится приближение к решению задачи – искомой точке минимума х* или, если такая точка не единственна, – к множеству точек минимума. Иногда, если только это и требуется, строится приближение к минимальному значению целевой функции.
Алгоритмы, использующие лишь информацию о значениях минимизируемой функции, называются алгоритмами нулевого порядка; алгоритмы, использующие также информацию о значениях первых производных, – алгоритмами первого порядка; алгоритмы, использующие, кроме того, информацию о вторых производных, – алгоритмами второго порядка.
Если все точки выбираются одновременно до начала вычислений, то алгоритм минимизации называется пассивным.
Однако для решения большинства задач точки вычисления выбираются поочередно, т. е. точка x(i+1) выбирается, когда уже выбраны точки предыдущих вычислений x1…xi и в каждой из них произведены предусмотренные алгоритмом вычисления, результаты которых будем обозначать соответственно через y1…yi. Такие алгоритмы называются последовательными
3. Конечно шаговые и бесконечно шаговые методы поиска. Сходимость методов. Условия останова методов поиска.
Конечношаговыми (или конечными) называются методы, гарантирующие отыскание решения задачи за конечное число шагов.
Для бесконечно шаговых методов достижение решения гарантируется лишь в пределе.
Важной характеристикой бесконечношаговых методов является сходимость. Метод сходится если x^k -> x^*, при k -> беск., где x^*- решение задачи Условие остановки может определяться имеющимися в наличии вычислительными ресурсами (например, числом вычислений характеристик минимизируемой функции).
На практике часто используют следующие условия остановки:
