Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Оснащения врачебно-сестринской бригады.
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-06-04 | 542 |
5.00
из
|
Заказать работу |
Многомерный поиск без использования производных.
Рассмотрим методы решения минимизации функции нескольких переменных f, которые опираются только на вычисление значений функции f(x), не используют вычисление производных, т.е. прямые методы минимизации. В основном все описанные методы заключаются в следующем. При заданном векторе х определяется допустимое направление d. Затем, отправляясь из точки х, функция f минимизируется вдоль направления d одним из методов одномерной минимизации. Задача линейного поиска заключается в минимизации f(x+lym*d) при условии, что lym принадлежит L, где L обычно задается в форме L=E1, L={lym: lym >= 0} или L={l: a<=lym<=b}. Будем предполагать, что точка минимума lym* существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть не ограниченным или оптимальное значение функции конечно, но не достигается ни при каком lym.
Метод циклического покоординатного спуска.
В этом методе в качестве направлений поиска используются координатные векторы. Метод циклического покоординатного спуска осуществляет поиск вдоль направлений d1,..., dn, где dj - вектор, все компоненты которого, за исключением j-ого, равны нулю. Таким образом, при поиске по направлению dj меняется только переменная xj, в то время как все остальные переменные остаются зафиксированными.
Алгоритм циклического покоординатного спуска
Начальный этап. Выбрать eps >0, которое будет использоваться для остановки алгоритма, и взять в качестве d1,..., dn координатные направления. Выбрать начальную точку x1, положить y1 = x1, k=j=1 и перейти к основному этапу.
Основной этап.
Шаг 1. Положить lymj равным оптимальному решению задачи минимизации f(yj+lym*dj) при условии, что lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то перейти к шагу 2.
Шаг 2. Положить x[k+1] = y[n+1]. Если || x[k+1] - xk || < eps, то остановиться. В противном случае положить y1= x[k+1], j=1, заменить k на k+1 и перейти к шагу 1.
Метод Хука и Дживса.
Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке.
При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2. Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.
Алгоритм Хука и Дживса с использованием одномерной минимизации.
Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1,..., dn и направлений поиска по образцу.
Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.
Основной этап.
Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то положить x[k+1] = y[n+1]. Если ||x[k+1] - xk|| < eps, то остановиться; в противном случае перейти к шагу 2.
Шаг 2. Положить d = x[k+1] - xk и найти lym - оптимальное решение задачи минимизации f(x[k+1]+lym*d) при условии lym принадлежит E1. Положить y1= x[k+1]+lym*d, j=1, заменить k на k+1 и перейти к шагу 1.
1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.
Многомерный поиск, использующий производные.
Пусть функция f(x) деференцируема в Еn. В этом разделе рассматривается итерационная процедура минимизации вида:
xk = x[k-1] + lym[k]*dk, k=1,...,
где направление убывания dk определяется тем или иным способом с учетом информации о частных производных функции f(x), а величина шага lym[k] >0 такова, что
f(xk) < f(xk-1), k=1,2,....
Так как функция предполагается дифференцируемой, то в качестве критерия останова в случае бесконечной итерационной последовательности { xk }, как правило, выбирают условие ||grad(f(xk))||<eps, хотя, разумеется, могут быть использованы и другие критерии.
Метод наискорейшего спуска
Метод наискорейшего спуска является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Вектор d называется направлением спуска для функции f в точке x, если существует такое d > 0, что f(x+lym*d)<f(x) для всех lym принадлежащих интервалу (0, d). В частности, если
f(x+ld)-f(x) | ||
lim | -------------------< 0, | при lym->0+ |
lym |
то d - направление спуска. В методе наискорейшего спуска осуществляется движение вдоль направления d, для которого ||d|| = 1 и которое минимизирует приведенный выше предел. Если f дифференцируема в точке x и grad(f(x))!=0, то -grad(f(x))/||grad(f(x))|| является направлением наискорейшего спуска. В связи с этим метод наискорейшего спуска иногда называют градиентным методом.
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!