3608 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ОДНОМЕРНЫХ МЕТОДОВ В ЗАДАЧАХ СИНТЕЗА РЭС

ВВЕДЕНИЕ

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

Ниже будут рассмотрены некоторые методы одномерной минимизации. При этом предполагается, что функция f(x) дважды непрерывно дифференцируема на отрезке [a, b], на котором она также достигает своего минимума в единственной точке .

1. Метод прямого перебора

Метод прямого перебора является простейшим методом поиска, в котором точка минимума определяется по значениям функции на равномерной сетке. Для этого отрезок [a, b] разбивается на N одинаковых интервалов и в каждой из точек разбиения вычисляется значение функции. В качестве решения задачи  выбирается точка, в которой функция имеет минимальное значение. При этом интервал, которому принадлежит точка минимума (интервал неопределенности), имеет длину .

Другой разновидностью метода прямого перебора является метод Монте-Карло, в котором точка минимума определяется по значениям функции на случайной сетке. При этом точки разбиения выбираются  случайно  с  равномерным  законом  распределения  на отрезке [a, b].

2. Метод деления отрезка пополам

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

Очевидно, что если функция f(x) является унимодальной на отрезке [a, b], то для того чтобы сократить интервал неопределенности, необходимо вычислить значения функции как минимум в двух точках (рис. 1). Если , то интервалом неопределенности будет отрезок ; если же , то интервалом неопределенности будет отрезок . Каждый из этих интервалов имеет длину соответственно  и . Интервал неопределенности имеет наименьшую длину, если . Однако в этом случае две точки  и  вырождаются в одну. Поэтому выбираются точки  и , где  - малое число. В методе дихотомии интервал неопределенности выбирается в зависимости от значений функции  f(x) в точках , .

 

Рис. 1

Модельная схема метода деления отрезка пополам

  1. Начальный этап

Выбирается положительное малое , а также конечное значение  длины интервала неопределенности. Полагается .

  1. Основной этап

2.1.  Если , то вычисления прекращаются и ; иначе - определяют величины: ,  и переходят к п. 2.2.

2.2.  Если , то , ; в противном случае , . После этого полагается  и осуществляется переход к пункту 2.1.

Число вычислений целевой функции в этом методе, необходимое для достижения интервала неопределенности,  определяется по формуле

,

где [.] - операция взятия целой части.

3. Метод золотого сечения

Рис. 2

 

Более эффективным, по сравнению с методом дихотомии, является метод золотого сечения. В этом методе на каждом шаге итерационного процесса (за исключением первого) вычисляется только одно значение функции в точке, которая выбирается по правилу золотого сечения. Точка x делит отрезок [a, b] по правилу золотого сечения, если  (рис. 2).

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

Модельная схема метода золотого сечения

  1. Начальный этап

Выбирается конечное значение  длины интервала неопределенности. Полагается , , , , . Вычисляются  и .

  1. Основной этап

2.1.  Если , то вычисления прекращаются и . В противном случае, если ,  осуществляется переход к п. 2.2, а если , то - к п. 2.3.

2.2.  Полагается , , . Вычисляется  и осуществляется переход к п. 2.4.

2.3.  Полагается , , . Вычисляется  и осуществляется переход к п. 2.4.

2.4.  Полагается  и осуществляется переход к п. 2.1.

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

.

4. Метод Фибоначчи

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

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

Пусть n - заданное число вычислений целевой функции, которое предполагается затратить для получения требуемого интервала неопределенности ;  - начальный интервал неопределенности;  - интервал неопределенности, полученный после i-й итерации. Рассмотрим две точки  и  из интервала , заданные с помощью соотношений

, , .

Новый интервал неопределенности  равен , если , и , если . Тогда в первом случае новый интервал неопределенности имеет длину

,

а во втором -

.

Отсюда следует, что как в первом, так и во втором случае на i-й итерации интервал неопределенности сжимается в  раз. Можно показать, что на (i+1)-й итерации либо , либо . Поэтому на каждом шаге вычисляется только одно значение функции.

В методе Фибоначчи число итераций n выбирается из следующих соображений. Так как на каждом шаге интервал неопределенности сжимается в  раз, то после (n-1) итераций интервал неопределенности сжимается в  раз. Отсюда следует, что если  - длина конечного интервала неопределенности, то число итераций n можно выбрать из условия .

Модельная схема метода Фибоначчи

  1. Начальный этап

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

  1. Основной этап

2.1.  Если , то осуществляется переход к п. 2.2, если , то - к п. 2.3.

2.2.  Полагается , . После этого вычисляются  и . Если , то осуществляется переход к п. 2.5; в противном случае вычисляется  и осуществляется переход к п. 2.4.

2.3.  Полагается , . После этого вычисляются  и . Если , то осуществляется переход к п. 2.5; в противном случае вычисляется  и осуществляется переход к п. 2.4.

2.4.  Полагается  и осуществляется переход к п. 2.1.

2.5.  Полагается , . Если , то принимается , ; иначе - ,  и вычисления прекращаются. Точка минимума .

5. Методы полиномиальной интерполяции

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

5.1. Квадратичная интерполяция (метод Пауэлла)

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

,

где;

;

;

.

Функция  имеет минимум в точке . Следовательно, можно аппроксимировать точку минимума целевой функции значением .