Поиск оптимума численными методами

Численные методы поиска применяют, во-первых, когда в точке экстремума отсутствуют производные. Так, изменение целевой функции может носить дискретный характер, например, при срав­нении разных вариантов оформления процесса, когда R меняется не непрерывно, а скачком от одного варианта к другому. Но про­изводные в точке экстремума могут отсутствовать и у непрерывной функции. Чаще всего это бывает, если экстремум расположен на краю области допустимых значений. На рис. 23.1 максимум лежит на краю области, в этой точке производная отсутствует. Имеется «производная слева», но она не равна нулю.

Рис 23.1 График, иллюстрирующий оптимум на краю области допустимых значений

а, b - границы области допустимых значений.

Часто бывает и так, что целевая функция в точке экстремума дифференцируема, но задана она таким образом, что продифферен­цировать ее в общем виде не удается, вследствие чего приходится обращаться к численным методам. Это обычно связано с тем, что функция задана не формулой, а алгоритмом вычисления при за­данных значениях аргументов (факторов). Если бы не было и алгоритма, функция была бы невычислимой и следовало бы при­менить экспериментальную оптимизацию.

Наконец, иногда имеется принципиальная возможность запи­сать и решить систему

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

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

Оптимизация перебором применяется, если число возможных вариантов конечно. Тогда достаточно рассчитать целевую функ­цию для всех этих вариантов и выбрать наибольшее (или наимень­шее) значение. Например, мы можем рассчитать R для случаев протекания процесса в аппаратах всех стандартизованных разме­ров и выбрать лучший вариант.

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

Сканирование — метод, близкий к перебору, но применяемый к непрерывным функциям.

Рассмотрим для примера одномерное сканирование — случай, когда ищем максимум функции от одного фактора (как мы уже говорили, поиск минимума осуществляется точно так же). Будем считать, что мы задались пределами изменения фактора х от а до Ь. Здесь а и b — ограничения, которые можно установить в любой реальной задаче: никогда не бывает так, что мы может задать лю­бые, ничем не ограниченные значения х.

Таким образом, вначале мы знаем следующее. Имеется интер­вал [а, b], на котором мы хотим отыскать экстремум целевой функции; его называют интервал неопределенности.

При этом практически нам не нужно определить точку экстре­мума абсолютно точно. Достаточно сильно сузить интервал неопре­деленности. Например, если мы узнаем, что оптимальная темпера­тура, соответствующая максимуму целевой функции, заключена в пределах от 380 К до 381 К, то большая точность не нужна. В про­мышленных условиях вряд ли удастся регулировать температуру с точностью выше 1 К. Нас устраивает интервал неопределенности [380, 381], и дальнейшее его сужение смысла не имеет.

Итак, в одномерном случае (k = 1) задача поиска экстремума сводит­ся к сужению интервала неопределенности. Методом сканирования эта задача решается так.

Выберем целое число q — число значений целевой функции, которое придется рассчитывать. Рассчитаем интервал x:

Отложим от точки а до точки b интервалы x; (рис. 25.1). Кон­цы каждого интервала назовем узлами; на рис. 25.1 каждый узел обозначен крестиком

В каждом узле рассчитаем R (х) (см. точки на рис. 25.1). Теперь мы можем принять за максимум наибольшее из полученных значений — на рисунке это 4-я точка слева. К концу расчета интер­вал неопределенности  составит 2x: истинный максимум может лежать либо справа, либо слева от полученной наилучшей точки (пунктиры на рис. 25.1). Таким образом

Формула (25.2) определяет эффективность метода. При сканировании для достижения достаточно малого  величина q должна быть велика. Метод малоэффективен. Но он удобен для первоначального исследования функции, поскольку дает возмож­ность представить ее вид на всем отрезке, установить число экстре­мумов и их локализацию.

Сканированием можно исследовать и функции более чем одно­го фактора. Так, участок на плоскости (факторное пространство для двух факторов) можно покрыть сетью узлов и таким образом исследовать поведение функции на этом участке. В принципе это возможно в любом k-мерном пространстве, но по мере роста k резко растет число необходимых расчетов и падает эффектив­ность метода.

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

Прежде всего, направленный поиск дает надежный результат, если функция унимодальна. Наиболее просто (хотя и не впол­не строго) унимодальную функцию можно определить так. В до­пустимой области она имеет только один экстремум нужного знака (один максимум, если ищем максимум, один минимум в противо­положном случае). Например, на рис. 25.2 функция 1 унимодальна. Функция 2 унимодальна, если ищем максимум, и неунимодальна при поиске минимума (два минимума —при х = а и при х = b). Функция 3 неунимодальна.

Методы направленного поиска способны привести в точку од­ного из экстремумов, но не позволяют установить, единственный ли это экстремум, а если известно, что не единственный, то в какой экстремум мы попали: глобальный (экстремальный для всей об­ласти) или локальный (другие точки могут оказаться выше в слу­чае максимума или ниже для минимума). Если при решении за­дачи оптимизации появится подозрение, что мы встретились с неунимодальностью, следует грубо исследовать функцию скани­рованием и выделить область глобального экстремума.

Еще одно важное свойство функции R, учитываемое при выборе метода поиска, — это число факторов. Здесь различаются два основных случая. Первый, когда R зависит только от одного фактора, R — R(x): тогда говорят об одномерном поиске. Второй, когда факторов больше одного — многомерный поиск. При­чем почти все методы многомерного поиска принципиально при­менимы при любом числе факторов k>1, тогда как при k = 1 при­меняются иные, одномерные методы. Лишь немногие методы, как например, сканирование, применимы и в одномерном, и в много­мерном случаях.