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


 

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

16709. ВОПРОСЫ О ПУБЛИЧНОЙ ДОСТОВЕРНОСТИ ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРАВ НА НЕДВИЖИМОЕ ИМУЩЕСТВО И СДЕЛОК С НИМ 100.5 KB
  Е.Ю. ПЕТРОВ К ВОПРОСУ О ПУБЛИЧНОЙ ДОСТОВЕРНОСТИ ГОСУДАРСТВЕННОЙ РЕГИСТРАЦИИ ПРАВ НА НЕДВИЖИМОЕ ИМУЩЕСТВО И СДЕЛОК С НИМ Государственная регистрация прав на недвижимое имущество и сделок с ним далее по тексту государственная регистрация государственная регистрац
16710. АКЦИОНЕРНЫЕ ОБЩЕСТВА ПО ГРАЖДАНСКОМУ ПРАВУ НИДЕРЛАНДОВ 45.5 KB
  Томас Кейзер АКЦИОНЕРНЫЕ ОБЩЕСТВА ПО ГРАЖДАНСКОМУ ПРАВУ НИДЕРЛАНДОВ Место акционерных обществ в системе юридических лиц Правовое положение юридических лиц в Нидерландах определено в части 2 Гражданского кодекса. Кроме того часть 7а Гражданского кодекс...
16711. ГРАЖДАНСКИЙ КОДЕКС РОССИЙСКОЙ ФЕДЕРАЦИИ И ГРАЖДАНСКОЕ ЗАКОНОДАТЕЛЬСТВО 71.5 KB
  В. С. ЯКУШЕВ ГРАЖДАНСКИЙ КОДЕКС РОССИЙСКОЙ ФЕДЕРАЦИИ И ГРАЖДАНСКОЕ ЗАКОНОДАТЕЛЬСТВО Опыт работы Федерального Собрания РФ показывает что главное направление в формировании новой системы права России кодификация принятие не отдельных законов а кодексов которым и ...
16712. Абсорбшен-костинг: учет, калькулирование и принятие решений 59.5 KB
  Абсорбшенкостинг: учет калькулирование и принятие решений Определение себестоимости производства единицы продукции одна из основных учетных задач так как себестоимость служит базой для установления цены и информация о ней се лежит в основе управлен...
16713. Антиинфляционные подгузники, или Wealth management 64.5 KB
  Антиинфляционные подгузники или Wealth management Экономика и жизнь № 29 2008 С. Суранов Как сберечь свои капиталы в условиях высокой инфляции в России ЭЖ при помощи экспертов финансового рынка предлагает некоторые возможные варианты инвестир
16714. Антикризисные услуги Отечественному бизнесу не нужен аутсорсинг 54 KB
  Антикризисные услуги Отечественному бизнесу не нужен аутсорсинг Отечественный рынок рекрутинга развивается по своим правилам. Просто применить западные технологии на нем не получится. Российские заказчи
16715. ПРОБЛЕМЫ ПЕРЕХОДА ОТ ФИНАНСОВОГО КОНТРОЛЯ К АУДИТУ ЭФФЕКТИВНОСТИ ДОЛГОВЫХ ОБЯЗАТЕЛЬСТВ 77.7 KB
  Л. Брагинская ПРОБЛЕМЫ ПЕРЕХОДА ОТ ФИНАНСОВОГО КОНТРОЛЯ К АУДИТУ ЭФФЕКТИВНОСТИ ДОЛГОВЫХ ОБЯЗАТЕЛЬСТВ. В стратегических документах Правительства Российской Федерации определяющих долговую политику страны говорится о том что в целях повышения эффективности долг...
16716. Economics in China 21.96 KB
  Economics in China. The official support of a marketbased economy that came from Deng Xiao Ping in 1992 has resulted in a more open system of trade for China and subsequently a huge growth spurt in China's economy. The economic reforms which Deng instigated culminated in a socialist market economy a term which was actually incorporated into the Chinese constitution during the National People's Congress in March 1993. Since that time China's economy has experienced a substantial boost in...
16717. Planned economy 41.9 KB
  Planned economy This article is about an economic system controlled or directed by the state. For proposed economic systems that employs participatory or democratic planning Planned economy or command economy is an economic system in which the state directs the economy.[1] It is an economic system in which the central government controls industry such that it makes major decisions...