Методы одномерной оптимизации

19. Методы одномерной оптимизации

Допустим, что целевая функция u(x), хÎ[а,b] унимодальна и на интервале [а,b], включая его концы, имеет один минимум. Необ­ходимо отыскать оптимальное значение        проектного пара­метра xc точностью до некоторой, наперед задаваемой величины ε,обеспечивающее

 

Интервал [а, Ь] значений проектного параметра xÎ[a,b] бу­дем называть интервалом неопределенности, и его начальная длина          

            Процесс оптимизации сводится к уменьшению    до величи­ны

Метод общего поиска. Суть метода общего поиска, или, как его еще называют, метода перебора [17, 18] в том, что исходный интер­вал неопределенности [а, Ь] делится на N равных частей с шагом h = (b - a)/N  и в (N+1) узлах полученной сетки вычисляются значения

                           целевой функции

 

                       как показано на     рисунке.

                   Пусть минимальным из

          вычисленных значений

        оказалось

                Следовательно, оптимальный

      параметр

                         и тем самым исходный интервал неопределенности 

   удалось сузить до величины

Чтобы обеспечить

 необходимо вычислить целевую функцию в 21 точке, а что­бы уменьшить

в 100 раз, требуется 201 значение целевой функции.

Описанный способ оказывается весьма трудоемким, поскольку для выполнения соотношения

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

Повысить эффективность метода общего поиска можно путем пос­ледовательного сужения интервала неопределенности. Осуществляется это следующим образом. Предположим, что исходный интервал неопре­деленности [а, b] необходимо уменьшить в 100 раз. Это можно проде­лать в два этапа. Вначале, вычислив целевую функцию в 21 точке, уменьшим [а, Ь] в 10 раз, а полученный новый интервал неопределен­ности

снова уменьшим в 10 раз, причем во втором слу­чае понадобится 19 вычислений целевой функции, поскольку

 уже известны. Таким образом, последовательное сужение ин­тервала неопределенности позволило уменьшить количество вычислений целевой функции до 40 вместо 201 в рассмотренном ранее случае. Од­нако и в таком варианте метод общего поиска требует существенных вычислительных затрат.

Существуют более эффективные методы оптимизации, реализующие различные способы сужения интервала неопределенности [18, 19].

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

 

 Пусть на нулевом шаге длина интервала неопределенности [a,b] задана в виде

 Внутри [а, Ь] выбираются две точки х1 и х2 и вычисляются u(x1) и u(x2). Оказывается, что u(x1)<u(x2),  сле-

довательно, искомый минимум располагается между

В полученном новом интервале неопределеннности

необходимо опять выбрать две точки, но одна из них

уже есть, поэтому выбирается точка

Границы нового интервала неопределенности

Описанная процедура продолжается до тех пор¸ пока не будет выполнено соотношение

Точка золотого сечения выбирается из условия

где представляет собой длину интервала неопределеннос­ти. Проделав элементарные преобразования с соотношением (6.1), а именно

получим

Таким образом, метод золотого сечения можно представить в ви­де итерационного процесса, на каждом k-м (k = 1, 2, ...) шаге ко­торого выполняются следующие операции [19]:

1) определяется k-е значение x1k в виде

и   вычисляется

2) определяется k-е значение x2k виде

и вычисляется

3) определяется k-й интервал неопределенности

согласно следующим соображениям:

     

вычис­лено в операции 2),

4) находится длительность k-го интервала неопределенности

и производится сравнение:

Описанный итерационный процесс всегда сходится, причем за

итераций [19] (INT - целая часть числа). Для не унимодальных целе­вых функций метод золотого сечения может сойтись к любому локаль­ному экстремуму.