Лабораторная работа №1 методы построения целевой функции многокритериальной задачи

1. ЦЕЛЬ РАБОТЫ

Целями работы являются:

• освоение методов построения целевой функции многокритериальной задачи параметрической оптимизации (обобщенного критерия качества);

• ознакомление с особенностями применения методов построения целевой функции.

2. ЛАБОРАТОРНОЕ ЗАДАНИЕ И МЕТОДИЧЕСКИЕ

УКАЗАНИЯ ПО ЕГО ВЫПОЛНЕНИЮ

Сформулировать постановку оптимизационной задачи по теме магистерской диссертации, обосновать выбор метода векторной свёртки критериев, произвести расчёт в соответствии с выбранным методом.

Указания по выполнению

Детальное описание основных методов построения целевой функции многокритериальной задачи приведено в [2]: метод главного критерия, аддитивный метод, мультипликативный метод, метод наихудшего случая и вероятностный метод.

Математическую постановку оптимизационной задачи студент формирует в ходе консультаций с научным руководителем. Для проведения расчётов могут быть использованы математические пакеты, средства САПР, а также оригинальные программные продукты. Защита лабораторной работы проводится в форме научной дискуссии.

Лабораторная работа № 2 методы учёта ограничений в задачах оптимизации

1. ЦЕЛЬ РАБОТЫ

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

2. ЛАБОРАТОРНОЕ ЗАДАНИЕ И МЕТОДИЧЕСКИЕ

УКАЗАНИЯ ПО ЕГО ВЫПОЛНЕНИЮ

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

Указания по выполнению

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

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

Детальное описание основных методов учёта ограничений многокритериальной задачи приведено в [2].

Лабораторная работа № 3 методы поисковой оптимизации

1. ЦЕЛЬ РАБОТЫ

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

2. ЛАБОРАТОРНОЕ ЗАДАНИЕ И МЕТОДИЧЕСКИЕ

УКАЗАНИЯ ПО ЕГО ВЫПОЛНЕНИЮ

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

Указания по выполнению

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

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

Исходными данными в методах поиска являются требуемая точность метода e и начальная точка поиска Х⁰ .

Затем выбирается величина шага поиска h, и по некоторому правилу происходит получение новых точек Х^k+1 по предыдущей точке Х^k при k = 0, 1, 2, … Получение новых точек продолжают до тех пор, пока не будет выполнено условие прекращения поиска. Последняя точка поиска считается решением задачи оптимизации. Все точки поиска составляют траекторию поиска.

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

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

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

1) все соседние точки поиска хуже, чем предыдущая;

2) çФ(X^k+1 )–Ф(X ^k)ç £ e, то есть значения целевой функции Ф(Х) в соседних точках (новой и предыдущей) отличаются друг от друга на величину не больше, чем требуемая точность e;

3) , i = 1, …, n, то есть все частные производные в новой точке поиска практически равны 0, то есть отличаются от 0 на величину, не превышающую точности e.

Алгоритм получения новой точки поиска Х^k+1 по предыдущей точке Х^k свой для каждого из методов поиска, но всякая новая точка поиска должна быть не хуже предыдущей: если задача оптимизации является задачей поиска минимума, то Ф(Х^k+1) £ Ф(Х^k).

Методы поисковой оптимизации принято классифицировать по порядку производной целевой функции, используемой для получения новых точек. Так, в методах поиска нулевого порядка не требуется вычисления производных, а достаточно самой функции Ф(Х). Методы поиска первого порядка используют первые частные производные, а методы второго порядка используют матрицу вторых производных (матрицу Гессе).

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

Эффективность поискового метода определяют по числу итераций и по количеству вычислений целевой функции Ф(Х) на каждой итерации метода.

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

Для методов поиска нулевого порядка справедливо следующее: в методе случайного поиска нельзя заранее предсказать количество вычислений Ф(Х) на одной итерации N, а в методе покоординатного спуска N £ 2×n, где n- количество управляемых параметров X = (x₁, x₂.,…,x_n).

Для методов поиска первого порядка справедливы следующие оценки: в градиентном методе с постоянным шагом N = 2×n; в градиентном методе с дроблением шага N=2× n + n ₁, где n₁ – число вычислений Ф(Х), необходимых для проверки условия дробления шага; в методе наискорейшего спуска N = 2×n + n₂, где n₂ – число вычислений Ф(Х), необходимых для расчета оптимальной величины шага; а в методе Давидона - Флетчера - Пауэлла (ДФП) N = 2× n + n₃, где n₃ – число вычислений Ф(Х), необходимых для расчета матрицы, приближающей матрицу Гессе (для величин n₁, n₂, n₃ справедливо соотношение n₁< n₂ < n₃).

И, наконец, в методе второго порядка - методе Ньютона N = 3×n².

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

На практике широкое применение нашли метод наискорейшего спуска и метод ДФП, как методы с оптимальным соотношением числа итераций и их трудоемкости.