Упражнения.

Глава 5.Численные методы решения задач одномерной оптимизации.

Задача условной минимизации.

Обобщенная задача оптимизации.

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

Число (или символ -¥) называют точной нижней гранью или инфимумомфункции ¦ на множестве X, если неравенство £ ¦ (x) имеет место для всех хÎХ и, кроме того, для любого числа ¦’>найдётся точка х’ÎХ такая, что верно неравенство ¦(x’)<¦’. Тот факт, что - точная нижняя грань функции ¦ на множестве Х, записывают в виде

(4.8)

Аналогично вводится понятие точной верхней грани. Число (или символ +¥) называютточной верхней гранью или супремумом функции ¦ на множестве Х, если неравенство³¦ (x) справедливо для всех хÎХ и для любого числа ¦’ < найдётся точка х’ÎХ такая, что верно неравенство ¦(x’) >¦’. Для точной верхней грани используется обозначение

Как указано выше, не всегда можно указать точку, в которой точная грань достигается, т.е. точку , для которой .Поэтому в обобщённой задаче минимизации под решением понимают не отдельную точку, как это имеет место в обычной задаче оптимизации, а последовательность точек, , к =1,2,…,такую, что

(4.9)

Эта последовательность всегда существует и называется, минимизирующей последовательностью.

Таким образом, обобщённая задача минимизации целевой функции ¦ на множестве Х заключается в отыскании числа (или символа -¥)и последовательности точек , , к =1,2,…,таких что выполняются равенства (4.8) ... (4.9).

Задача (4.1) называется задачей условной оптимизации (условной задачей), если Х-собственное подмножество пространства .

Рассмотрим конечномерную задачу условной минимизации с ограничениями типа равенств и неравенств:

f(x)inf,

g_i(x)=0, j=1,2...,k,

g_i(x)0, i=1,2,...,m,

xEⁿ

Предположим, что задача является гладкой, т.е. функции f(x), g_i(x), j=1,2...,k, g_i(x), i=1,2,...,m –непрерывно-дифференцируемы по х.

Допустимое множество этой задачи имеет вид

X=xg_i(x)=0, j=1,2...,k, g_i(x)0, i=1,2,...,m

Для такой задачи сохраняют силу утверждения теорем 4.1…4.3,если её локальное решение х* является внутренней точкой допустимого множества Х(х*ÎintX). Для многих условных задач минимум достигается на границе, в силу чего для них классические результаты анализа неприемлемы. Вообще при переходе от безусловных задач к условным все вопросы оптимизации становятся более сложными.

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

Для геометрической интерпретации данной двумерной задачи необходимо изобразить её допустимое множество Х и несколько характерных линий уровня целевой фунции ¦ (рис.4.7.).

Рис.4.7 Геометрическая интерпритация задача оптимизации.

Чтобы отразить характер изменения функции, у данной линии уровня полезно ставить знак “+ “ с той стороны, где ¦ принимает значения большие a, и знак “ - “ с другой. Если функция ¦ дифференцируема в точке х, то градиент ¦’(x) ортогонален к проходящей через х линии уровня и направлен (если естественно ¦’(x)¹0) в сторону возрастания функции, т.е. в сторону знака “+”. В геометрическом плане поиск глобального решения сводится к нахождению минимального числа среди всех a таких, что линия уровня имеет непустое пересечение с Х. При этом любая точка х*Îявляется глобальным решением задачи, а сама - минимальным значением функции ¦ на Х. Возможны два случая: х* лежит внутри (рис.4.9,а) и на границе (рис. 4.9,б) множества Х.

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

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

5.1. Прямые методы.

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

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию ¦(), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию ¦() унимодальной на отрезке [a; b].

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

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

Пусть ¦(x)ÎQ[a; b],

где Q[a; b] - множество унимодальных функций на отрезке [a; b].

Требуется найти какую-либо из точек минимума * функции f() на отрезке [a; b] с абсолютной погрешностью e>0. Разобьем [a; b] на n равных частей точками деления

, i=0,1,2,...,n,