Минимизация функции методом ломаных и методом касательных

 

Министерство сельского  хозяйства РФ

Федеральное государственное  бюджетное образовательное учреждение

Высшего профессионального  образования 

Пермская ГСХА имени академика  Д.Н.Прянишникова.

 

Кафедра ИТАП

 

КУРСОВАЯ РАБОТА

по дисциплине:

«Прикладные методы оптимизации»

на тему:

«Минимизация функции методом ломаных и методом касательных»

 

                                                                             Выполнила:

                                                      студентка гр. Пиб-31

                                            Девятых К. К.

 

                                                                            Проверила:

                                                                             К. Т. Н., доцент

                                                                             Бояршинова Ирина Николаевна

 Оценка

___________

 

 

Пермь 2013

Содержание

Введение                                                                                                               3

1. Теоретическая часть                                                                                      

1.1 Описание метода ломаных                                                                       5

   1.2 Описание метода касательных                                                                10

 

2 Практическая часть                                                                                       

   2.1 Постановка задачи                                                                                     11

  2.2 Решение задачи в Pascal                                                                           11 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Формулировка математической задачи оптимизации

В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом:

Минимизировать (максимизировать) целевую  функцию с учетом ограничений  на управляемые переменные. Под минимизацией (максимизацией) функции n переменных f(x)=f(x1, ... ,xn) на заданном множестве U n-мерного векторного пространства En понимается определение хотя бы одной из точек минимума (максимума) этой функции на множестве U, а также, если это необходимо, и минимального (максимального) на U значения f(x). При записи математических задач оптимизации в общем виде обычно используется следующая символика:

f(x) -> min (max),

x принадлежит U,

где f(x) - целевая функция, а U - допустимое множество, заданное ограничениями  на управляемые переменные. 

 

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

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

f(x) -> min ,

x принадлежит [a, b].

Максимизация целевой функции  эквивалента минимизации ( f(x) -> max ) эквивалентна минимизации противоположной  величины ( -f(x) -> min ), поэтому, не умаляя общности можно рассматривать только задачи минимизации. К математическим задачам одномерной минимизации приводят прикладные задачи оптимизации с одной управляемой переменной. Кроме того, необходимость в минимизации функций одной переменной возникает при реализации некоторых методов решения более сложных задач оптимизации.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Теоретическая часть

1. Описание метода ломаных

Метод ломаных.

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

Опр. Функция удовлетворяет условиям Липшица на отрезке , если существует константа : ,    (1)

где  . Здесь - константа Липшица на отрезке для функции .

Из определения  , что:

1. Функция - Липшицева на отрезке   - непрерывна на отрезке ;
2. Геометрический  смысл: условие (1) означает, что угловой коэффициент (тангенс угла наклона) хорды, соединяющей две точки и графика функции не превышает значение   , для .

Рассмотрим  функцию  , где - фиксировано, .

Рассмотрим график:

                                                                     1).

2). .

 

 

 

\

 

 

График функции  будет всегда выше графика функции , т.е. для любого фиксированного и .

Докажем этот факт:

  (*)

0 по определению

и причем - одна общая точка. Это свойство используется в методе ломаных.

 

Описание алгоритма  метода ломаных.

1. Выбираем произвольно точку и строим функцию ;
2. Следующая  точка выбирается из условия (очевидно, что,  или );
3. Строится функция ;
4. Очередная точка находится как ;
5. Рассмотрим шаг , т. - известны, т.е.  , а определяем из условия и строим ;
6. Процесс останавливается по достижении точности: (тип 1) или (тип 2).

Метод описан.

 

 

 

 

 

 

 

Рассмотрим график.

 

- является кусочно-линейной  функцией и график ее представляет  собой непрерывную ломаную линию,  состоящую  из отрезков прямых  с угловым наклоном  , причем     удовлетворяет опр1 c  той же L , что и функция .

 

Свойства семейства  ломаных :

1. Получаем ;
2. Очевидно, что   ;

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

 

Докажем, что при  , т.е. последовательность , является минимизирующей.

 

Теорема ( о сходимости метода ломаных).

Пусть - произвольная функция, удовлетворяющая условию Липшица на отрезке с константой Липшица L . Тогда последовательность  , получаемая с помощью указанного метода ломаных такова, что:

1. , причем справедлива оценка: (*)
2. сходится ко множеству точек минимума функции на отрезке , т.е.

Доказательство.

1. Возьмем произвольно  , и фиксируем ее. И докажем, что последовательность просто сходится.

 

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

Пусть - какая-либо предельная точка последовательности , т.к. последовательность ограничена слева a и справа b, то по теореме Больцано - Вейерштрасса должна существовать  последовательность , которая будет сходиться к   , , . Заметим, что :

Тогда, при и . Теперь положим и , тогда получим:

, отсюда при  имеем:

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

2. т.к. (применяя теорему Вейерштрасса о минимизирующей последовательности). Теорема доказана.

Как вычислить  константу Липшица L.

Теорема. Пусть функция , т.е. дифференцируема на и ее производная ограничена на отрезке . Тогда функция удовлетворяет условию (1) на с константой .

Доказательство.

По формуле конечных приращений для  имеем , где . Отсюда из ограниченности следует утверждение теоремы. Теорема доказана.

 

Рассмотрим метод вычисления константы Липшица.

Возьмем число  и .

Обозначим:

Утверждение.  .

Замечание. В случае, если найденное значение константы L завышено, то это приводит к увеличению количества итераций, а если занижена, то приводит к увеличению погрешности метода.

 

 

 

 

 

 

 

2. Описание метода касательных  

 

Метод касательных.

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

Область применения – только выпуклые функции.

Функция f(x) называется выпуклой на [a,b], если для любых точек и из этого отрезка и для любого числа , выполняется неравенство:

f ()+(1- f(

 

Пусть функция выпуклая на отрезке [a,b]

1. Выбираем произвольную точку и составляет вспомогательную функцию

           

           

Выбираем min

 

2. Строим вспомогательную 

}

Выбираем  min

 

2 Практическая часть

2.1 Постановка задачи

 

Найти минимум функции методом  касательных.

F(x)=1/3 x³ -5x³+x * ln(x),  на отрезке [1,5;2], вычисления производить с точностью ε = 0.0000001

 

2.2 Решение задачи

var e,x0,x1,y,p,p0,p1,min,t1,t2,y1,y2,x:real;

    n:integer;

  function f(x:real):real; // вычисление заданной функции

    begin

      result:=1/3 * power(x,3) - 5*x +x* ln(x);

    end;

  function f1(x:real):real; // вычисление производной

    begin

      result:=power(x,2)-4+ ln(x);

    end;

begin

  cls;

  e:=0.0000001;

  n:=0;

  x0:=1.5;

  x1:=2;

  min:=(f(x1)-f1(x1)*x1-f(x0)+f1(x0)*x0)/(f1(x0)-f1(x1));{находим  точку пересечения 2 касательных}

           p0:=f1(x0);

         p1:=f1(x1);

         p:=f1(min);

  repeat

    inc(n);

    t1:=(f(min)-p*(min)-f(x0)+p0*x0)/(p0-p);{находим  точку пересечения новой касательной  к 1 прямой}

    t2:=(f(min)-p*(min)-f(x1)+p1*x1)/(p1-p);{находим  точку пересечения новой касательной  к 2 прямой}

    y1:=f(t1);y2:=f(t2);

    if y2<y1 then

    begin

         x0:=min;

         min:=t2;

         p0:=f1(x0);