40843

Методы прямого поиска в задачах одномерной минимизации

Лекция

Математика и математический анализ

Найти минимум функции одной переменной нет анализа заданной функции. Больше ничего о функции неизвестно. Можно вычислить измерить значения функции в точках. После n nчетно экспериментов min функции лежит в интервале .

Русский

2013-10-22

576 KB

7 чел.

  1.  Методы прямого поиска в задачах одномерной минимизации.

min-?

xk+1 = xk + tkSk , где Sk -направление.

Необходимо определить tk.

(t) = f(xk + tSk)- найти минимум функции одной переменной (нет анализа заданной функции). Будем искать точку локального минимума, поэтому ограничимся функциями, имеющими один минимум. Больше ничего о функции неизвестно. Можно вычислить (измерить) значения функции в точках.

1. Метод квадратичной интерполяции.

Пусть функция задана на прямой, даны при этом точки a<b<c, и , точка минимума в [a, c]

Через эти точки проведем параболу:

Положим:

, т.е. имеем 3 уравнения и 3 неизвестных g0, g1, g2.

Находим g0, g1, g2

Рассмотрим два случая:

  1.  
  2.  

Так поступаем до тех пор, пока точка не окажется в достаточно малой окрестности одной из трех точек a, b, c. После чего такую точку считаем точкой минимума.

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

2. Метод дихотомии ( половинного деления.).

Если мы вычислим значения f в двух точках x1,x2 , то станет возможным исключение из рассмотрения некоторого множества точек, на котором гарантировано нет минимума, то есть имея измерения в двух точках можем сократить интервал поиска.

Как лучше выбирать точки, чтобы процесс быстрее сходился?

В методе дихотомии предлагается (отрезок [0,1] ).

Остается один из интервалов:. Выберем 3-й и 4-й эксперимент на -пару в середине оставшегося интервала. После n (n-четно) экспериментов min функции лежит в интервале .

Здесь каждый раз два эксперимента, но можно один, а  в качестве другого брать один из предыдущих.


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

Интервал [a,b], вычислить функцию в точках .

На интервале  [a,b] расположен минимум функции.

, где F1 и F2 некоторые числа 0<F1<1, 0<F2<1.

Анализируем перегибы функции внутри интервала, и также, как  раньше, заменяем отрезок [a,b] на или . Идея метода в том чтобы после замены, необходимо было вычислить только одну точку при гарантированном уменьшении длины отрезка, т.е.

 , так как

 (после замены отрезок уменьшится в 1/ F2 =

В новом отрезке должно быть(по правилу «золотого» сечения): так как

Тогда так как , , то.

Таким образом, уменьшение интервала в 1/ F2 =  раз достигается с помощью вычисления функции в одной новой точке (см. процедуру выполнения). После n экспериментов имеем интервал неопределенности:

 .

 В пересчете на одно измерение этот метод лучше дихотомии.

Процедура выполнения:

Рассмотрим [a,b], вычислить функцию в точках .

  1.   
  2.  

В 1) и 2) появилась только одна новая точка. И так далее, пока длина отрезка [a,b] не станет меньше заданной величины.


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

Пусть у нас существует ограничение на количество вычисляемых точек N.

Как выбирать средние точки , чтобы максимально уменьшить интервал, внутри которого лежит точка min?

, к- номер итерации.

Fj - числа Фибоначчи, обладающие свойством.

Fk+2 = Fk+1+ Fk

Два первых: 1;1

Как метод Фибоначчи связан с методом «золотого» сечения?

.

То есть асимптотически один метод переходит в другой. Окончательный интервал в методе «золотого» сечения всегда на 17% больше чем в методе Фибоначчи. Если количество измерений не задано, то используется метод «золотого» сечения, если задано - то Фибоначчи.

3. Условная минимизация.

  1.  Задача нелинейного программирования.

min f -?, на множестве X.

Нелинейная область: - допустимое множество.

ji- некоторые функции. 

2.1.1 Ограничения типа равенства.

рассмотрим найти .

Ïóñòü g разрешима относительно x1, то есть x1= (x2).

Тогда  

Пусть f,  - дифференцируемы. Тогда условие экстремальности:  , так как


Тогда:

, из определения

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

F(x,)=f+g.

 Тогда необходимое условие min функции f(x1,x2) при наличии ограничений может быть записано следующим образом:

2.1.2 Ограничения типа неравенств.

Пусть:

                                                          область, которая разрешена ограничениями

    g1(x)=0                          f                              g2(x)=0  

                                                                                       точка минимума

                                                                                    f = const (линия уровня)                  

                           g1                                     g2

                                                   -f  

                                            

                                          

                                           конус

Тогда -f представляется так:

-f = 1g1+2g2, где 10, 20.(1)

-f расположен в конусе, образованном g1 и g2.

  1.  переписывается так:

f + , где i - множители Лагранжа.

По рисунку i gi (x) = 0 (мы попадаем на границу). Тогда можно рассматривать функцию Лагранжа f + и считать стационарную точку так, будто нет ограничений. Переход от равенств к неравенствам накладывает ограничения на i

(i 0). Пусть f  направлен иначе (-f находится не в конусе), тогда иллюстрация.

Иллюстрация:

                               S                                g2(x) = 0

    g1(x) = 0                               

                 

                -f

                                                             

                             g1              конус             g2 

 

В этом случае есть выбор S, которое составляет острый угол с -f и тупой с g1 иg2.

То есть, если пойдем по S, то наши ограничения будут выполняться (в тоже время функция будет убывать), и эта точка не будет extr.

Таким образом, чтобы точка была экстремальной, антиградиент должен лежать в соответствующем конусе.

Рассмотрим другую точку на g2(x) = 0.  

                                   f1                 g2(x) = 0

                                                                    g2

                                                         

Если f1 направлен так, как показано, то точка будет подозрением на extr. Необходимое условие записывается также, но в этом случае  1=0 (то есть не рассматривается g1).

Пусть x*- экстремальная точка, свяжем с x* множество индексов активных ограничений :

Лемма: 

Ïóñòü - некоторый вектор, удовлетворяющий следующим свойствам:

(*),тогда точка x* - не экстремальная.


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

Идея:

Показать, что на луче с вершиной x* и направлением S будут лежать вблизи вершины некоторые точки, которые будут допустимыми и в них целевая функция строго меньше чем в точке x*

Пусть >0

(1)

(разложение в полином Тейлора)

тогда  (см. определение I(x*)).

Тогда (см.(1)).

Если , то . Отсюда (- достаточно мало).

Таким образом, при достаточно малых , точка x* + S- допустима, кроме этого функция f на этом луче убывает. Таким образом точка x* не является экстремальной. Для экстремальной точки x* система неравенств (*) - несовместна.

Лемма Фаркаша:

Пусть  есть матрица А(m  n), тогда справедливо одно из следующих двух условий :

  1.  
  2.  

Без доказательства.

Теорема Каруша-Джона:

Пусть x* - экстремальная точка задачи нелинейного программирования.

Пусть в точке x* градиенты функций, соответствующие активным ограничениям, линейно- независимы, тогда существуют 1,...,m 0 (не все нулевые), для которых выполняются следующее условия:

- условие дополняющей нежесткости.

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

Как показано выше, не существует такого S, для которого выполнялись бы следующие неравенства:

, для любого iI(x*).

Воспользуемся леммой Фаркаша, составим матрицу:

, iI(x*).

Не существует S такого, ÷òî AS<0. Следовательно, существуют  такие, что (по лемме Фаркаша) выполняются условия:

( x*) (i: = 0, если iI(x*)).

Для активных ограничений gi = 0, для неактивных отсюда i = 0. Тогда

 i gi (x*) = 0,, так как если бы он был равен 0 ,то градиенты, соответствующих активных ограничений, были бы линейно- зависимы, что противоречит условию. Разделим (*) на  0 и получим требуемое утверждение. Условие линейной независимости градиентов функций активных ограничений иногда называют условием регулярности.

2.2 Задача выпуклого программирования

min f = ?        X- допустимое множество

X=xRn, gi(x)0, i =1...m      f и все gi  выпуклы

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

Допустимое множество в задаче выпуклого программирования (ЗВП) выпукло

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

пусть x1,x2X ,      0,1

x1+(1-)x2X

воспользуемся свойством выпуклости gi :

gi(x1+(1-)x2) gi (x1) + (1-) gi(x2)0

тогда x1+(1-)x2X (см. опр. X),но рассматривается только отдельная gi.

Все допустимое множество X рассматривается как пересечение выпуклых

множеств X выпукло. 

Определение : 

