Методы решения задач нелинейного программирования

из "Математические исследования операций в экономике "

Также очевидно, что вопрос о типе оптимизации не является принципиальным. Поэтому мы, для определенности, в дальнейшем по умолчанию будем рассматривать задачи максимизации. [c.83]
Как и в ЗЛП, вектор х =(x ,x 2.x n)eD называется допустимым планом, а если для любого х е D выполняется неравенство f(x ) f(x), то х называют оптимальным планом. В этом случае х является точкой глобального максимума. [c.83]
В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения. [c.84]
Из теоремы (2.1) вытекает метод поиска условного экстремума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов. [c.85]
Еще раз подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений (2.7), к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума (2.3)-(2.4). Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений (2.7). Их применение объясняется необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретических выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итеративных процессах вычисления и сравнения значений оптимизируемых функций. [c.86]
Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х перемещаться в направлении вектора V/(j (1)), то функция / будет возрастать, по крайней мере, в некоторой окрестности х Следовательно, для точки jt(2 =jt(1)+A,V/(jt(1)), (A, 0), лежащей в такой окрестности, справедливо неравенство f(x( )) f(x(2)). Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1). [c.87]
В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее известных из них. [c.87]
Название метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее по традиции такое название используется и при решении задачи на максимум. [c.87]
После того как точка j +1 найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора V/(j ( 7)) должны быть близки к нулю. [c.89]
Однако существует один класс функций, для которых градиентные методы приводят к нахождению глобального оптимума. Это выпуклые функции. [c.91]
Как следует из геометрической интерпретации, для выпуклой функции локальный экстремум, если он существует, совпадает с глобальным. Справедлива теорема. [c.92]
Теорема 2.2. Если f(x) выпуклая (вогнутая) на Rn функция и Vf(x ) = Q,mox — точка глобального минимума (максимума). [c.92]
Доказательство достаточно провести для случая вогнутой функции, т. к. для противоположного случая оно будет абсолютно аналогичным с точностью до знака. [c.92]
Поскольку выпуклые функции обладают столь полезными оптимизационными качествами, они занимают исключительно важное место в теории исследования операций. Соответствующий раздел получил название выпуклого программирования, а общая задача выпуклого программирования формулируется как проблема поиска максимума вогнутой (минимума выпуклой) функции на выпуклом множестве. [c.93]
По отношению к векторам, задающим направления перемещения, вводятся два фундаментальных понятия. [c.94]
Направление s называется прогрессивным в точке x(q)eDf если существует такое Х 0, что f(x(q) + Xs) 1(х(д))для задачи максимизации и f(x(q + Xs) f(x(q) ) для задачи минимизации. [c.94]
В алгоритме метода допустимых направлений правила выбора точки х +1 к которой происходит очередной переход, различаются в зависимости от того, где находится текущая точка Принципиально возможны две ситуации. [c.94]
Шаговый множитель hq выбирается так, чтобы, с одной стороны, новая точка х +1) принадлежала Д а с другой — значение целевой функции в ней /(лс +1)) было как можно большим. [c.94]
Вновь найденная точка лс+ может находиться или внутри области D, или на ее границе. В первом случае (на рис. 2.4 ему соответствует точка x(q l) ) переходим к началу данного пункта и повторяем вышеописанные действия, а во втором (точка ( 7+1) на рис. 2.4) — действуем по рассматриваемой далее схеме. [c.96]

Вернуться к основной статье