Студопедия — МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ

МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ

Смысл методов нахождения безусловного экстремума функции нескольких переменных заключается в том, что по определенному правилу выбирается последовательность значений { xi } вектора x такая, что Q (xl+1)≤(≥) Q (xl). Так как целевая функция предполагается ограниченной, то такая последовательность ее значений стремится к пределу. В зависимости от принятого алгоритма и выбора начальной точки этим пределом может быть локальный или глобальный экстремум функции Q(x).

Метод Гаусса-Зайделя. Метод заключается в последовательном определении экстремума функции одной переменной с точностью до ε вдоль каждой координаты, т.е. фиксируются все координаты, кроме одной, по которой и осуществляется поиск экстремума Q. Потом та же процедура осуществляется при фиксации следующей координаты. После рассмотрения всех n координат выполняется возврат к первой и вновь производится поиск локального экстремума вдоль каждой из n координат до тех пор, пока экстремум не будет локализован с заданной точностью.

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

,

где параметр αk ≥ 0 задает длину шага.

Алгоритм метода градиента включает в себя следующие шаги.

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

2. Рассчитывается значение целевой функции в начальной точке .

3. Определяется направление градиента в начальной точке.

4. Делается шаг в направлении антиградиента при поиске минимума, в результате чего попадают в точку x1.

5. Процесс поиска продолжается, повторяя все этапы с п. 2, т.е. вычисляется , определяется направление градиента в точке x1, делается шаг и т.д.

Важной задачей в этом методе является выбор шага. Если размер шага слишком мал, то движение к оптимуму будет долгим из-за необходимости расчета целевой функции и ее частных производных в очень многих точках. Если же шаг будет выбран слишком большим, то в районе оптимума может возникнуть "рыскание", которое либо затухает слишком медленно, либо совсем не затухает. На практике сначала шаг выбирается произвольно. Если окажется, что направление градиента в точке x1 существенно отличается от направления в точке x2, то шаг уменьшают, если отличие векторов по направлению мало, то шаг увеличивают. Изменение направления градиента можно определять по углу поворота градиента рассчитываемого на каждом шаге по соответствующим выражениям.

Итерационный процесс поиска прекращается, если выполняются неравенства , где ε;, δ;, γ; – заданные числа.

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

 

Метод наискорейшего спуска. При применении метода градиента на каждом шаге вычисляются значения всех частных производных оптимизируемой функции Q по всем независимым переменным U, что при большом числе этих переменных приводит к весьма большому времени поиска оптимума. Сократить время поиска позволяет метод наискорейшего спуска, блок-схема которого представлена на рис. 5, где ε – точность вычисления, H – величина шага, n – размерность вектора u, Q – алгоритм вычисления целевой функции Q(u), L – количество шагов по конкретному направлению градиента функции Q.

Рис. 5. Блок-схема метода наискорейшего спуска.

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

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

 




<== предыдущая лекция | следующая лекция ==>
Введение. Направляется призывник_____________________________________________________________ | Введение. Облік розрахунків з оплати праці (тема №3)

Дата добавления: 2015-03-11; просмотров: 725. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Менадиона натрия бисульфит (Викасол) Групповая принадлежность •Синтетический аналог витамина K, жирорастворимый, коагулянт...

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

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

ПУНКЦИЯ И КАТЕТЕРИЗАЦИЯ ПОДКЛЮЧИЧНОЙ ВЕНЫ   Пункцию и катетеризацию подключичной вены обычно производит хирург или анестезиолог, иногда — специально обученный терапевт...

Ситуация 26. ПРОВЕРЕНО МИНЗДРАВОМ   Станислав Свердлов закончил российско-американский факультет менеджмента Томского государственного университета...

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия