Шпаргалка по "Экономико-математическому моделированию"

Одна из возможных  траекторий поиска минимума двумерной функции методом Гаусса — Зайделя приведена на рис. В качестве начальной изменяемой переменной в каждом цикле принята x₂.

3-траектория метода Гаусса-Зайделя

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

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

При нахождении оптимума по каждой переменной прекращают поиск не в точке оптимума, а несколько пройдя ее. При этом удается выскочить из ловушек", за меньшее число циклов выйти в район оптимума. В районе оптимума наблюдается зацикливание, и в этом случае последовательно уменьшают величину последействия.

В двумерных  задачах метод Гаусса-Зайделя  фактически сводится к методу наискорейшего  спуска, так как в обоих методах  траектория поиска представляет собой  последовательность взаимноортогональных отрезков

 

35. БЕЗГРАДИЕНТНЫЕ МЕТОДЫ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ ЭКСПЕРИМЕНТОВ. СИМПЛЕКСНЫЙ МЕТОД.

 

Симплексом в n-мерном пространстве называют фигуру, содержащую n+1 вершину. На плоскости — это треугольник, в трехмерном пространстве - тетраэдр и т.д.  Если все вершины симплекса равно удалены друг от друга, то такой симплекс называется регулярным. В литературе можно встретить и другое название метода — метод деформируемою многогранника. В организации    алгоритма    поиска    используется    важное    свойство симплекса    против  каждой   вершины  находится только одна грань. Суть метода заключается в следующем. В окрестности начальной точки х° строим симплекс, затем находится самая "плохая" его вершина (т.е. та, в которой наихудшее  значение критерия оптимальности) и на противоположной грани строится новый симплекс, отличающийся от исходною только одной вершиной. Эта вершина получается симметричным отражением выбрасываемой вершины относительно центра противолежащей грани. Центр грани определяется геометрически, как среднее значение

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

˜x^j=2/n  (x¹+x²+…+xⁿ⁺¹) – (1+ 2/n)x^j

где x¹, x², ... — вектора вершины симплекса (координаты вершин), х^j — вектор выбрасываемой вершины, ˜x^j — новая вершина в новом симплексе. В скалярном представлении для каждой координаты будет аналогичная формула.

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

˜x^j=3/2n  (x¹+x²+…+xⁿ⁺¹) – (1+ 3/2n)x^j

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

Основным недостатком  метода является невозможное ускорения  поиска вдали оптимума. Этот  недостаток устранен в  модификаций метода, известной как метод Нелдера  — Мида. В      этом варианте симплексного метола предусмотрено растяжение симплекса в случае, если новая вершина лучше в старом симплексе, а также сжатия симплекса, если новая вершина оказывается хуже наихудшей в старом симплексе.

Формула растяжения имеет вид:

  ̂˜x^j=γx^j+(1-γ)x^a   где γ — коэффициент растяжения.

Формула сжатия имеет следующий вид:

  ̂˜x^j=βx^j+(1-β)x^a  где β — коэффициент сжатия, х^a — вектор центра противолежащей грани, ˜x^j — "отраженная" новая вершина по алгоритму,  ̂˜x^j — новая вершина.

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

При этом уменьшаются  все грани симплекса одновременно в два раза. Умнение размера  симплекса в два раза осуществляется делением пополам расстояния от каждой точки симплекса до точки х₁, определяющей наименьшее значение функции, т.е. будет: x_i=x_i^c+0.5(x_i-x₁).

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

Одна из возможных  траекторий поиска минимума двумерной  функции базовым алгоритмом симплексного метода приведена на рис

5-траектория симплексного  метода 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

36. БЕЗГРАДИЕНТНЫЕ  МЕТОДЫ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ  ЭКСПЕРИМЕНТОВ. МЕТОД СКАНИРОВАНИЯ, МЕТОД ПАРАЛЛЕЛЬНЫХ КАСАТЕЛЬНЫХ.

 

Метод сканирования

Метод заключается в последовательном переборе всех значений а ≤ х ≤, b с шагом е (погрешность решения) с вычислением критерия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи x*

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

На практике можно реализовать одну из основных модификаций метода — последовательное уточнение решении, или сканирование с переменным шагом (рис. 13).

Рис, 13, Иллюстрация модифицированного  метола  сканирования: 1 — интервал, включающий в себя искомый максимум    функции после первого этапа сканировали (исходный участок разбит на 5 участков);      2-то же, после второго этапа

На первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение R(х) разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточненное значение

максимума. Он (новый  отрезок) опять делится на более мелкие и т.д. до тех пор, пока величина отрезка, содержащего максимальное значение R(х), не будет меньше заданной погрешности. Главный недостаток этого варианта метода — возможность пропуска "острого" глобального максимума R(х).

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

Метод параллельных касательных рассмотрим на примере  двухмерной задачи R(x₁,x₂).   Он  заключается в следующем.   Из двух произвольных точек х¹⁰, х²⁰ , не лежащих на одной прямой заданного направления (например, вдоль одной переменной), проводят два спуска по направлению и находят две точки оптимумов х¹¹  и х²¹. Далее оптимум ищут на прямой, соединяющей эти точки. Во всех поисках по направлению могут применяться любые одномерные методы поиска. После отыскания оптимума х³ вдоль направления   х¹¹ - х²¹ опять ищут оптимум из точки х³ в первоначально заданном направлении и находят точку х³¹, затем опять в направлении х³¹ – х¹¹ ищут одномерным методом оптимум и т д.

В качестве исходного  направления задается обычно направление одной из координатных осей (по х₁ или по х₂ и т д.), хотя может задаваться любое направление.

Для квадратичных функций поиск заканчивается  всего за три одномерных поиска, для не квадратичных — это итерационная процедура, сходящаяся к решению тем быстрее, чем ближе R(х₁,х₂) к квадратичной функции.

Для трехмерной задачи (в случае квадратичного критерия оптимальности) необходимо сначала найти за три одномерных поиска оптимум в одной плоскости (например, х₃=const₁), затем в другой, параллельной ей (х₃=const₂), далее потребуется один спуск вдоль направления точек оптимума в этих плоскостях.

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

  N_n=2N_n-1+1

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

Одна из возможных  траекторий поиска минимума двумерной функции методом параллельных касательных приведена на рисунке

2-траектория метода параллельных касательных

 

 

38. ОСОБЕННОСТИ ОРГАНИЗАЦИИ ЭКСТРЕМАЛЬНЫХ ЭКСПЕРИМЕНТОВ В ОВРАЖНЫХ И МНОГОЭКСТРЕМАЛЬНЫХ СИТУАЦИЯХ.

 

Овраг-это такое  образование, в котором крутизна склонов в разных направлениях разная. Вдоль дна понижения идет медленно, а поперек - быстро.

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

Овражной принято  назвать функцию, если она имеет min или max.

В общем случае большинство рассмотренных методов в овражных функциях низко эффективны.

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

Один, из которых  мы рассмотрим.

Берем любую  точку и любым методом ищем наилучшее решение, которое окажется примерно на дне оврага. В окрестности  начальной точки х₁ берется другая произвольная точка х₃ и из нее также ищется решение, получим точку х₄, которая также лежит в окрестности дна оврага. Т.о. мы определили приметно дно оврага, точки х₂ и х₄ указывают направление оврага. В этом направлении совершается большой шаг, называется прострел. Дно оврага кривое – точка х₅ далеко. Из точки х₅ идет спуск ко дну оврага и получаем точку х₆. Через две точки на дне оврага делается большой прострел из х₄ и х₆ и получаем х₇, которая опять не лежит на дне оврага, из нее спускаемся на дно оврага и получаем х₈.

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

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

Есть несколько  специальных методов:

1.метод тяжелого  шарика

Идея метода базируется на аналогии с движением материального тела вниз. Для того, чтобы шарик остановился на дне самой глубокой ямки, нужно создать трение, это трение эмитирует налитую в эту чашу жидкость (трение среды). Траектория движения зависит от «массы шарика» и от «вязкости среды». Можно построить уравнение движения, в которое войдут и m и μ. Можно заменить непрерывное уравнение дискретным аналогом. Дифференциальное уравнение движения будет 2 порядка, поэтому разностный дискретный аналог будет включать в себя не только предыдущую точку, но и предпредыдущую. xⁱ⁺¹=xⁱ+h grad R(xⁱ)    xⁱ⁺¹=f(R(xⁱ))      xⁱ⁺¹=f(R(xⁱ,x^i-1))

Когда новая  точка определяется не только текущей, но и предыдущей -> второго порядка  метода. Важность: ускорение поиска вдали от оптимума.

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