Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b]
Пример решения методами дихотомии и золотого сечения
Численные методы многомерной безусловной оптимизации
Поиск точки min методом циклического покоординатного спуска
Основы линейного программирования
Навигация
Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b]
Сравнительный анализ методов оптимизации
22076
знаков
78
таблиц
12
изображений
1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке [а; b].
2. Функция, унимодальная на отрезке [а; b], является унимодальной и на любом меньшем отрезке [с; d] 
[а; b].
3. Пусть f (x) 
Q [а; b] и 
. Тогда:
если 
, то x* [a; x2];
если 
, то x* [x1; b],
где х* – одна из точек минимума f (x) на отрезке [a; b].
Из численных методов одномерной безусловной оптимизации рассмотрим два:
1. метод дихотомии
2. метод золотого сечения
2.1 Метод дихотомии
В этом методе точки x1 и х2 располагаются близко к середине очередного отрезка [а; b], т.е:
,
где d > 0 – малое число. При этом отношение длин нового и исходного отрезков 
близко к 1/2, этим и объясняется название метода.
Отметим, что для любых точек x1 и х2 величина t > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска х*.
В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [а; b], убедившись предварительно, что достигнуто неравенство 
.
Опишем алгоритм метода деления отрезка пополам.
Шаг 1. Определить x1 и х2 по формулам (2.11). Вычислить f (x1) и f (x2).
Шаг 2. Сравнить f (x1) и f (x2). Если 
, то перейти к отрезку [а; x2], положив b = x2 , иначе – к отрезку [x1; b], положив а = x1 .
Шаг 3. Найти достигнутую точность 
Если 
, то перейти к следующей итерации, вернувшись к шагу 1. Если 
, то завершить поиск х*
2.2 Метод золотого сечения
Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.
Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1–t (рис.2.2).
Рис. 2.2.-Определение пробных точек в методе золотого сечения
Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2¢ = 1–t нового отрезка [0; т]. Чтобы точки х2 = t, и х2¢ = 1–t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство 
или 
, откуда находим положительное значение 
… Таким образом, х1 = 1–t = 
, 
.
Для произвольного отрезка [а; b] выражения для пробных точек примут вид
; 
.
1. Точки x1 и х2 обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b].
2. На каждой итерации исключения отрезков с пробными точками одна из них 
переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х2], то на него переходит пробная точка 
исходного отрезка, становясь его второй пробной точкой (х2’= х1) (рис. 2.2). В случае перехода к отрезку [х1; b] пробная точка 
исходного отрезка становится первой пробной точкой отрезка [х1; b].
3. Легко проверить, что х1=а+b–х2 , и x2=а+b–х1. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания.
4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков 
.
На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении 
, поэтому в результате п итераций его длина становится 
. Таким образом, точность en определения точки х* после п итераций находят из равенства
, а условием окончания поиска точки х* с точностью e служит неравенство en £ e.
Похожие работы
... МП к некритическому экстраполированию результата считается его слабостью. Сети РБФ более чувствительны к «проклятию размерности» и испытывают значительные трудности, когда число входов велико. 5. МОДЕЛИРОВАНИЕ НЕЙРОННЫХ СЕТЕЙ ДЛЯ ПРОГНОЗИРОВАНИЯ СТОИМОСТИ НЕДВИЖИМОСТИ 5.1 Особенности нейросетевого прогнозирования в задаче оценки стоимости недвижимости Использование нейронных сетей можно ...
... с издержками двух или трех конкурентов. Это позволит выявить конкурентоспособность предприятия, определить имеющиеся резервы для снижения издержек. Подобный сравнительный анализ издержек производства на данном предприятии и предприятиях-конкурентах служит основанием для разработки и проведения стратегических мероприятий по снижению издержек производства и оптимизации производственной программы. ...
... от года-x и от номера месяца в году-y следующим образом: F(x)=50-x2+10x-y2+10y. Определите, в каком году и в каком месяце прибыль была максимальной. Зав. кафедрой -------------------------------------------------- Экзаменационный билет по предмету МЕТОДЫ ОПТИМИЗАЦИИ Билет № 22 1) Постановка вариационной задачи с ограничениями. Привести пример. 2) Дайте геометрическую ...
... ) аппарат, а затем полученную величину корректируют с учетом других факторов (долгосрочная стратегия предприятия, ограничения по производственным мощностям и пр). 3. Рекомендации по оптимизации величины себестоимости продукции на основе анализа соотношения "затраты - объем - прибыль" 3.1 Деление затрат на постоянные и переменные части и определение показателей маржинального дохода ...
0 комментариев