- •6. Важной составляющей современного аппарата теории оптимизации является выпуклый анализ – раздел математики, в котором изучают свойства выпуклых множеств и выпуклых функций.
- •7. *************************************************
- •8. Задача называется выпуклой, если X – выпуклое множество, f – выпуклая функция на X.
- •9. Численные методы поиска экстремума делятся на 2 класса:
- •10.Во всех численных методах оптимизации необходимо найти экстремумы функции, а после производить над ними какие-либо действия для непосредственной оптимизации.
- •12. Какие условия остановки работы метода оптимизации?
- •13. Приведите и объясните постановку задачи оптимизации функций одной переменной
- •14. Какая функция называется унимодальной?
- •15. Сформулируйте правило исключения интервалов (метод исключения интервалов)
- •16. Что такое интервал неопределенности?
- •17. В чем состoит minmax стратегия поиска минимума на интервале неопределенности?
- •19. Опишите схему метода разделения интервала пополам
- •20. Сформулируйте метод золотого сечения. В чем его отличие от метода разделения интервала пополам?
- •25. В чем состоит стратегия поиска по образцу? в каких методах она реализована?
- •26. Какие преимущества симплекса?
- •27. Опишите схему методов многогранника и деформированного многогранника.
- •28. В чем особенность метода случайного поиска?
- •29. Какая основная особенность градиента используется в методах оптымизации?
- •30. Опишите общую схему градиентных методов.
- •31. В чем состоят особенности методов второго порядка (Метод Ньютона и его модификации)?
- •32. Опишите схему метода Ньютона.
- •33. Какие недостатки метода Ньютона? Дайте их характеристику
- •35. Структурная идентификация
- •37. Принцип последовательной (лексикографической) оптимизации.
- •38. Что положено в основу типизации ситуаций принятия решений? Приведите основные типы ситуаций выбора компромиссного решения.
- •39. Поясните задачу нормализации частных критериев
13. Приведите и объясните постановку задачи оптимизации функций одной переменной
Задача оптимизации, функция цели которой зависит от одной переменной, относится к самому простому типу оптимизационных задач и имеет вид
Анализ задач такого типа занимает центральное место в оптимизационных исследованиях, как теоретической, так и практической направленности. Прежде всего это связано с тем, что методы оптимизации функций одной переменной используются для решения промежуточных подзадач во время поиска экстремума функций многих переменных. Важность оптимизационных задач с одной управляемой переменной обусловила разработку большого количества алгоритмов их решения.
14. Какая функция называется унимодальной?
15. Сформулируйте правило исключения интервалов (метод исключения интервалов)
Методы поиска, которые позволяют определить оптимум функции одной переменной путем уменьшения интервала поиска, носят название методов исключения интервалов.
Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить, в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют.
Правило исключения интервалов. Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x*. Рассмотрим x1 и x2, расположенные a<x1<x2<b.
Если W(x1)>W(x2), то точка минимума W(x) не лежит в интервале (a,x1), т.е. x*Є (x1,b).
Если W(x1)<W(x2), то точка минимума W(x) не лежит в интервале (x2,b), т.е. x*Є (a,x2).
Это правило позволяет реализовать процедуру поиска путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается тогда, когда оставшийся подынтервал уменьшается до достаточно малых размеров.
Главное достоинство поисковых методов - основаны на вычислении только значений функции и, следовательно, не требуют выполнения условия дифференцируемости и записи в аналитическом виде. Последнее свойство особенно ценно при имитационном моделировании.
Процесс применения методов поиска на основе исключения интервалов включает два этапа:
этап установления границ интервала;
этап уменьшения интервала.
Этап установления границ интервала
Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно используется эвристический метод, например, Свенна, в котором (k+1) пробная точка определяется по рекуррентной формуле
xk+1 = xk + 2kD , k=0,1,2... (3.1)
где
xo - произвольно выбранная начальная точка;
D - подбираемая величина шага.
Знак D определяется путем сравнения значений W(x), W(xo + |D | ), W(xo -|D | ):
если W(xo -|D| ) W(x) W(xo + |D| ), то D имеет положительное значение;
если W(xo -|D| ) W(x) W(xo + |D| ), то D имеет отрицательное значение;
если W(xo -|D| ) W(x) W(xo + |D| ), то точка минимума лежит между xo - |D| и xo + |D| и поиск граничных точек завершен;
если W(xo -|D| ) W(x) W(xo + |D| ), то имеем противоречие предположению об унимодальности.
Пример 3.
W(x)=(100-x)2, xo=30, |D| =5.
Определим знак D :
W(30)=4900;
W(30+5)=4225;
W(30-5)=5625.
Выполняется условие W(xo -|D| ) W(x) W(xo + |D| ), следовательно, D имеет положительное значение; x*=30.
x1=xo+20D = 35;
x2=x1+21D = 45, W(45)=3025 < W(x1) ® x*>35;
x3=x2+22D = 65, W(65)=1225 < W(x2) ® x*>45;
x4=x3+23D = 105, W(105)=25 < W(x3) ® x*>65;
x5=x4+24D = 185, W(185)=7225 > W(x4) ® x*<185.
Искомый интервал 65<x*<185.