Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Прямые методы минимизации. Метод многогранника






К прямым методам относятся: метод покоординатного спуска Пауэлла, метод Розенброка, метод многогранника (симплексный метод), метод Гаусса - Зейделя.

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

Fn+1 ≥ Fn ≥ F2 ≥ … ≥ F1.

Эти точки можно интерпретировать как вершины некоторого многогран­ника в n - мерном пространстве.

На каждой итерации текущий многогранник заменяется новым: " худшая" вершина xn+ 1 отбрасывается и вместо неё вводится некая более подходящая точка.

Обозначим через С центр тяжести n лучших вершин х1, х2, …, хn очередной итерации, определяемый по формуле

Расчеты начинаются с построения пробной точки

где α 0 - коэффициент отражения, в ней значения F2 минимизируемой функции, т.е. x2 получается отражением точки xn+1.

Возможны три случая.

 

1. Если Fn ≥ F2 ≥ F1, то xn+1 заменяется на x2 и выполняется следующая итерация.

2. F2 < F1, т.е. x2 – лучшая точка – делается попытка растянуть многогранник в этом направлении. Для этого рассчитывается точка

хе = с + β (х2 - с),

где β > 1коэффициент растяжения. Если Fе < F1 растяжение увенчалось успехом и тогда x2 заменяется на xе, в противном случае xn+1 заменяется на xе.

3. F2 ≥ Fn делается заключение, что многогранник слишком велик и его надо сжать. Это осуществляется введением точки

 

 

 

Рис. 2.1. Метод многогранника.

 

ЛЕКЦИЯ 3

ГРАДИЕНТНЫЕ МЕТОДЫ. МЕ­ТОД НАИСКОРЕЙШЕГО СПУСКА

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал