Основы теории оптимизации (стр. 15 )

последовательности одномер­ных минимизаций. В отличие от метода покоординатного спуска, где система направле­ний спуска жестко фиксиру­ется (этой системой являются координатные орты), в данных методах направления спуска строятся в процессе минимизации. Принцип их построения — сделать их (для задачи ми­нимизации квадратичной функции) сопряженными; тогда, как мы знаем процесс минимизации конечен в квадра­тичном случае. Основная идея методов этой группы иллю­стрируется рис. 2 — три последовательные одномерные мини­мизации приводят в точку минимума.

Рис. 2. Метод сопряженных направлений

В многомерном простран­стве верен аналогичный результат.

Лемма 2. Пусть р1, ..., рk — сопряженные векторы: (Арi, рj) =0, i ≠ j, k < п,

Тогда

Тогда вектор рk +1 = у1 — y0 является сопряженным с р1, ..., рk.

Этот результат следует из условия минимума f(x) на под­пространстве.

На этой основе можно построить метод минимизации, напри­мер, следующим образом. Пусть xk — полученное на k-й итера­ции приближение к решению, р0, ..., pk — найденные направ­ления (х0 и р0 произвольны). Построимгде hk — произвольный вектор, не являющийся линейной комбинацией р0, ..., pk. Проведем цикл последовательных одномерных мини­мизаций по направлениям р0, ..., pk, начиная из точки обо­значим полученную в результате точку В качестве xk+1 возьмем минимум f(x) на прямой, соединяющей а в качестве pk+1 — вектор Для квадратичной функции в Rп такой метод Пауэлла приводит к минимуму не более чем за п шагов.

Существует и много других модификаций, основанных на по­добной идее. Всего для отыскания минимума в квадратичном случае требуется п(п+1)/2 одномерных минимизаций. Если считать, что каждая из них включает три вычисления функции, то видно, что метод менее экономен, чем (4), (5) (где нужно п(п+1)/2 вычислений для той же цели). Однако в неквадра­тичном случае метод работоспособен даже для плохого началь­ного приближения (если принять меры против вырождения системы рі), тогда как метод барицентрических координат по­добно методу Ньютона требует хорошего начального прибли­жения.

3.4. Метод перебора

Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.

Разобьем отрезок [a; b] на N равных частей точками деленияВычислив значения f(x) в точках xі, путем сравнения найдем точку хт, 0≤т≤п, для которой

(1)

Далее, положим

Замечание:

1 Потребность определения точки минимума х* функции f(x) методом перебора не превосходит величины

Предположим, что хт из (1) является внутренней точкой разбиения отрезка [a;b], т. е. 1≤т≤п-1 (случаи т = 0 и т = п рассматриваются аналогично). Тогда из соотношения (1) с учетом свойства унимодальных функций следует, что:

Отсюда получаем, что

Длина последнего отрезка равна 2(b-a/n), а точка хт является его серединой. Поэтому

Таким образом, чтобы обеспечить требуемую точность ε определения точки х*, число отрезков разбиения п необходимо выбрать из условия

2. Пусть реализация метода перебора потребовала N вычислений функции f(x). Это означает, что отрезок [a;b] был разбит на n = N-1 частей и достигнутая точность определения х* составила

Поэтому точность решения ε(N),которую обеспечивает метод перебора в результате N вычислений f(x) будет

Пример. Метод перебора

Решить задачус точностью до ε = 0.1

Функция f(x) унимодальна на отрезке [0;l]. Найдем число п отрезков разбиения т. е., можно взять n = 10. Вычислим значения f(xi), где хi = 0,1∙i, i = 0,...,10 и запишем их в таблицу 1

Таблица 1

В этой таблице выделено минимальное из вычисленных значений f(x). Таким образом,

3.5. Метод поразрядного поиска

Рассмотрим возможности усовершенствования метода перебора с целью уменьшения количества значений f(x), которые необходимо находить в процессе минимизации.

Во-первых, если оказывается, что то отпадает необходимость вычислять f(x) в точках хi+2, х i+3 и т. д., так как х* ≤ хi+1 (см. в п.3.4 (1)).

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

Указанные возможности улучшения метода перебора реализованы в методе поразрядного поиска. В этом методе перебор точек отрезка происходит сначала с шагом ∆=xi+1–xi>ε до тех пор, пока не выполнится условие или пока очередная из этих точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения f(x) снова не перестанут уменьшаться или очередная точка не совпадёт с другим концом отрезка и т. д. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг дискретизации не превосходит ε. Приведем описание алгоритма метода поразрядного поиска.

Шаг 1. Выбрать начальный шаг

Положить х0 =а. Вычислить f(х0).

Шаг 2. Положить х1 = х0 + ∆. Вычислить f(х1).

Шаг 3. Сравнить f(х0) и f(х1). Если f(х0)> f(х1), то прейти к шагу 4,

иначе - к шагу 5.

Шаг 4. ПоложитьПроверить условие х0 (a;b). Если а<х0 <b , то перейти к шагу 2, иначе - к шагу 5.

Шаг 5. Проверка на окончание поиска: еслито вычисление завершить, полагая иначе - перейти к шагу 6.

Шаг 6. Изменение направления и шага поиска: продолжить х0 = х1, Перейти к шагу 2.

Пример. Метод поразрядного поиска.

Решить задачу, приведенную в предыдущем примере.

Начальный шаг ∆ = 1/4 = 0,25. Вычисляя последовательно значения f(x) в точках дискретизации с шагом 0,25, получим:

Так как f(0,50) <f(0,75), причемто поиск х* продолжаем из начальной точки х0 =0,75, изменив его направление и уменьшив шаг в 4 раза: