Нелинейное программирование. Постановка задачи

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

Рис. 5.1 Интервал неопределенности

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

Рис. 5.2 Сужение интервала неопределенности путем вычисления двух значений целевой функции

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

Задачу одномерной оптимизации можно поставить следующим образом. Значения проектного параметра х должны быть заключены в интервале а<=х<=b. Приступая к решению задачи, мы ничего не знаем о целевой функции, кроме того что она унимодальна. Интервал значений х, в котором заключен оптимум, будем называть «интервалом неопределенности». В начале процесса оптимизации этот интервал имеет длину b— а (рис. 6.5). Вычислив значения целевой функции М₁ и M₂ при значениях x₁ и x₂ в указанном интервале, сузим интервал неопределен­ности (рис. 5.2). Существует несколько способов систематиче­ского сужения интервала, которые излагаются ниже.

5.1. Общий поиск

Очевидно, наиболее естественным способом сужения интервала неопределенности для одномерной унимодальной функции является деление его на несколько равных частей с последующим вычислением значений целевой функции в узлах полученной сетки (рис. 5.3). В результате интервал неопределенности сужается до двух шагов сетки. Обычно говорят о дроблении интервала неопределенности, которое характеризуется коэффициентом f. Разделив интервал неопределенности на N частей, получим N+1 узел, и тогда

Чтобы получить значение f==0,01, потребуется вычислить целевую функцию в 199 точках, а при f=0,001 N=1999. Ясно, что эффективность этого

Рис. 5.3 Метод общего поиска

метода при уменьшении интервала неопре­деленности быстро падает. Сам собой напрашивается другой путь: чтобы получить f=0,01, вычислить сначала функцию в 19 точках и получить f=0,1, а затем, вычислив еще 19 значе­ний функции на сокращенном интервале неопределенности, по­лучить f=0,01, сделав при этом всего 38, а не 199 вычислений. Таким образом, при некоторой изобретательности эффективность поиска можно резко повысить.

5.2. Деление интервала пополам

Пользуясь тем же приемом, но вычисляя значения функций в подынтервалах неодинаковое число раз, можно дополнительно повысить эффективность поиска. Вычисляя N значений функция на i последовательно сужаемых интервалах, получим для коэф­фициента дробления интервала неопределенности

При таком методе поиска целевую функцию приходится вычислять J раз, причем J=Ni. Весьма заманчиво найти оптималь­ное значение N, при котором J при заданном f минимально.

Рис. 5.4 Определение оптимального числа вычислений целевой функции при применении метода деления интервала пополам

С помощью соотношения i=J/N и выражения для интервала неопределенности можно найти J:

Рис. 5.5 Первый шаг при применении метода деления интервала пополам

Если нанести значения J/ln(1/f) на график (рис. 5.4), оказывается,

что минимум расположен где-то вблизи N=3. Так как функция всегда вычисляется целое число раз, то в качестве оптимального примем значение N=3. При этом на каждом интервале f=0,5.

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