70102

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

Лабораторная работа

Информатика, кибернетика и программирование

Цель работа: знакомство с методами многомерной безусловной оптимизации первого и нулевого порядка и их освоение, сравнение эффективности применения этих методов конкретных целевых функций.

Русский

2014-10-15

373 KB

20 чел.

Лабораторная работа № 2

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

Цель работа: знакомство с методами многомерной безусловной оптимизации первого и нулевого порядка и их освоение, сравнение эффективности применения этих методов конкретных целевых функций.

  1.  Краткие теоретические сведения.

  1.  О  численных методах многомерной оптимизации.

Задача многомерной безусловной оптимизации формулируется в виде:

                                       min f(x),

                                        xX 

где x={x(1), x(2),…, x(n)} – точка в n-мерном пространстве X=IRn, то есть целевая функция f(x)=f(x(1),…,f(x(n)) – функция n аргументов.

Так же как и в первой лабораторной работе мы рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {xk}, удовлетворяющих условию f(x0)>f(x1)>…>f(xn)>… . Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {xk} вычисляются по формуле:   

хk+1 = xk + kpk, k=0,1,2,… ,   

где pk – направление спуска, k – длина шага в этом направлении.

Различные методы спуска отличаются друг от друга способами выбора направления спуска pk и длины шага k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции, относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д.

1.2. Градиентные методы.

1.2.1. Общая схема градиентного спуска.

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

xk+1 = xk - k f’(xk), k>0, k=0,1,2,… .

В координатной форме этот процесс записывается следующим образом:

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

1.2.2. Градиентный метод с постоянным шагом.

Основная проблема в градиентных методах – это выбор шага k. Достаточно малый шаг k обеспечивает убывание функции, то есть выполнение неравенства:

                                f(xk - k( xk))) < f(xk),

но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка условия убывания на каждой итерации является довольно трудоемкой, поэтому в методе градиентного спуска с постоянным шагом задают =k постоянным и достаточно малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим количеством итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент ).

Схема алгоритма

Шаг 1.

Задаются начальное приближение х0, постоянный шаг , условия останова алгоритма 3. Вычисляется значение градиента  – направление поиска. Присваивается к=0.

Шаг 2.

Определяется точка очередного эксперимента:

             хк+1 = хк - f’(xk),

или, в координатной форме:

Шаг 3.

Вычисляется значение градиента в точке хк+1:

                    ,

или, в координатной форме:

Шаг 4.

Если ||||3, то поиск заканчивается, при этом:

Иначе к=к+1 и переходим к шагу 2.

1.2.3. Градиентный метод с дроблением шага.

В методе градиентного спуска с дроблением шага величина шага к выбирается так, чтобы было выполнено неравенство:

                             f(xk-k)-f(xk)-k||||2,

             где 0<<1 – произвольно выбранная постоянная (одна и та же для всех итераций). Это требование на выбор шага к более жесткое, чем условие убывания, но имеет тот же смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства.

Процесс выбора шага протекает следующим образом. Выбираем число >0, одно и то же для всех итераций. На к-й итерации проверяем выполнение неравенства при к=. Если оно выполнено, полагаем к= и переходим к следующей итерации. Если нет, то шаг к дробим, например уменьшаем каждый раз в два раза, до тех пор, пока оно не выполнится.

Схема алгоритма

Шаг 1.

Задаются х0, 3, и начальное значение шага . Вычисляется значение градиента  – направление поиска. Присваивается к=0.

Шаг 2.

Проверяется условие: f(xk-)-f(xk) -||||2. Если выполняется, то переходим к шагу 3, иначе дробим значение (=/2) и повторяем шаг 2.

Шаг 3.

Определяется точка очередного эксперимента:    хк+1 = хк - .

Шаг 4.

Вычисляется значение градиента в точке хк+1: .

Шаг 5.

Если ||||3, то поиск заканчивается, при этом:

           Иначе к=к+1 и переходим к шагу 2.

1.2.4. Метод наискорейшего спуска.

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

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

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

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

Схема алгоритма