Функцией Лагранжа в ЗВП называется функция

f(x)+ f(x) + (,g(x)), где  i0

справедлива теорема Каруша-Джона:

f(x)+=0, i gi(x*) = 0,    i=1..m

В случае выпуклости множества X условие линейной независимости векторов

gi(x), соответствующее активным ограничениям, можно заменить более просто

проверяемыми, а именно, так называемыми  условиями регулярности.

Существуют различные условия регулярности ограничений:

А) если для любого i (1 i m)

существует xiX : gi (xi) 0, то говорят, что множество X  удовлетворяет

условию регулярности.

Б) условие регулярности  Слейтера:

Существует  точка xX такая, что для любого i=1...m  gi(x)0.

Легко доказать эквивалентность условий  А и Б .  Очевидно, что из Б

следует А. Пусть теперь выпукла А. Выберем x =, =1,

0, i=1...mэто возможно, так как X выпукло.

Тогда Б следует из неравенства Иенсена.

Замечание:

Условие регулярности означает, что допустимое множество имеет внутреннюю

точку (то есть оно не вырождено в точку(общий случай))

Определение:

Пусть существует функция (x,y), точка (x,y) называется седловой точкой функции, если выполняется следующее неравенство: (x,y)(x,y)(x,y)

Теорема (о седловой точке):

Пусть функция Лагранжа ЗВП имеет седловую точку, то есть

f(x)+ f(x)+  f (x)+ 

для любого xRn, i 0, i =1...m

тогда x*- оптимальная точка (решение) ЗВП.

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

Из левого неравенства следует:

,i* 0, gi(x*)0(см. опред. X)

Так как -любое, то при =0 получится:

0(* , g(x*))=0.

Из правого неравенства имеем:

f(x*)+0 f(x)+  f(x)      xX

Тогда по определению оптимальной точки x*оптимальна.

Теорема Куна-Таккера:

Пусть в ЗВП выполнено условие регулярности Слейгера. Тогда  для того, чтобы

x* была оптимальной точкой ЗВП, необходимо и достаточно , чтобы для

некоторого вектора * с неотрицательными компонентами точка (x*,*)

была седловой точкой функции Лагранжа.

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

Достаточность следует из теоремы о седловой точке.

Необходимость -без доказательства.

  1.  Методы условной минимизации.
  2.  Метод  проекции градиенты.

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

xk+1= px (xk- f(xk)), где px проекция на X.

Пример:

Если X- круг, то проекция точки на X есть точка пересечения окружности и прямой, соединяющей центр и проектирующую точку. Чем сложнее область X, тем сложнее операция проектирования.

Метод обладает теми же свойствами, что и градиентный метод с постоянным шагом.

  1.  Метод условного градиента.

Движение в направлении -f(x0), находим минимум по этому направлению (). Произвольно выбираем x1 и вновь движение в соответствующем градиентном направлении и так далее.

В очередной точке xk  линеаризуют функцию  f(x) (в этом «условность» метода, то есть линеаризация и есть «условие» в названии). Затем решают задачу min линейной функции на X и найденную точку используют для выбора направления движения.

 

При этом предполагается:

  1.  Задача мин. линейной функции на X имеет решение.

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

Нужно указать правило выбора k. Можно k определить из условия наискорейшего спуска :

При определенных условиях : f(x*)- f* = o(1/k), где f* = min f(x) на X.


  1.  Метод модифицированной функции Лагранжа.

Соотношение (x* , ) (x* ,*) (x ,*)   xRn,   0

записывается так в случае функции Лагранжа.

(*) (x* ,*) = (x ,) = (x ,) = f(x*)

Если назвать x прямыми переменными, а двойственными, то видно, что прямые и двойственные переменные равноправны.

Доказательство (*):                         

1. (x ,)  (x ,*) = (x* ,*) = f(x*) + (*, g(x*))

(x ,) (x* ,) = (x* ,*) = f(x*)

То есть (x ,) = f(x*)

  1.  (x ,)  (x ,) = (x* ,*) = f(x*)

(x ,) (x* ,) = (x* ,*) = f(x*) отсюда следует

(x ,) = f(x*).

Теорема Куна- Таккера позволяет исходную задачу заменить задачей отыскания седловой точки функции Лагранжа, то есть задачи вида (x ,).

Можно показать, что седловая точка определяется соотношениями:

,где

Если на x наложены ограничения (x 0), то :

 

Существуют различные методы поиска седловой точки, например:


Метод Эрроу- Гурвица

Сходимость таких методов затруднена в общей ситуации.

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

- модифицированная функция Лагранжа.

  1.  некоторый параметр (штраф)

+ -  взятие положительной части.

Свойства модифицированной функции Лагранжа.

  1.  Если + k g(x)>0, то

- добавка (штраф) за то, что g(x)>0.

  1.  (функция Лагранжа),

иначе  

Метод модифицированной функции Лагранжа.

Метод сходится к (x* ,*) со скоростью геометрической прогрессии.

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

4.Метод штрафных функций.

Идея метода:

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

ЗНП:

min f(x), xX,

X = {xRn, gi(x) 0, i = 1...m


Определение:

Функция (x), определенная и непрерывная всюду в Rn , называется штрафной  функцией для рассматриваемой задачи с ограничениями, если:

Строится однопараметрическое семейство функций:

, где - скалярный параметр, принимающий строго положительные значения.

Алгоритм метода штрафных функций:

  1.  Выбираем убывающую последовательность  положительных чисел, такую, что .
  2.  Сопоставляем каждому к из этой последовательности соответствующую функцию семейства (x,). Получаем последовательность функций (x,1),..., (x,k).

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

    задача безусловной минимизации (одним из рассмотренных ранее методов) : 

    .

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

Применяются различные штрафные функции. Наиболее распространена следующая щтрафная функция:

, где  - «срезка» функции :

=0, если 0

=, если >0

или


2.4 Двойственность ЗВП

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

Введем функцию: g(x)=sup(x,), при 0

Тогда очевидно ,что

g(x) = f(x), если gi(x)0, i=1...m

g(x) =, в противном случае

Понятно, что (x,) = f(x)+(, g(x)),  

Поэтому исходная ЗВП может быть записана в виде:

min g(x)-?, при xRn 

Эту задачу принято называть прямой.

Поступим аналогичным образом, поменяв роль переменных и операций max и min. Обозначим h()= inf , при xRn

Задачу max h()-? при , называют двойственной.

Теорема двойственности:

Справедливы следующие соотношения двойственности: 

1) f(x)h()  xX,

2) Если выполнено условие т. Куна-Таккера, а пара (x*,*) является седловой точкой функции Лагранжа, то *-решение двойственной задачи.

* = argmax h(),при  и f(x* )=h(*)

3)Если для допустимых x*, * : f(x*)=h(*), то

x* = argmin f(x), при xX

* = argmax h(), при 0

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

1) f(x)f(x)+(,g(x))=(x,) inf(x,) = h(), при xRn

2) Для  всех 0 справедливо соотношение:

h(*)= inf(x ,*) =(x* , *)(x* ,) inf(x,) = h(),при xRn

Отсюда *-решение двойственной задачи.

Но (x, *) = f(x*)h(*)=f(x*)

3) На основании 1) f(x)h(*) = (2)) f(x*)h()

тогда x*- прямое решение, *- двойственное решение

Продемонстрируем двойственность ЗВП  на примере задачи линейного программирования (ЗЛП) , которая вкладывается в ЗВП.

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

2.4.1.Двойственность ЗЛП

X=xRn, x, Axbb- вектор размерности n, A- матрица размерности mn.

f(x) = (c, x)- целевая функция (линейна)

ЗЛП: min f(x)-?, при xX- прямая задача линейного программирования.

Построим функцию Лагранжа.

=(c, x)+( 1,b-Ax)+(  2,-x), 1Rm, 2Rn  (подгоняем под gi(x)0).

Тогда min(c, x) = max inf (c, x)+( 1, b-Ax)+( 2, -x), при 10, 20, xRn = (см. метод модификации функции Лагранжа) = max inf (c- AT1-2, x)+( b, 1) 

при 10, 20, xRn =

(1, Ax)=(AT2, x)

= max , при 10, 20

= max (b, 1) (при 10, 20, с=AT1+2)  = max (b, 1) (при 10, с AT1)

= max (b, ) = (c, x*), с AT,  0

max (b, ), с AT,  0 - двойственная ЗЛП.

Таким образом, решение исходной ЗЛП может быть сведено к решению новой ЗЛП : максимизация (b, ) по множеству, определенному условиями с AT,

 0.

