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 используются только равенства, то это .


 

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

34106. Уголовная ответственность за порчу земель (ст. 254 УК РФ) 22.5 KB
  Уголовная ответственность за порчу земель ст. Порча земель ст. За порчу земель предусмотрена как административная так и уголовная ответственность в зависимости от последствий. Порча земель это ухудшение физических и биологических свойств почвы снижение ценности земли.
34107. Порядок установления и взимания земельного налога 32 KB
  Существует две формы платы за землю: земельный налог; арендная плата. Земельный налог. Земельный налог относится к категории местных налогов. Земельный налог устанавливается исключительно нормативноправовыми актами органов местного самоуправления либо законами представительных органов Москвы и СанктПетербурга.
34108. Арендная плата и нормативная цена земли 40.5 KB
  Оценка земли виды стоимости. Существует 4 вида стоимости цены: нормативная цена; кадастровая стоимость; рыночная стоимость; выкупная цена. В любом случае нормативная цена земельного участка не должна быть более 75 от рыночной стоимости аналогичных земельных участков. были внесены изменения в Закон “Об оценке и оценочной стоимости в РФ†и впервые кадастровая стоимость получила закрепление на законодательном уровне.
34109. Пять базовых техник психотерапии:суггестия, абреакция, манипуляция, разъяснение, интерпретация 95 KB
  Абреакция как основа эмоционального состояния и способности пациента справляться с ним. кратко говоря различных ментальных процессов терапевтом индивидуум в авторитетном положении у пациента индивидуума в зависимом положении независимо от или с исключением рационального или критического реалистического мышления последнего. Техническое использование суггестии может быть главным образом формальным к примеру чтобы в общем индуцировать пациента к фантазии или сну какой бы не была эта фантазия или сон или главным образом...
34110. Понятие регрессии. Роль регрессии в развитии психоаналитической терапии 48 KB
  Понятие регрессии. Роль регрессии в развитии психоаналитической терапии. Процесс регрессии как временный постоянный защитный топический ситуационный. Патологическая и нормальная регрессии их формирование в процессе развития и их значение в функционировании психического аппарата и формировании различных уровней психопатологии.
34111. Принцип психоаналитической нейтральности. Реакции аналитика на пациента: рациональные аффективные, комплиментарные, эмпатические, контрпереносные 48 KB
  Принцип психоаналитической нейтральности. В данной теме особое внимание следует уделить пониманию центрального базового значения психоаналитического понимания нейтральности. Слово НЕЙТРАЛЬНОСТЬ neutrlity и концепция ПСИХОАНАЛИТИЧЕСКОЙ НЕЙТРАЛЬНОСТИ были амбивалентными с самого момента рождения психоанализа. Приветствуемая одно время как настолько фундаментальная что принимается как данность к нейтральности тут же стали тихо относиться как мифу.
34112. Психоаналитическое понятие тревоги и ее типы 85.5 KB
  Тревога и процесс регрессии в психоаналитической ситуации. Тревога рассматривается как архаичный аффект оторвавшийся от первоначального смыслового контекста. Объективная тревога это тревога вызванная известной опасностью. Невротическая тревога вызвана неизвестной опасностью.
34113. Неспецифические аспекты психоаналитической терапии 77 KB
  В данной теме необходимо сформировать четкое представление о неспецифических формах взаимодействия аналитика и пациента. Данный раздел дает четкое представление о вспомогательных формах и методах во взаимодействии аналитика и пациента в рамках психоаналитической терапии. Если он будет это делать с неохотой аналитик может сказать что его интересуют факты. Пациента увязнувшего в неискренней похвале своих родителей можно спросить: Ваши родители действительно замечательные люди Расспрашивание для прояснения очевидности: Вместо того чтобы...
34114. Роль сновидений в психоаналитической терапии и техника работы с ними 73 KB
  Работа сновидения. Роль сновидения в работе психического аппарата. Развитие понимание сновидения и его роли в терапевтическом процессе от З. Классические подходы к пониманию сновидения его роль в общей структуре психики.