Градиентные методы решения задач выпуклого программирования

Размещено на http://www.allbest.ru/

1

Контрольная работа

Градиентные методы решения задач выпуклого программирования

Содержание

Введение

1. Понятие нелинейного программирования

1.1 Специфика нелинейных программ и методы их решения

1.2 Классификация методов нелинейного программирования

1.3 Выпуклое программирование

2. Градиентные методы решения задач выпуклого программирования

2.1 Градиентные методы решения задач

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

Использованная литература

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

Введение

Интенсивное развитие методов математического программирования связано с тем, что оптимизационные задачи играют большую роль в самых различных областях человеческой деятельности. Сейчас основное внимание уделяется развитию методов выпуклого программирования. Построен целый ряд алгоритмов, проведены исследования их сходимости. Однако эти алгоритмы применяются довольно редко, и нет достаточной информации, позволяющей судить об их сравнительной эффективности. При использовании методов выпуклого программирования решение исходной задачи обычно определяется как предел минимизирующей последовательности решений более простых (вспомогательных) экстремальных задач.

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

- К первой группе относятся методы, при реализации которых на каждом шаге приходится решать задачу минимизации линейной или выпуклой функции при линейных ограничениях. Это различные варианты метода возможных направлений (метод отсечения, проекций градиента).

- Ко второй группе относятся методы, с помощью которых искомое решение определяется как предел последовательности безусловных минимумов специальным образом сконструированных вспомогательных функций: метод штрафных функций, центров, множителей Лагранжа.

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

Глава 1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1 Понятие нелинейного программирования

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

Математические модели в задачах проектирования реальных объектов или технологических процессов должны отражать реальные протекающие в них физические и, как правило, нелинейные процессы. Переменные этих объектов или процессов связанны между собой физическими нелинейными законами, такими, как законы сохранения массы или энергии. Они ограничены предельными диапазонами, обеспечивающими физическую реализуемость данного объекта или процесса. В результате, большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования - это задачи нелинейного программирования (НП). Пусть в математической модели проектируемого объекта или процесса непрерывная функция представляет собой функцию цели (функцию качества),

задают ограничения в виде равенств

задают ограничения в виде неравенств, где

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

Тогда задача нелинейного программирования может быть сформулирована следующим образом:

найти вектор , доставляющий минимум (максимум) целевой функции при m линейных и (или) нелинейных ограничений в виде равенств

и (p-m) линейных и (или) нелинейных ограничений в виде неравенств

В течение последних двух десятилетий из нелинейного программирования выделились самостоятельные разделы:

-выпуклое программирование,

-квадратичное программирование,

-целочисленное программирование,

-стохастическое программирование,

-динамическое программирование и др.

Задачи выпуклого программирования - это задачи, в которых определяется минимум выпуклой функции (или максимум вогнутой), заданной на выпуклом замкнутом множестве. Эти задачи среди задач нелинейного программирования наиболее изучены.

Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция - квадратичная, а ограничения - линейны.

В задачах целочисленного программирования неизвестные параметры могут принимать только целочисленные значения.

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

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

1.2 Классификация методов нелинейного программирования

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

По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:

- однокритериальные,

- многокритериальные.

По длине вектора методы делятся на:

- однопараметрические или одномерные (n=1),

- многопараметрические или многомерные (n>1).

По наличию ограничений методы нелинейного программирования делятся на:

- без ограничений (безусловная оптимизация),

- с ограничениями (условная оптимизация).

По типу информации, используемой в алгоритме поиска экстремума методы делятся на:

- методы прямого поиска, т.е. методы, в которых при поиске экстремума целевой функции используются только ее значения;

- градиентные методы первого порядка, в которых при поиске экстремума функции используются значения ее первых производных;

- градиентные методы второго порядка, в которых при поиске экстремума функции наряду с первыми производными используются и вторые производные.

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

1.3 Выпуклое программирование

Выпуклое программирование [convex programming] -- раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений.

Общая задача выпуклого программирования состоит в отыскании такого вектора x (т. е. такой точки выпуклого допустимого множества), который доставляет минимум выпуклой функции f(x) или максимум вогнутой функции y(x). Для второго случая (выпуклая область допустимых значений и максимум вогнутой функции) ряд авторов предпочитают термин “вогнутое программирование”.

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

Как видим, есть сходство между задачами выпуклого (вогнутого) и линейного программирования (последнее можно рассматривать как частный случай первого). Но нелинейность зависимостей делает задачу намного сложнее.

Под задачей выпуклого программирования понимают задачу вида

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

Для решения задач этого типа разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях ѕ метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.

Глава 2. Градиентные методы решения задач выпуклого программирования

2.1 Градиентные методы решения задач

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

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

Градиентные методы могут быть подразделены на две группы.

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

- Ко второй - методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу - Гурвица.

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

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

В качестве основной в теории выпуклого программирования обычно рассматривается задача отыскания вектора который удовлетворяет условиям:

и доставляет глобальный минимум функции

функции предполагаются гладкими и выпуклыми.

Если-- вогнутая функция, а -- выпуклые функции, то получаем соответственную задачу: найти вектор удовлетворяющий условиям и доставляющий глобальный максимум функции

Множество точекудовлетворяющих условиям формулированных задач, является выпуклым.

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

Если функциядифференцируема в точкето градиентом в точке называется n-мерный вектор

Градиент в каждой точке, в которой он существует, направлен по нормали к линии уровня поверхности (рис. 1) и показывает направление наискорейшего возрастания функции в данной точке. Если градиент отличен от нуля, то он указывает направление, небольшое перемещение по которому будет увеличивать значение функции

