Методы поиска экстремума. Оптимизация

3.1. Методы поиска экстремума.

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

Простейшей оптимизационной задачей является поиск экстремума функции одной переменной (одномерная или однопараметрическая оптимизация).

Пусть функция , называема целевой функцией, определена на отрезке . Если в области определения функции существует окрестность такая, что для всех (или ), то точка является локальным максимумом (минимумом) функции . Наибольшее (наименьшее) значение функции в области ее определения называется глобальным максимумом (минимумом). Функция, имеющая один локальный максимум (минимум), называется унимодальной. Для определенности будем говорить о максимуме функции. Естественно, что для унимодальной функции глобальный и локальный максимумы совпадают.

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

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

Отметим тесную связь задач оптимизации и нахождения корней уравнений. Действительно, решение уравнения равносильно нахождению точки минимума функции (или максимума функции )

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

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

Рис.1

Если , то максимум расположен в интервале , а интервал не содержит максимума и из дальнейшего рассмотрения исключается.

Если , то максимум функции расположен в интервале , а интервал - отбрасывается

Если , то максимум функции лежит в интервале между точками и , а интервалы и - отбрасываются.

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

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

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

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

3.2. Пассивный поиск.

Пассивные методы недостаточно эффективны по сравнению с последовательными. Однако они все-таки используются, в частности, если все эксперименты должны проводиться одновременно.

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

Рис.2

Общая формула для оптимального размещения экспериментов при их четном числе имеет вид

,

Где означает целую часть числа. При этом максимум находится в интервале , где - эксперимент, в котором получено наибольшее значение . Интервал неопределенности равен , т.е. он уменьшается прямо пропорционально числу опытов. На Рис.3 показано оптимальное размещение 6 экспериментов при последовательном поиске. Такое размещение экспериментов называется поиском однородными парами. Проведение нечетного числа опытов обычно нецелесообразно.

Рис.3

3.3. Последовательный поиск.

Метод дихотомии (половинного деления )

Первые два эксперимента проводятся посередине исходного интервала возможно ближе друг к другу: и . Интервал, не содержащий максимума отбрасывается, как показано на Рис.4. Длина оставшегося интервала равна

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

Рис.4

Как видно, интервал неопределенности уменьшается экспоненциально с ростом . Условие окончания итерационного процесса . При пассивном поиске для уменьшения исходного интервала неопределенности в 100 раз требуется 198 экспериментов, тот же результат достигается дихотомией уже после 14 экспериментов (см. Табл.1)

Поиск по сайту: