Лекция 14. Практическая реализация методов нелинейного программирования


Содержание лекционного занятия:

· Построение начального приближения

· Практическая реализация методов нелинейного программирования

Построение начального приближения

Все рассмотренные нами методы итерационные. Для них нужно начальное приближение, чтобы построить последо­вательность точек, сходящуюся к минимуму. Разные мето­ды предъявляют и разные требования к начальному при­ближению. В методах безусловной оптимизации, как пра­вило, можно взять любое начальное приближение, если из­вестно, что нет локальных минимумов. В противном случае можно получить решение далеко от точки глобального ми­нимума. Если известно и число локальных минимумов и их приближенные значения, то задачу следует решать много­кратно, начиная из точек, близких к очередному локально­му минимуму

В задачах с ограничениями, если мы не можем по смыс­лу задачи указать хотя бы одну допустимую точку, можно прибегнуть к решению вспомогательной задачи.

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

Для этого задачу достаточно решить один раз. При этом можно получить не только граничную, но и внутреннюю точку, если ужесточить ограничения, приняв вместо cj(x) <=0 cj(x) <= -ε.

На практике встречаются задачи, в которых все ограни­чения можно разделить на две группы, так что для части ограничений (группа 1) легко указать допустимую точку, но она не удовлетворяет другим ограничениям (группа 2). То­гда в штрафную функцию можно включить квадраты невя­зок только в ограничениях группы 2, взять начальное при­ближение, удовлетворяющее всем остальным ограничени­ям, и решать задачу минимизации штрафной функции при ограничениях группы 1. Решение этой вспомогательной задачи будет начальным приближением для исходной зада­чи. Такой прием оказывается эффективным, если мы умеем хорошо работать с ограничениями группы 1, например, при линейных ограничениях можем легко вычислять соответст­вующие проекции.

Практическая реализация методов нелинейного программирования

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

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

Если численные значения 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 дополнительных перемен­ных, но целевая функция приобретает простой вид , так что исходная задача с негладкими функциями сводится к задаче линейного программирования.

Вопросы для самоконтроля:

1.Необходимые и достаточные условия первого и второго порядков оптимальности в задаче с ограничениями-равенствами.

2.Необходимые и достаточные условия первого и второго порядков оптимальности в задаче со смешанными ограничениями

Рекомендуемая литература:

1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981.

2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996