Вектор

противоположный градиенту, называется антиградиентом и указывает направление наискорейшего убывания

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

Градиентный метод основан на простой идее. Если заранее известно, чтоимеет в допустимой области единственный экстремум, то поиск точки, в которой он достигается, целесообразно проводить так. В допустимой области взять произвольную точкуи с помощью градиента (антиградиента) определить направление, в которомвозрастает (убывает) с наибольшей скоростью (рис. 2).

Сделав небольшой "шаг" в найденном направлении, перейти в новую точку . Потом снова определить наилучшее направление для перехода в очередную точкуи т.д. Иначе говоря, надо построить последовательность точек так, чтобы она сходилась к точке экстремума х*, т. е. для точек последовательности выполнялись условия

Величина "шага" из точки по направлению градиента (антиградиента ) определяется значением параметра в уравнении прямой

проходящей через параллельно градиенту (антиградиенту). Значение можно выбрать исходя из конкретных условий

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

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

2.2 Метод множителей Лагранжа

Метод множителей Лагранжа позволяет отыскивать максимум или минимум функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа. Пусть задана задача НП при ограничениях-равенствах вида при ограничениях

Предположим, что все функции f, h1, h2, ..., hm - дифференцируемы. Введем набор переменных (число которых равняется числу ограничений), которые называются множителями Лагранжа, и составим функцию Лагранжа такого вида:

Справедливо такое утверждение: для того чтобы вектор являлся решением задачи (4.1) при ограничениях (4.2), необходимо, чтобы существовал такой вектор , что пара векторов удовлетворяла бы системе уравнений

Покажем необходимость условий (4.4), (4.5) на простом примере: при ограничениях

Ограничения (4.7) определяют допустимую область S, которая представляет собой кривую в пространстве R(2) и является результатом пересечения h1(x) и h2(x).

Допустим, что рассматриваемая задача имеет точку минимума в S1: , функции f, h1, h2 имеют непрерывные производные первого порядка на некотором открытом множестве и градиенты линейно независимы.

Если две переменные в уравнениях (4.7) можно выразить через третью в виде x2=U(x1), x3=V(x1), то подставив их в целевую функцию (4.6), преобразуем исходную задачу в следующую задачу без ограничений, которая содержит лишь одну переменную x1:

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

Приведенный подход можно в принципе распространить и на случай функции n переменных при наличии m ограничений-равенств:

Если функции удовлетворяют условиям теоремы о неявной функции, то m из n переменных уравнений (4.9) можно выразить через остальные (n-m) переменных, подставить их в f(x) и таким образом преобразовать задачу минимизаци с ограничениями в задачу безусловной минимизации с (n-m) переменными. Однако такой подход трудно реализовать на практике, поскольку очень трудно разрешить уравнения (4.9) относительно некоторых переменных. В общем случае это совсем невозможно.

Поэтому рассмотрим другой подход, который базируется на методе множителей Лагранжа.

Пусть x+ - точка минимума f(x), определяемого выражением (4.8). В соответствии с известной теоремой математического анализа о неявной функции можно записать

Аналогичные соотношения получим для ограничений

Запишем уравнения (4.10), (4.11) совместно в виде где

Поскольку вектор не является нулевым, то из (4.12) следует, что det A = 0. Из этого следует, что вектора-строки матрицы A должны быть линейно зависимы. Следовательно, существуют три таких скаляра a, b, c не все равные 0, что

Скаляр, а не может равняться 0, так как в соответствии с предположением и - линейно независимы. Поэтому после деления (4.13) на a, получим

Таким образом, для задачи минимизации с ограничениями (4.6) существуют такие , для которых справедливо уравнение (4.14) и которые одновременно не обращаются в нуль. Итак, справедливость условий (4.4) для случая n=3 показана.

Таким образом, для отыскания минимума (4.6) при условиях (4.7) необходимо найти стационарную точку функции Лагранжа:

Для того чтобы найти искомые значения , необходимо решить совместно систему уравнений (4.14), (4.5). С геометрической точки зрения условие (4.14) означает, что лежит в плоскости, натянутой на векторы .

Теперь рассмотрим общий случай для произвольных n. Пусть задана задача НП в виде (4.1), (4.2), все функции , имеют непрерывные частные производные на множестве R(n). Пусть S(x)- подмножество множества R(n), на котором все функции , то есть . Тогда справедлива такая теорема о множителях Лагранжа.

Теорема 4.7. Допустим, что существует такая точка x+, в которой достигается относительный экстремум задачи НП (4.1) при условиях (4.2). Если ранг матрицы в точке x+ равен m, то существуют m чисел , не все из которых равны нулю одновременно, при которых

Эта теорема обосновывает метод множителей Лагранжа, который состоит из следующих шагов.

Составляют функцию Лагранжа

Находят частные производные

Решают систему уравнений и отыскивают точки , удовлетворяющие системе (4.16).

Найденные точки x0 дальше исследуют на максимум (или минимум).

Список литературы

1. Васильев Ф. П. Численные методы решения экстремальных задач - М. Наука, 1980

2. Гроссман К. Г., Каплан А. А. Нелинейное программирование на основе безусловной минимизации - Новосибирск: Наука, 1981

3. Кудрявцев Е. М. Исследование операций в задачах, алгоритмах, программах - М.: Радио и связь, 1984

4. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации М.: Наука, 1978

5. Романовский И. В. Алгоритмы решения экстремальных задач - М.: Наука, 1982

6. Шун Терри Е. Решение инженерных задач на ЭВМ - М.: Мир, 1977.

Размещено на Allbest.ru