Шаг 1.

Задаются х0, 3. Вычисляется градиент , направление поиска.    

          Присваивается к=0.

Шаг 2.

Определяется точка очередного эксперимента:

                                  хк+1 = хк - к,

              где к – минимум задачи одномерной минимизации:

Шаг 3.

Вычисляется значение градиента в точке хк+1: .

Шаг 4.

Если ||||3, то поиск точки минимума заканчивается и полагается:

            Иначе к=к+1 и переход к шагу 2.

1.3.Метод покоординатного спуска.

Желание уменьшить объем вычислительной работы, требуемой для осуществления одной итерации метода наискорейшего спуска, привело к созданию методов покоординатного спуска.

Пусть                - начальное приближение. Вычислим частную производную по первой координате и примем:

      где е1={1,0,…,0}T – единичный вектор оси х(1). Следующая итерация состоит в вычислении точки х2 по формуле:

           где е2={0,1,0,…,0}T – единичный вектор оси х(2) и т. д.

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

    

Спуск по всем координатам составляет одну «внешнюю» итерацию. Пусть к – номер очередной внешней итерации, а j – номер той координаты, по которой производится спуск. Тогда формула, определяющая следующее приближение к точке минимума, имеет вид:

                   где к=0,1,2,… ;  j=1,2,…n.

В координатной форме формула выглядит так:

После j=n счетчик числа внешних итераций к увеличивается на единицу, а j принимает значение равное единице.

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

Схема алгоритма покоординатного спуска с постоянным шагом

Шаг 1.

При к=0 вводятся исходные данные х0, 1, .

Шаг 2.

Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки хkn по формуле:

Шаг 3.

Если ||x(k+1)nxkn||1, то поиск минимума заканчивается, причем:

Иначе к=к+1 и переходим к шагу 2.

Если же шаг к выбирается из условия минимума функции:

то мы получаем аналог метода наискорейшего спуска, называемый обычно методом Гаусса – Зейделя.

Схема метода Гаусса – Зейделя

Шаг 1.

При к=0 вводятся исходные данные х0, 1.

Шаг 2.

Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из  точки хkn по формулам:

     где kn+j-1 является решением задачи одномерной минимизации функции:

Шаг 3.

Если ||x(k+1)nxkn||1, то поиск минимума заканчивается, причем:

            Иначе к=к+1 и переходим к шагу 2.

1.4. Методы оврагов

1.4.1. Общая характеристика.

Градиентные методы медленно сходятся в тех случаях, когда поверхности уровня целевой функции f(x) сильно вытянуты. Этот факт известен в литературе как «эффект оврагов». Суть эффекта в том, что небольшие изменения одних переменных приводят к резкому изменению значений функции – эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дно оврага», функция меняется незначительно. На рисунке изображены линии уровня «овражной» функции траектория градиентного метода характеризуется довольно быстрым спуском на «дно оврага», и затем медленным зигзагообразным движением в точку минимума.

 

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

1.4.2. Эвристические алгоритмы.

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

Первая эвристическая схема содержит два основных этапа. Оба этапа представляют собой аналоги градиентного спуска с постоянным шагом. Только вместо градиента   используется вектор g(x), формируемый из координат , но на каждом из этапов по разным правилам.

На первом этапе задается малое число 1<<1 и используется градиентный спуск, где вместо градиента  берется вектор g(x)={g(1)(x),…,g(n)(x)}, который определяется следующим образом:

 

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

На втором этапе задается некоторое большое число 2>>1 и используется процедура спуска, где вместо градиента  берется вектор g(x)={g(1)(x),…,g(n)(x)}, который определяется следующим образом:

В этом случае перемещение происходит по «берегу» оврага вдоль его «дна». Как и на первом этапе, спуск продолжается до тех пор, пока метод не зациклится.

После выполнения первого и второго этапов принимается решение о завершении работы или продолжении. Для этого сравнивается норма разности предыдущей точки, то есть точки, которую мы имели до применения первого и второго этапов, с текущей точкой, то есть полученной после применения с точностью решения задачи 1. Если эта норма меньше 1 и норма градиента в текущей точке меньше 3, то поиск заканчивается и последняя вычисленная точка принимается за приближенное решение задачи. Иначе для текущей точки вновь повторяем первый и второй этапы и т. д.

Схема алгоритма

Шаг 1.

Задаются х0, 1, 3,1,2,1 – постоянный шаг пункта 1 и 2 – постоянный

         шаг пункта 2 (1<2). Присваивается к=0.

Шаг 2. (Первый этап).

Из точки хк осуществляется спуск на «дно оврага» с постоянным шагом   

          1. При спуске вычисление очередной точки осуществляется с          

         использованием   формул:

            xj+1 = xj - 1g(xj), где  g(x)={g(1)(x),…,g(n)(x)},

Пусть этот процесс остановится в точке xl.

Шаг 3. (Второй этап).

Из точки xl осуществляется спуск вдоль «дна оврага» с постоянным шагом 2. При спуске используются формулы: xj+1 = xj - 2g(xj), где

                  g(x)={g(1)(x),…,g(n)(x)},

Пусть этот процесс остановился в точке xm.

Шаг 4.

Если ||xkxm||  1 и ||||  3, то полагаем:

        и поиск минимума заканчивается.

Иначе k=m и переходим к шагу 2.

1.4.3. Овражные методы (Метод Гельфанда).

Вторая эвристическая схема, предложенная И.М. Гельфандом, состоит в следующем.

Пусть х0 и      - две произвольные близкие точки. Из х0 совершают обычный градиентный спуск с постоянным шагом и после нескольких итераций с малым шагом попадем в точку u0. Тоже самое делаем для точки      , получая точку     . Две точки u,     лежат в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг» в полученном направлении, перемещаясь «вдоль дна оврага» (шаг называют овражным шагом). В результате получаем точку х1. В ее окрестности выбираем точку        и повторяем процедуру.

Схема овражного метода 1.

Шаг 1.

   Вводятся начальное приближение х0, точность решения 1 и 3, шаг для      

   градиентного спуска, начальное значение для овражного шага. Из   точки х0  

   осуществляется градиентный спуск с постоянным шагом на дно оврага. В

   результате получается точка u0. Полагается к=0.

Шаг 2.

В окрестности хк берется точка      и из нее осуществляется градиентный  

   спуск. В результате получается точка      .    

Шаг 3.

Новая точка хк+1 определяется следующим образом. По формуле

или

вычисляется точка x'k+1. Из нее осуществляется градиентный спуск и мы получаем точку  . Если f()<f(uk), то полагаем xk+1= и uk+1=.

Иначе уменьшаем овражный шаг (например в 2 раза =/2)и повторяем шаг 3.

Шаг 4.

Если ||uk+1-uk||1 и ||||3, то полагаем:

и поиск минимума на этом заканчивается, иначе к=к+1 и переходим к шагу 2.

            Рассмотрим другую реализацию той же идеи.

Пусть х0 и х1 – две произвольные близкие точки. Как и в предыдущем случае, из каждой точки осуществим градиентные спуски с постоянным шагом . Получим точки u0 и u1, лежащие в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг» в полученном направлении. В результате получим точку х2. Из этой точки осуществим градиентный спуск и получим точку u2. А вот далее, для того чтобы осуществить «овражный шаг», берем предпоследнюю точку u1. Соединяя прямой точки u2 и u1, делаем шаг в полученном направлении и определяем х3. Дальше аналогичным образом вычисляются х45, … .

           

          

             Схема овражного метода 2

Шаг 1.

Задаются начальное приближение х0, точность решения 1 и 3, шаг для градиентного спуска, начальное значение для овражного шага.

Из точки х0 осуществляется градиентный спуск с постоянным шагом на «дно оврага». В результате получается точка u0.

В окрестности х0 берется точка х1, из которой тоже осуществляется градиентный спуск на «дно оврага». В результате получается точка u1. Полагается к=1. Если f(u0)<f(u1), то полагаем u0=u1, u1=u0. Если f(u0)>f(u1), то u0=u0, u1=u1.

Шаг 2.

Новая точка хк+1 определяется следующим образом. По формуле:

вычисляется точка x'k+1. Из нее осуществляется градиентный спуск и мы получаем точку  . Если f()<f(uk), то полагаем xk+1= и uk+1=.

Иначе уменьшаем овражный шаг (например в 2 раза =/2)и повторяем шаг 2.

Шаг 3.

Если ||uk+1-uk||1 и ||||3, то полагаем:

и поиск минимума на этом заканчивается, иначе к=к+1 и переходим к шагу 2.

1.5. Методы прямого поиска.

1.5.1. Общая характеристика.

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

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

1.5.2. Метод конфигураций (метод Хука и Дживса).

Алгоритм включает в себя два основных этапа поиска.

а) В начале обследуется окрестность выбранной точки (базисной точки), в результате находится приемлемое направление спуска;

б) Затем в этом направлении находится точка с наименьшим значением целевой функции. Таким образом находится новая базисная точка.

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

Схема алгоритма

Шаг 1.

Задаются начальное приближение (первая базисная точка)

                                      ,   начальный шаг h для поиска направления спуска, точность решения (предельное значение для шага h). Присваивается к=0.

Шаг 2. (Первый этап).

Определяется направление минимизации целевой функции f(x)=f(x(1),x(2),…,x(n)) в базисной точке                                                     .  Для этого последовательно дают приращение переменным x(j) в точке хк. Присвоим z=xk. Циклически даем приращение переменным x(j) и формируем z(j)=xk(j)+h, если f(z)<f(xk), если же нет, то z(j)=xk(j)-h, если f(z)<f(xk), иначе z(j)=xk(j). Так для всех j(j=1,2,…,n).

Шаг 3.

Если z=xk, то есть не определилось подходящее направление, то обследование окрестности базисной точки хк повторяется, но с меньшим шагом h (например, h=h/2).

Если h>, то перейти к шагу 2, то есть повторить обследование точки хк.

Если h, то поиск заканчивается, то есть достигнуто предельное значение для шага h и найти приемлемое направление спуска не удается. В этом случае полагается                          

Шаг 4. (Второй этап).

Если zxk, то требуется найти новую базисную точку в направлении   

  вектора z-xk: xk+1=xk + (z-xk), где - коэффициент «ускорения поиска».

Определяется такое значение =к, при котором достигается наименьшее значение целевой функции в выбранном направлении, то есть функции

            f(xk +(z-xk) = ().

В зависимости от способа выбора к возможны варианты метода:

а) к==const постоянная для всех итераций;

б) задается начальное 0=, а далее к=к-1, если f(xk+1)<f(xk), иначе дробим к, пока не выполнится это условие;

в) к определяется решением задачи одномерной минимизации функции ().

Таким образом определяется новая базисная точка xk+1=xk + (z-xk). Полагаем к=к+1 и поиск оптимального решения повторяется с шага 2.

1.5.3.Метод симплекса.

Под симплексом понимается n-мерный выпуклый многогранник n-мерного пространства, имеющий n+1 вершину. Для n=2 это треугольник, а при n=3 это тетраэдр.

Идея метода состоит в сравнении значений функции в n+1 вершинах симплекса и перемещении симплекса в направлении лучшей точки. В рассматриваемом методе симплекс перемещается с помощью операций отражения. Далее принято следующее: х0(k), х1(k), … , хn(k) – вершины симплекса, где к - номер итерации.

Схема алгоритма

Шаг 1.      

           Построение начального симплекса.

Для этого задаются начальная точка х0(0) и длина ребра симплекса l. Формируются остальные вершины симплекса:

xi(0) = x0(0) + l*ei (i=1,2,…,n), где ei – единичные векторы.

 

Шаг 2.  

          Определение направления улучшения решения.

Для этого на к-й итерации вычисляются значения целевой функции в каждой точке симплекса. Пусть для всех i:

f(xmin(k))f(xi(k))f(xmax(k)),

где min, max, i – номера соответствующих вершин симплекса. Определим центр тяжести всех точек, исключая точку xmax(k),

Ck=(xi(k))/n .

 Тогда направление улучшения решения определяется вектором Ck-xmax(k).

Шаг 3.

Построение отраженной точки.

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

uk=ck+(ck-xmax(k))=2ck-xmax(k)

x(2)

Шаг 4.

          Построение нового симплекса.

Вычисляем f(uk). При этом возможен один из двух случаев:

а) f(uk)<f(xmax(k);

б) f(uk)f(xmax(k).

Случай а): вершина xmax заменяется на uk, чем определяется набор вершин к+1-й итерации и к-я итерация заканчивается.

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

                            xi(k+1)=x^i=(xi(k)+xmin(k))/2, где i=0,1,…,n.

На этом к-я итерация заканчивается.

Шаг 5.

           Проверка сходимости.

Если

         то поиск минимума заканчивается и полагается

В противном случае к=к+1 и происходит переход к шагу 2.

1.5.4. Метод деформируемого симплекса (метод Нелдера – Мида).

 

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

В рассматриваемом методе симплекс перемещается с помощью трех основных операций над симплексом: отражение, растяжение и сжатие.

Схема алгоритма.

Шаг 1.

           Построение начального симплекса.

Задаются начальная точка х0(0) и длина ребра l. Формируются остальные вершины симплекса:  xi(0)=x0(0)+lei (i=1,2,…,n), где ei – единичные векторы.

Шаг 2.

         Определение направления улучшения решения.

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

              f(xmin(k)) f(xi(k))  f(xm(k))  f(xmax(k)),

    где  min, m, max, i-номера соответствующих вершин симплекса. Определим центр тяжести всех точек, исключая точку xmax(k),

                       

Тогда направление улучшения решения определяется векторов

                Ck- xmax(k).

Шаг 3.

   Построение нового симплекса.

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

                        uk=Ck+*(Ck-xmax(k)),   где -коэффициент отражения.

Шаг 4.

       Построение нового симплекса.

        Вычисляем f(uk), при этом возможно один из трех случаев:

 а)  f(uk)< f(xmin(k));

 б)  f(uk)>f(xm(k));

 в)  f(xmin(k)) f(uk)  f(xm(k));

Случай а): отражённая точка является точкой с наилучшим значением целевой функции. Поэтому направление отражение является перспективным и можно попытаться растянуть симплекс в этом направлении. Для этого строиться точка

                      Vk= Ck+*(uk-Ck),  где >1 –коэффициент расширения.

Если  f(vk)<f(uk), то вершина xmax(k) заменяется на vk, в противном случае на uk и k-ая итерация заканчивается.

Случай б): в результате отражения получается новая точка uk, которая, если заменить xmax(k), сама станет наихудшей. Поэтому в этом случае производится сжатие симплекса. Для этого строится точка vk:    

                  где  0<<1 –коэффициент сжатия.

Если f(vk)<min{f(xmax(k)),f(uk)}, то вершина xmax(k) заменяется на vk .

В противном случае вершинам xi(k+1) (i=0,1,2,..,n) присваивается значение:

 и на этом k-ая итерация заканчивается.

в)  вершина xmax(k) заменяется на uk, чем определяется набор вершин k+1-й  итерации и k –ая итерация заканчивается.

Шаг 5.  

    Проверка сходимости.

    Если  

то поиск минимума заканчивается и полагается

В противном случае к=к+1 и происходит переход к шагу 2.

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

 =1, =2, =0.5.

2.Задание на лабораторную работу.

  1.  Изучить изложенные методы многомерной безусловной оптимизации.

  1.  В соответствие с вариантом задания, определенным преподавателем,    составить программы реализующие методы многомерной безусловной минимизации и найти точку минимума целевой функции f(x)=f(x(1), x(2)) с заданной точностью указанными методами. Начальное приближение x0 и точность приводятся в условие задачи. Сравнить результаты, полученные разными методами для одной и той же целевой функции (в частности, сравнить число вычислении целевой функции и её производных, понадобившихся для получения заданной точности). Для каждого применяемого метода построить траекторию промежуточных точек, получаемых на очередных шагах метода и сходящихся к точке минимума.

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

3. Варианты задания.

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

             а) градиентный метод с постоянным шагом;

             б) градиентный метод с дроблением шага;

             в) метод наискорейшего спуска (указание метода одномерного поиска);

             г) метод покоординатного спуска с постоянным шагом;

             д) метод Гаусса-Зейделя (указание метода одномерного поиска);

             е) эвристический алгоритм;

            ж) овражный метод ;

             з) овражный метод ;

             к) метод конфигураций;

             л) метод симплекса;

             м) метод деформируемого симплекса.

3.2    Варианты заданий.

       Целевая функция f(x)=f(x(1), x(2)) зависит от двух аргументов. Функция f(x) следующего вида:

f(x)=a*x(1)+b*x(2)+ec*(x ) +d*(x ).

Целевая функция

Начальное

приближение

Точность

решения

a

b

c

d

1

1

-1,4

0,01

0,11

(1;0)

0,0001

2

2

-1,3

0,04

0,12

(0;1)

0,00005

3

10

-0,5

0,94

0,2

(0;0)

0,0001

4

15

0

1,96

0,25

1,96

0,25

5

3

-1,2

0,02

1,3

(0;-1)

0,00005

6

11

-0,4

1

0,21

(-1;0)

0,0001

7

10

-1

1

2

(1;0)

0,0003

8

15

-0,5

2,25

2,5

(0;0)

0,0002

9

20

0,4

0,3

0,3

(0;-1)

0,0001

10

25

0,9

0,35

0,35

(1;0)

0,0004

             


 

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

39116. ИССЛЕДОВАНИЕ КОРОННОГО РАЗРЯДА. Отрицательный коронный разряд 85 KB
  Кроме того критические потенциалы коронного разряда и искрового пробоя Uп неодинаковы. Возникновение коронного разряда объясняется появлением вблизи коронирующего электрода резкой неоднородности электрического поля значительно превосходящей напряженность электрического поля на других участках воздушного промежутка между электродами. Для возникновения коронного разряда напряженность поля у электрода должна превосходить электрическую прочность воздуха.
39117. ПСИХОФИЗИОЛОГИЧЕСКИЕ ПОДХОДЫ И ТЕОРИИ, ОКАЗАВШИЕ ЗНАЧИТЕЛЬНОЕ ВЛИЯНИЕ НА РАЗВИТИЕ ОТЕЧЕСТВЕННОЙ ПСИХОЛОГИИ 102.5 KB
  Основным фактором детерминирующим развитие и функционирование живых организмов а также отдельных физиологических систем в составе организма выступает не прошлое событие а подготовка к еще не наступившим событиям которая обеспечивается прогнозированием результатов предстоящих действий на основе опережающего отражения и механизмами целеполагания. Любой поведенческий акт живого организма обеспечивается рядом системных механизмов и процессов которые организуются в функциональную систему: механизм афферентного синтеза...
39118. АЛЬТЕРНАТИВНЫЕ ОБЩЕПСИХОЛОГИЧЕСКИЕ ТЕОРИИ И ТЕОРЕТИЧЕСКИЕ ПОДХОДЫ К ОБЪЯСНЕНИЮ ПСИХИЧЕСКИХ ЯВЛЕНИЙ 63.5 KB
  Строгий естественнонаучный подход к анализу и объяснению психических явлений в психологии поведения. В качестве одного из основателей объективной психологии поведения называют российского физиолога И. Вместе с тем это направление имеет множество научных достижений которые составляют золотой фонд мировой психологии: исследована эффективность различных типов подкрепления поощрения и наказания в процессах научения разработано множество тонких методов позволяющих регистрировать различные формы поведения животных установлено...
39119. КУЛЬТУРНО-ИСТОРИЧЕСКИЙ И СИСТЕМНО-ДЕЯТЕЛЬНОСТНЫЙ ПОДХОДЫ К АНАЛИЗУ И ОБЪЯСНЕНИЮ ПСИХИЧЕСКИХ ЯВЛЕНИЙ 172 KB
  Культурное развитие человека представляет собой формирование и развитие в совместной деятельности и общении высших психических функций ВПФ. Источник развития человеческой психики находится во внешней идеальной форме – в фиксированных в человеческой культуре средствах и способах деятельности и общения которыми необходимо овладеть. Формирование ВПФ выделяет человека из животного мира и заключается в присвоении культурноисторического опыта человечества что обеспечивает изменение структуры деятельности и психики человека. При этом...
39120. ТЕОРИИ ЭМОЦИОНАЛЬНЫХ ЯВЛЕНИЙ. ТЕОРИИ МОТИВАЦИОННОЙ И ВОЛЕВОЙ РЕГУЛЯЦИИ 155 KB
  Состояние когнитивного диссонанса возникает тогда: когда человек воспринимает самого себя в качестве причины возникшей когнитивной несогласованности; когда действия субъекта основаны на свободном выборе и разрушают Яконцепцию; когда люди чувствуют личную ответственность за свои неверные действия и поступки; когда такие действия и поступки имеют серьезные последствия. Когда свои действия или поступки которые вызывают когнитивный диссонанс человек не может оправдать и объяснить внешними факторами уменьшение диссонанса...
39121. СТРУКТУРНЫЕ, ФУНКЦИОНАЛЬНЫЕ И ГЕНЕТИЧЕСКИЕ ТЕОРИИ МЫШЛЕНИЯ (ИНТЕЛЛЕКТА) ЧЕЛОВЕКА 163.5 KB
  Такие возможности реализуются на основе эмпирического опыта и воздействий социального окружения; эмпирическим опытом который включает: формирование двигательных навыков путем упражнения извлечение информации из опыта взаимодействия с физическим миром логикоматематический опыт организации и координации познавательных действий; воздействием социального окружения. Взаимодействие субъекта и объекта – это источник любого знания который складывается из двух типов опыта: координации действий и операций которые строятся...
39122. СТРУКТУРНЫЕ, ФУНКЦИОНАЛЬНЫЕ И ГЕНЕТИЧЕСКИЕ ТЕОРИИ ПАМЯТИ ЧЕЛОВЕКА 104.5 KB
  СТРУКТУРНЫЕ ФУНКЦИОНАЛЬНЫЕ И ГЕНЕТИЧЕСКИЕ ТЕОРИИ ПАМЯТИ ЧЕЛОВЕКА План 1. Теории и модели памяти в когнитивной психологии 1. Модели организации процессов памяти в когнитивной психологии Кратковременная память Ограниченность объема: в среднем 5–7 единиц информации. На самых глубоких уровнях: а происходит когнитивная семантическая обработка путем установления различных связей с информацией в долговременной памяти; б устанавливается смысл и содержание информации осуществляется ее субъективная оценка.
39123. Структурные, функциональные и генетические теории внимания человека 63.5 KB
  Теории и модели внимания в когнитивной психологии Д. Модель внимания на основе избирательного ослабления сигналов Существует перцептивный фильтр расположенный между входными сенсорными сигналами и вербальным семантическим анализом сообщения. Стадия предвнимания: происходит быстрое извлечение и обработка информации полученной рецепторами позволяющие выделить простые и наиболее заметные признаки объектов; обработка информации производится автоматически быстро параллельно; обработка информации происходит без сознательных усилий и...
39124. ТЕОРИИ СОЗНАНИЯ ЧЕЛОВЕКА 86.5 KB
  ТЕОРИИ СОЗНАНИЯ ЧЕЛОВЕКА План Структурное и функциональное определение и объяснение сознания сохраняет свою актуальность в психологии до настоящего времени. Попытки объяснить сознание человека в истории психологии были связаны: с анализом организации процессов внимания с анализом осознаваемых и неосознаваемых мотивов человека с описанием сознания как сцены на которой представлен феноменологический опыт субъекта ассоциативная психология гештальтпсихология с трактовкой сознания как активного начала организующего в единство...