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

Наконец, условия определяются величиной области задания функции f, т. е. длиной L отрезка между х' и х".

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

1) Насколько осуществима поставленная цель при данных возможностях и в данных условиях? Приме­нительно к интересующему нас вопросу это означает следующее.

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

2) Какими возможностями необходимо располагать, чтобы осуществить поставленную цель в данных условиях?

В нашей задаче этот вопрос можно конкретизиро­вать так. Пусть мы хотим определить минимизирую­щую функцию f точку с заданной точностью ε, т. е. указать такое х, что расположено между х — ε и х + ε. Сколько определений значений функции f для этого необходимо произвести и как эти определения организовать?

3) В каких условиях данные возможности доста­точны для достижения поставленной цели?

В данном случае речь идет о нахождении наиболь­шего интервала L изменения функции f (т. е. наиболь­шего значения разности х" — х'), для которого существует способ определения минимизирующей f точки с заданной точностью ε за п наблюдений.

4. Строго говоря, нам придется сейчас иметь дело не с одной задачей, а с двумя.

Во-первых, речь может идти о нахождении мини­мизирующей точки вместе с тем значением f(x), которое функция в этой точке принимает.

Во-вторых, мы можем интересоваться только самой точкой , оставаясь безразличным к значению f(x).

Совершенно ясно, что в первой из этих задач (будем далее ее называть задачей А) наши цели шире, чем во второй (которую мы назовем задачей Б). Поэтому естественно ожидать:

- что при заданных возможностях и условиях цели задачи А удастся осуществить в меньшей степени, чем цели задачи Б (при данном числе п и длине L в за­даче Б удается получить меньшее ε, чем в задаче А);

- что для осуществления в равной мере целей обеих задач при одинаковых условиях в задаче А необхо­димы большие возможности (при одной и той же по­грешности ε и одинаковых длинах L интервалов изме­нения функции в задаче А необходимо большее п);

- что одинаковое осуществление целей при равных возможностях требует в задаче А более легких усло­вий (данные ε и п в задаче А совместимы лишь с мень­шими значениями L, чем в за­даче Б).

5. Чтобы сделать сформули­рованные задачи математиче­ски вполне четкими, необхо­димо разъяснить следующее важное обстоятельство.

Допустим, что мы интере­суемся возможностями определения минимизирующей точки в отрезке длины L (очевидно, мы можем считать нача­лом этого отрезка точку 0 на оси координат, а кон­цом— точку L) с точностью ε. Будем считать, что мы решаем задачу А, т. е. что интересует нас вместе со значением f().

Предположим, что мы избрали следующий способ определения х.

Выберем совершенно произвольно некоторое между 0 и L и определим значения функции f в точ­ках х — ε, х и х + ε, т. е. вычислим величины

(рис. 5).

Рис. 5.

При всей произвольности вы­бора х мы считаем, что так что значение функции f(x — ε) можно фактически вы­числить; точно так же мы принимаем, что Вполне может случиться, что

Это значит, что функция f, убывающая в х — ε, при переходе к х + ε начинает возрастать. Но переход от убывания функции к возрастанию неизбежно связан с ее прохождением через наименьшее значение. В дан­ном случае это наименьшее значение функции f долж­но достигаться на некотором , лежащем между х — ε, х и х + ε.

Поэтому х будет отстоять от не более, чем на ε, и х окажется как раз тем прибли­женным значением , которое мы ищем. В этом случае опре­деление искомого осуществ­ляется в результате трех наблюдений. Такое может случиться. Однако никакой гарантии того, что это действительно произойдет, мы не имеем. Более того, если длина L отрезка велика, а ε малó, то наступление этого явления может пока­заться довольно неожиданным. Наоборот, в этом слу­чае вполне правдоподобно, что вблизи трех выбран­ных нами точек функция f будет принимать сравни­тельно большие значения, а минимума своего она будет достигать где-нибудь совсем в другом месте. Следовательно, трех наблюдений может хватить, а может и не хватить.

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

(1)

до тех пор, пока не дойдем до такого f(rε), что (r + 1)ε будет больше, чем L (рис. 6).

Рис. 6.

Ясно, что то kε, для которого значение функции будет наименьшим в последовательности (1), и окажется искомым.

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

Поэтому наилучший в наихудших условиях план называют минимаксимальным планом, или пла­ном минимакса. Мы будем этот план называть опти­мальным.

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

6. Важно отметить, что не для всякой задачи поиска существуют оптимальные планы. Так, напри­мер, в задаче Б оптимального плана нет. В самом деле, пусть L = 2 и п = 2. Какую точ­ное ε определения мы можем при этом гарантировать?

Будем считать концами нашего отрезка числа 0 и 2. Возьмем произвольно малое положительное ε и вычислим значения функции f в точках 1 — ε и 1 + ε. Если при этом

то искомый минимум должен лежать между нулем и 1 + ε, а если

то расположено между 1—ε и 2.

Положим в первом случае

а во втором —

В наихудшем случае так определяемое отли­чается от истинного минимума функции f на

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