2. Лекции Практические и лабораторные занятия
Практическая реализация методов
жүктеу/скачать 0,77 Mb.
|
| Практическая реализация методов нелинейного программирования
Для решения практической задачи оптимизации создается ее математическая модель. При этом стремятся обеспечить ее максимальное приближение к действительности, а вопрос о том, как будут проводиться оптимизационные расчеты, откладывается до момента, когда модель построена. Прежде чем приступить к решению задачи при уже построенной математической модели, эту модель нужно проанализировать с точки зрения организации будущего вычислительного процесса и по возможности предотвратить его осложнения. Например, целевая функция выражена квадратичной формой с диагональной матрицей: Если численные значения Ki существенно различны, то поверхности уровня функции F(x) вытянуты по тем координатным осям, которым соответствуют малые значения Ki. Возникает овражность, существенно замедляющая сходимость многих алгоритмов оптимизации. В данном случае этой овражности легко избежать с помощью замены переменных yi = ki1/2xi. После этой замены целевая функция превращается в сумму квадратов, а поверхности уровня в сферы. При наличии ограничений в них тоже необходимо произвести замену переменных. Для функции произвольного вида можно взять приближенные значения вторых производных d2F(x)/dxi2, если эти производные легко доступны для вычисления и не сильно меняются в допустимой области. При этом не получим сферических поверхностей, но существенно уменьшим овражность. Масштабирование заменой переменных с вычислительной точки зрения имеет своей целью добиться, чтобы в области поиска приходилось иметь дело с переменными, абсолютные величины которых имеют одинаковые порядки. Если в области поиска модули переменных существенно меняются, то такая замена ненадежна. Если для каждой переменной известен диапазон изменения, например в явном виде заданы ограничения ai<= xi <= bi, то имеет смысл, как говорят, «отмасштабировать и центрировать переменные». Это означает переход к новым переменным у, по формуле После этой замены все новые переменные уi окажутся на отрезке [-1,1]. Иногда такое преобразование называют переходом к безразмерным центрированным величинам. После оптимизации по уi исходные переменные xi определяются с помощью обратного преобразования: Или в матричном виде х = Dy + с, где D — диагональная матрица с элементами dij = 1/2 (bi – аi), а с — вектор с компонентами сi= 1/2 (bi + ai). Если градиент по старым переменным хi обозначить как обычно g, то градиент по новым переменным gy = Dg. Существенные сложности при решении задач оптимизации возникают при наличии негладких функций. Разработанные в недавнем прошлом специальные методы негладкой оптимизации достаточно сложны. В то же время в практических целях функции с разрывными производными часто могут с успехом быть заменены функциями, имеющими непрерывные производные. В программных реализациях стремятся избежать работы с величинами, численные значения которых различаются на много порядков, чтобы уменьшить влияние ошибок представления чисел в компьютере. Существенных упрощений процесса оптимизации в ряде случаев можно добиться преобразованием целевой функции н ограничений при введении дополнительных переменных. Наиболее наглядно это проявляется в задаче минимизации суммы модулей линейных функций при линейных ограничениях. Задача имеет вид: найти min Σ|η(x)| при ограничениях Ах <= b. Здесь Дополнительные переменные yi вводятся так: | η(x)| <= уi. При этом появляются 2m дополнительных линейных неравенств: относительно n исходных и m дополнительных переменных, но целевая функция приобретает простой вид , так что исходная задача с негладкими функциями сводится к задаче линейного программирования. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|