Планирование
Содержание:
1. Численные методы безусловной оптимизации первого порядка…………..3
1.1 Минимизация функций многих переменных. Основные положения…..9
1.2 Метод наискорейшего спуска…………………………………….……….10
1.3 Метод сопряженных градиентов…………………………………….……12
2. Аналитическая часть………………………………………………………..16
2.1 Вопросы по теме………………………………………
2.2 Тест …………………………………………………………………
2.3 Примеры задач……………………………………………
1. Численные методы безусловной оптимизации первого порядка
При решении конкретной задачи
оптимизации исследователь
В настоящее время для
решения оптимальных задач
- методы исследования функций классического анализа;
- методы, основанные на использовании неопределенных множителей Лагранжа;
- вариационное исчисление;
- динамическое программирование;
- принцип максимума;
- линейное программирование;
- нелинейное программирование.
В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.
Как правило, нельзя рекомендовать
какой-либо один метод, который можно
использовать для решения всех без
исключения задач, возникающих на практике.
Одни методы в этом отношении являются
более общими, другие - менее общими.
Наконец, целую группу методов (методы
исследования функций классического
анализа, метод множителей Лагранжа,
методы нелинейного программирования)
на определенных этапах решения оптимальной
задачи можно применять в сочетании
с другими методами, например динамическим
программированием или
Отметим также, что некоторые методы специально разработаны или наилучшим образом подходят для решения оптимальных задач с математическими моделями определенного вида. Так, математический аппарат линейного программирования, специально создан для решения задач с линейными критериями оптимальности и линейными ограничениями на переменные и позволяет решать большинство задач, сформулированных в такой постановке. Так же и геометрическое программирование предназначено для решения оптимальных задач, в которых критерий оптимальности и ограничения представляются специального вида функциями позиномами.
Динамическое программирование
хорошо приспособлено для решения
задач оптимизации
Пожалуй, наилучшим путем при выборе метода оптимизации, наиболее пригодного для решения соответствующей задачи, следует признать исследование возможностей и опыта применения различных методов оптимизации. Ниже приводится краткий обзор математических методов решения оптимальных задач и примеры их использования. Здесь же дана лишь краткая характеристика указанных методов и областей их применения, что до некоторой степени может облегчить выбор того или иного метода для решения конкретной оптимальной задачи.
Методы исследования функций
классического анализа
Дополнительные трудности
при решении оптимальной задачи
методами исследования функций классического
анализа возникают вследствие того,
что система уравнений, получаемая
в результате их применения, обеспечивает
лишь необходимые условия
Методы исследования при
наличии ограничений на область
изменения независимых
Метод множителей Лагранжа применяют для решения задач такого же класса сложности, как и при использовании обычных методов исследования функций, но при наличии ограничений типа равенств на независимые переменные. К требованию возможности получения аналитических выражений для производных от критерия оптимальности при этом добавляется аналогичное требование относительно аналитического вида уравнений ограничений.
В основном при использовании метода множителей Лагранжа приходится решать те же задачи, что и без ограничений. Некоторое усложнение в данном случае возникает лишь от введения дополнительных неопределенных множителей, вследствие чего порядок системы уравнений, решаемой для нахождения экстремумов критерия оптимальности, соответственно повышается на число ограничений. В остальном, процедура поиска решений и проверки их на оптимальность отвечает процедуре решения задач без ограничений.
Множители Лагранжа можно
применять для решения задач
оптимизации объектов на основе уравнений
с частными производными и задач
динамической оптимизации. При этом
вместо решения системы конечных
уравнений для отыскания
Следует отметить, что множители Лагранжа используют также в качестве вспомогательного средства и при решении специальными методами задач других классов с ограничениями типа равенств, например, в вариационном исчислении и динамическом программировании. Особенно эффективно применение множителей Лагранжа в методе динамического программирования, где с их помощью иногда удается снизить размерность решаемой задачи.
Методы вариационного исчисления обычно используют для решения задач, в которых критерии оптимальности представляются в виде функционалов и решениями которых служат неизвестные функции. Такие задачи возникают обычно при статической оптимизации процессов с распределенными параметрами или в задачах динамической оптимизации.
Вариационные методы позволяют
в этом случае свести решение оптимальной
задачи к интегрированию системы
дифференциальных ' уравнений Эйлера,
каждое из которых является нелинейным
дифференциальным уравнением второго
порядка с граничными условиями,
заданными на обоих концах интервала
интегрирования. Число уравнений
указанной системы при этом равно
числу неизвестных функций, определяемых
при решении оптимальной
Уравнения Эйлера выводятся
как необходимые условия
При наличии ограничений типа равенств, имеющих вид функционалов, применяют множители Лагранжа, что дает возможность перейти от условной задачи к безусловной. Наиболее значительные трудности при использовании вариационных методов возникают в случае решения задач с ограничениями типа неравенств.
Заслуживают внимания прямые методы решения задач оптимизации функционалов, обычно позволяющие свести исходную вариационную задачу к задаче нелинейного программирования, решить которую иногда проще, чем краевую задачу для уравнений Эйлера.
Динамическое программирование
По существу метод динамического
программирования представляет собой
алгоритм определения оптимальной
стратегии управления на всех стадиях
процесса. При этом закон управления
на каждой стадии находят путем решения
частных задач оптимизации
Ограничения на переменные
задачи не оказывают влияния на общий
алгоритм решения, а учитываются
при решении частных задач
оптимизации на каждой стадии процесса.
При наличии ограничений типа
равенств иногда даже удается снизить
размерность этих частных задач
за счет использования множителей Лагранжа.
Применение метода динамического программирования
для оптимизации процессов с
распределенными параметрами
При решении задач методом
динамического
Принцип максимума применяют для решения задач оптимизации процессов, описываемых системами дифференциальных уравнений. Достоинством математического аппарата принципа максимума является то, что решение может определяться в виде разрывных функций; это свойственно многим задачам оптимизации, например задачам оптимального управления объектами, описываемыми линейными дифференциальными уравнениями.
Нахождение оптимального
решения при использовании
Принцип максимума для процессов, описываемых дифференциальными уравнениями, при некоторых предположениях является достаточным условием оптимальности. Поэтому дополнительной проверки на оптимум получаемых решений обычно не требуется.
Для дискретных процессов принцип максимума в той же формулировке, что и для непрерывных, вообще говоря, несправедлив. Однако условия оптимальности, получаемые при его применении для многостадийных процессов, позволяют найти достаточно удобные алгоритмы оптимизации.
Линейное программирование
Для решения большого круга
задач линейного
Методы нелинейного
Для получения численных результатов важное место отводится нелинейному программированию и в решении оптимальных задач такими методами, как динамическое программирование, принцип максимума и т. п. на определенных этапах их применения.
Названием “методы нелинейного
программирования” объединяется большая
группа численных методов, многие из
которых приспособлены для
Геометрическое
Специфической особенностью
методов решения оптимальных
задач (за исключением методов
Важной характеристикой любой оптимальной задачи является ее размерность п, равная числу переменных, задание значений которых необходимо для однозначного определения состояния оптимизируемого объекта. Как правило, решение задач высокой размерности связано с необходимостью выполнения большого объема вычислений. Ряд методов (например, динамическое программирование и дискретный принцип максимума) специально предназначен для решения задач оптимизации процессов высокой размерности, которые могут быть представлены как многостадийные процессы с относительно невысокой размерностью каждой стадии.
1.1 Минимизация функций многих переменных. Основные положения
Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е.
f'(x[0]) = (дf(х[0])/дх1, …, дf(х[0])/дхn)T.
Этот вектор перпендикулярен к плоскости, проведенной через точку х[0] , и касательной к поверхности уровня функции f(x),проходящей через точку х[0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С0, С1, ... , получим серию поверхностей, характеризующих ее топологию (Рис. 1.1).
Рис. 1.1. Градиент
Вектор-градиент направлен
в сторону наискорейшего
Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f’(х[k]) в точке х[k], получаем итерационный процесс вида
х[k+1] = x[k]-akf'(x[k]), аk > 0; k=0, 1, 2, ...
В координатной форме этот процесс записывается следующим образом:
xi[k+1]=хi[k] - ak f(x[k])/ xi
i = 1, ..., n; k= 0, 1, 2,...
В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || <= e, либо выполнение условия малости градиента
|| f’(x[k+l]) || <= g,
Здесь e и g - заданные малые величины.
Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага аk.
При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шагаk обеспечит убывание функции, т. е. выполнение неравенства
f(х[k+1]) = f(x[k] – akf’(x[k])) < f(x[k]).
Однако это может привести
к необходимости проводить
Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется. Рассмотрим применяемые на практике варианты таких методов.
1.2 Метод наискорейшего спуска
При использовании метода
наискорейшего спуска на каждой итерации
величина шага аk выбирается
из условия минимума функции f(x) в направлении
спуска, т. е.
f(x[k] –akf’(x[k])) =
f(x[k] – af'(x[k])).
Это условие означает, что
движение вдоль антиградиента происходит
до тех пор, пока значение функции f(x) убывает. С
математической точки зрения на каждой
итерации необходимо решать задачу одномерной
минимизации по а функции
j(a) = f(x[k] - af'(x[k])) .
Алгоритм метода наискорейшего спуска состоит в следующем.
1. Задаются координаты начальной точки х[0].
2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k]).
3. Определяется величина шага ak, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).
4. Определяются координаты точки х[k+1]:
хi[k+1] = xi[k] – аkf’i(х[k]), i = 1 ,..., п.
5. Проверяются условия
останова стерационного
В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 1.2). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг ak выбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:
dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.
Рис. 1.2. Геометрическая интерпретация метода наискорейшего спуска
Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)
мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями li, i =1, …, n, матрицы являются корни характеристического уравнения
Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 1.3), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 1.3) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.
Рис. 1.3. Овражная функция
Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Вследствие перечисленных причин градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х[0] находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.
1.3 Метод сопряженных градиентов
Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию
f(x) = (х, Нх) + (b, х) + а
с симметрической положительно определенной матрицей Н за конечное число шагов п , равное числу переменных функции. Любая гладкая функция в окрестности точки минимума хорошо аппроксимируется квадратичной, поэтому методы сопряженных градиентов успешно применяют для минимизации и неквадратичных функций. В таком случае они перестают быть конечными и становятся итеративными.
По определению, два n-мерных вектора х и у называют сопряже
Одной из наиболее существенных
проблем в методах сопряженных
градиентов является проблема эффективного
построения направлений. Метод Флетчера-Ривса
решает эту проблему путем преобразования
на каждом шаге антиградиента -f(x[k]) в направление p[k], H-
Направления р[k] вычисляют по формулам:
p[k] = -f’(x[k])+bk-1p[k-l], k >= 1;
p[0] = -f’(x[0]).
Величины bk-1 выбираются так, чтобы направления p[k], р[k-1] были H-сопряженными:
(p[k], Hp[k-1])= 0.
В результате для квадратичной функции
,
итерационный процесс минимизации имеет вид
x[k+l] =x[k] +akp[k],
где р[k] - направление спуска на k-м шаге; аk - величина шага. Последняя выбирается из условия минимума функции f(х) поа в направлении движения, т. е. в результате решения задачи одномерной минимизации:
f(х[k] + аkр[k]) = f(x[k] + ар [k]).
Для квадратичной функции
Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.
1. В точке х[0] вычисляется p[0] = -f’(x[0]).
2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка х[k+1].
3. Вычисляются величины f(x[k+1])
4. Если f’(x[k+1]) = 0, то точка х[k+1] является точкой минимума функции f(х). В противном случае определяется новое направление p[k+l] из соотношения
и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за пшагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:
x[k+l] = x[k] +akp[k],
p[k] = -f’(x[k])+bk-1p[k-l], k >= 1;
p[0] = -f’(x[0]);
f(х[k] + akp[k]) = f(x[k] + ap[k];
.
Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.