Утверждения:

  1.  Вектор состояния   двойственной ЗЛП имеет размерность m- количество ограничений в исходной задаче (размерность вектора Ax).
  2.  Количество ограничений (кроме  0, неотрицательных) совпадает с размерностью вектора состояний в исходной задаче (вектора x).
  3.  Суммарное количество ограничений совпадает с (n + m) в обеих задачах.
  4.  Двойственная задача к двойственной дает исходную.

Когда какую задачу решать - зависит от числа ограничений и от размерности x.

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

Двойственные переменные можно рассматривать как коэффициент чувствительности целевой функции к изменению параметров задачи.

Пусть x* ,  *- решения прямой и двойственной задач, причем эти решения единственны (достиг. в одной точке минимум x и в одной максимум )

Тогда f(x*) = (b, *), несколько изменим b: bb+b min увеличился на

(b, *). При сдвиге b градиенты не изменились, i остались теми же.

Обозначим h(b) = min f(x), Ax b, x 0.

Тогда при малых b:

h(b+b) = h(b) + (b, *), следовательно при b 0 получим:

, для компонент векторов

  1.  Линейное программирование
  2.  Основные понятия

ЗЛП : min f(x), xX

X={x Rn : g j(x) 0, j = 1...m}, f, g j - линейны для любого j.

Таким образом ЗЛП- частный случай ЗНП.

Определение:

Функция называется линейной, если справедливо:

f(1x1+ 2x2) = 1f(x1) + 2f(x2), где iR, xiX.

В n-мерном пространстве линейная функция может быть определена так:

f(x) = (c,x)

f(x) = c1x1+ ....+ cnxn

Ограничения   

Расширим класс задач

,

то есть передвинуть область в n-мерном пространстве.

Определение:

Если при задании допустимого множества X используются только неравенства, то это ЗЛП в стандартной форме.

Определение:

Если при задании X используются только равенства, то это .


 

А также другие работы, которые могут Вас заинтересовать

59590. Позитивні та негативні емоції, їх значення для здоров’я 70.5 KB
  Гра Дружба починається з посмішки Запитання до учнів: Діти у вас є друзі Хто твій друг Як ви думаєте з чого починається дружба Я вам розкрию велику таємницю дружба починається з посмішки.
59591. Полеглим присвячується... 52 KB
  Степом степом йшли у бій солдати. Степом степом даль заволокло. Степом степом розгулись гармати Степом степом клекіт нароста. Степом степом падають солдати А кругом Шумлять жита.
59593. Правда, обпалена війною… (Аналіз кіноповісті Україна в огні) 37.5 KB
  Перевірка домашнього завдання і актуалізація опорних знань Україну в огнів називають Довженковою Голгофою. Що говорить сам Довженко у Щоденнику про це 31 січня 1944 р. Після дитячих версій можна запропонувати і версію Михайла Шевченка...
59594. Сценарій уроку: Правління в римській республіці 38.5 KB
  Учням ставляться запитання: Яка була роль консула та народного трибуна в державі Яким шляхом прагнув зробити кар’єру Гаймолодший Як йому вдалося стати консулом Чому Гаймолодший уплутався в корупцію У чому це виявилось З’ясувати з учнями як вони розуміють корупцію.
59595. Природа і людина в оповіданні Григора Тютюнника 41 KB
  Діти ви любите перебувати на лоні природи А чи вмієте милуватися нею Так само щиро любив свою землю свій край свою природу і Григір Тютюнник автор оповідання Лісова сторожка яке ми розглядатимемо на уроці. Будемо аналізувати персонажів твору...
59596. Проект: Квіти в творчості Тараса Григоровича Шевченка 36.5 KB
  Учити проведенню теоретичного дослідження; розвивати творчу уяву вміння робити підборку квітів складати їх в єдину композицію; сприяти вихованню у молоді любові до рідної землі історії культури мистецтва; вироблення навиків колективної праці; стимулювання інтересу учнів до творчості Т. Шевченка...
59598. Урок-гра подорож. Птахи нашого краю 54.5 KB
  Обладнання: малюнки із зображенням птахів інші ілюстрації картки Вулиця птахів виставка дитячих книжок про птахів ребуси кросворди. Отже ви здогадались що мова піде в нас про птахів нашого краю. Зараз ми з вами відправимось у дивну подорож вулицею Птахів у місто Природоград.