ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МЕТОДОВ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ. АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ

Новокузнецк

Министерство образования Российской Федерации

Сибирский государственный индустриальный университет

Кафедра информационных технологий в металлургии

АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ

Методические указания к выполнению лабораторно-практических работ по курсу «Методы оптимизации в металлургии»

Специальности: «Металлургия черных металлов» (110100),

специализации «Информационные технологии и предпринимательство
в металлургии» (110107),

по курсу «Оптимизация в технике и технологиях»

Специальности: «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение».

Новокузнецк

УДК 681.3.06

Алгоритмы и примеры решения задач многомерной оптимизации: Метод. указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 34с., ил.

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

Предназначены для студентов специальности «Металлургия черных металлов» (110100), специализации «Информационные технологии и предпринимательство в металлургии» (110107) и «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение»

Рецензент - кафедра систем автоматизации (зав. кафедрой С.М.Кулаков)

Печатается по решению редакционно-издательского совета университета.

ОБЩИЕ ПОЛОЖЕНИЯ

Решение оптимизационной задачи в общем случае заключается в определении таких значений входных переменных исследуемого объекта, которым соответствует наилучшее (минимальное или максимальное) значение целевой функции. Технологические системы, как правило, являются многомерными, с большим количеством входных факторов, на значение которых к тому же накладываются дополнительные ограничения. Это требует использования методов многомерной условной оптимизации. Многое из данного метода, однако, предполагает сведение задачи к безусловной оптимизации путем преобразования целевой функции с дальнейшим применением соответствующих процедур. Поэтому изучение методов поиска экстремума функций нескольких переменных без ограничений является не менее важной задачей.

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

ПОСТАНОВКА ЗАДАЧИ

Постановка задачи многомерной оптимизации заключается в нахождении для функции n действительных переменных

f(x₁, x₂, x₃, …, x_n) = f(X), xÎEⁿ

компонентов вектора X^*, которые дают условие

f(X^*) = min(max)f(X).

Рассматривая локальный X₀ и глобальный X^* экстремумы функции можно отметить их особенности. Функция f(X) имеет локальный минимум в точке X₀, если существует окрестность, такая, что f(X) больше f(X₀) во всех точках этой окрестности. В случае глобального минимума в точке X^* для всех X справедливо неравенство f(X) ³ f(X^*).

Аналитический анализ функции. Необходимым условием минимума в точке X₀ является уравнение Ñf(X₀) = 0, т.е. ¶ f(X₀)/¶x_i = 0 (i = 1, …, n).

Необходимыми и достаточными условиями минимума являются: Ñf(X₀) = 0; H(X₀) положительно определена. Необходимыми и достаточными условиями максимума являются: Ñf(X_m) = 0; H(X_m) - отрицательно определена.

H(X_0(m)) - матрица Гессе f(X), представляющая квадратичную матрицу вторых частных производных f(X) взятых в точке X_0(m).

H(X_0(m)) = .

Построение линий уровня Область f(X), в которой осуществляется нахождение оптимального решения, представляет некоторую поверхность в многомерном пространстве. Поверхность отклика наглядно можно представить для одномерного и двухмерного случаев. Для графического представления функций двух переменных используют линии уровня. Это множество точек, для которых целевая функция имеет постоянное значение. В топологии поверхности оптимума выделяют несколько характерных видов: круговой холм, эллиптический холм, симметричное или вытянутое седло, стационарный или спадающий овраг и др.

Для построения линий уровня в двумерной случае необходимо выразить одну переменную через другую переменную и целевую функцию
x₁=F(x₂, f(x₁,x₂)). Затем, задав значение функции и варьируя одну из переменных, рассчитать значение другой переменной. По полученным точкам строят линию уровня. Затем необходимо изменить значение функции и вновь повторить процедуру. Операция повторяется столько раз, сколько необходимо провести линий уровня.

Классификация методов. Выделяют два класса методов: поисковые или методы нулевого порядка и методы с использованием производных.

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

Методы с использованием производных делятся также на две группы: первого и второго порядка. К методам первого порядка относятся методы: градиентный, Бокса-Уилсона, наискорейшего спуска, методы сопряженных направлений и сопряженного градиента, переменной метрики и др. К методам второго порядка, которые используют вторые частные производные, относится метод Ньютона и его модификации.

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

ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МЕТОДОВ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ. АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ.

Поисковые методы.

Метод сканирования.

Простейшим методом является сканирование, которое строится аналогично одномерному поиску. Рассчитывается значение целевой функции в узлах сетки, затем определяется координата, в которой функция принимает минимальное значение. Можно проводить локализацию оптимума. Метод очень прост в реализации. Позволяет найти все локальные и глобальные решения поставленной задачи в заданной области определения критерия, а результаты поиска не зависят от вида целевой функции. Однако у этого метода есть один решающий недостаток. Это большое количество вычислений целевой функции, которое необходимо произвести для достижения требуемой точности. Этот недостаток особенно резко проявляется при применении метода сканирования с постоянным шагом, когда число разбиений для каждой переменной подбирается таким образом, чтобы шаг был соизмерим с точностью.