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

Основные данные о работе

Версия шаблона	1.1
Филиал	Типовые филиалы
Вид работы	Творческая работа
Название дисциплины	(0047) Математические методы исследования экономики
Тема	Градиентные методы решения задач выпуклого программирования
Фамилия студента	Колпаков
Имя студента	Александр
Отчество студента	Андреевич
№ контракта	05204120301009

 

Содержание

Введение

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

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

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

Основная часть

Введение

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

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

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

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

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

 

 

 

 

 

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

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

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

 

 

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

 

 

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

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

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

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

 

 

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

 

 

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

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

 

 

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

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

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

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

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

 

 

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

 

 

Вектор 

 

  

 

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

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

 

 

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

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

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

 

 

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

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

 

 

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