Задача выпуклого программирования. Постановка задачи выпуклого программирования

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

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

требуется определить значения n переменных x 1 , x 2 , ..., x n , которые удовлетворяют m уравнениям или неравенствам вида

i = 1, 2, ..., m.

и обращают в максимум (или минимум) функцию цели

f (X) = f (x 1 , x 2 , ..., x n). (2.2)

Предположим, что f и g i - нелинейные заданные функции, b i - известные константы. Обычно считается, что все или по крайней мере некоторые переменные должны быть неотрицательными.

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

Всякая другая задача математического программирования, отличная от этой, считается нелинейной задачей.

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

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

где на функции f j (x j) должны в свою очередь быть наложены некоторые ограничения. Это так называемая сепарабельная функция. В другом случае целевая функция может быть записана как сумма линейной и квадратичной функций:

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

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

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

Поделитесь работой в социальных сетях

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

Лекция №12

ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ

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

Задача математического программирования

(12.1)

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

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

Элементы выпуклого анализа

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

Определение 12.1. Множество вида

(12.2)

называется отрезком, соединяющим точки и, и обозначаемым.

Очевидно, при точка X совпадет с одним из концов отрезка (), при с другим (), а при - с некоторой внутренней точкой отрезка.

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

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

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

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

Теорема 12.1 . Теорема Фаркаша. Пусть заданы матрица размерности и вектор. Неравенство выполняется для всех в том и только том случае, если существует вектор такой, что.

Д о к а з а т е л ь с т в о. Достаточность. Пусть выполняются соотношения и. Тогда для любого вектора будет

Необходимость. Пусть для всех справедливо. Рассмотрим конус. Если, то теорема доказана. Предположим, что. Множество, по определению 12.2, выпукло и замкнуто, поэтому в силу теоремы отделимости существует вектор такой, что

(12.3)

для всех.

Так как при всех, то из (12.3) получаем, что при всех. Значит. С другой стороны. То есть и так как это имеет место для всех, то

. (12.4)

Но, поэтому из (12.3) следует

. (12.5)

Взяв, из (12.4) и (12.5) получаем противоречие условиям теоремы.

Замечание. Приведем геометрическое истолкование теоремы Фаркаша. Пусть

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

Рис 12.1

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

(12.6)

Функция называется строго выпуклой , если для всех неравенство (12.6) выполняется как строгое. Функция называется сильно выпуклой , если существует такое число, (константа сильной выпуклости ), что для всех и любого выполняется неравенство

(12.7)

Всякая сильно выпуклая функция является строго выпуклой и тем более выпуклой функцией, но не наоборот.

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

Теорема 12.2 . Линейная комбинация с неотрицательными коэффициентами выпуклых на выпуклом множестве функций есть выпуклая функция на данном множестве.

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

, (12.8)

где выпукла на.

Для произвольных точек и из и любого числа имеем

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

Теорема 12.3. Если выпукла на выпуклом множестве, то для любых точек и любых чисел, таких что выполняется неравенство Йенсена

. (12.9)

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

При этом, если, то и в (12.9) очевидно равенство. Если же. То из выпуклости и индуктивного предположения следует

Говорят, что множество удовлетворяет условию регулярности , если для каждого существует точка такая, что, т.е.

(12.10)

Нетрудно показать, что условию (12.10) эквивалентно другое условие, называемое условием регулярности Слейтера .

Теорема 12.4. Если для множества выполняется условие регулярности (12.10) , то множество регулярно по Слейтеру , а именно существует точка, в которой все ограничения выполняются строго

. (12.11)

Д о к а з а т е л ь с т в о. Пусть выполняется условие регулярности (12.10). Выберем точку, являющуюся выпуклой комбинацией точек и, следовательно, принадлежащую. Тогда при любом будем иметь

т.е. . В этой цепочке соотношений первое неравенство справедливо в силу неравенства Йенсена, а второе поскольку, по крайней мере, один член суммы, а именно строго меньше. Эти неравенства показывают, что для рассматриваемого имеет место условие регулярности Слейтера.

Приведем без доказательства следующее важное свойство выпуклых функций.

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

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

Теорема 12.5. Функция, дифференцируемая на выпуклом множестве, выпукла тогда и только тогда, когда для любых и, принадлежащих выполняется неравенство

. (12.12)

Д о к а з а т е л ь с т в о. Необходимость . Пусть выпукла. Тогда для любых и, () и всех таких, что справедливо неравенство

или

откуда

Переходя к пределу в последнем неравенстве при, получим

Достаточность . Пусть теперь выполняется условие (12.12) для любых двух точек множества. Тогда для точки при, принадлежащей, справедливы неравенства

Умножив первое неравенство на, второе - на и сложив полученные неравенства, имеем

или, учитывая, что имеем

т.е, что выпуклая функция на множестве.

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

Теорема 12.6 . Любая точка локального минимума функции на выпуклом множестве является точкой глобального минимума

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

. (12.13)

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

т.е. . Но это противоречит условию, что - точка локального минимума, поскольку при достаточно малых точка находится в окрестности, где имеет место (12.13).

Следовательно, - точка глобального минимума на.

Теорема 12.7. Множество точек минимума выпуклой функции на выпуклом множестве является выпуклым множеством.

Д о к а з а т е л ь с т в о. Пусть - множество точек минимума выпуклой функции на выпуклом множестве, т.е.

Выберем две любые точки и. Поскольку и - выпуклое множество, то для любого будет

а ввиду выпуклости функции имеем

То есть. Кроме того, поскольку - минимальное значение функции на, то. А, значит, т.е. . Следовательно, - выпуклое множество.

Теорема 12.8. Строго выпуклая функция на выпуклом множестве достигает своего минимума не более чем в одной точке.

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

Пусть =.

Предположим, что найдется точка, такая, что

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

т.е. . Это противоречит условию, что - точка минимума. Следовательно, точка единственна.

Контрольные работы

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

2. Дайте определение выпуклого множества.

3.Приведите формулировку теоремы Фаркаша.

4. Дайте геометрическое истолкование теоремы Фаркаша.

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

6. Приведите примеры выпуклых функций.

7. Сформулируйте условие регулярности множества.

8. Сформулируйте условие регулярности по Слейтеру, множества.

9. Приведите необходимое и достаточное условие выпуклости функции , дифференцируемой на выпуклом множестве .

10. Перчислите основные экстремальные свойства выпуклых функций на выпуклом множестве.

PAGE 131

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

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

1) целевая функция является дифференцируемой и вогнутой, т.е. для нее выполняется условие:

При любых ,

2) а левые части всех ограничений - дифференцируемыми и выпуклыми функциями, т.е. для них выполняются условия:

При любых ,

Тогда задача (4.7)-(4.8) называется задачей выпуклого программирования .

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

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

Введём три определения:

1). Функцией Лагранжа задачи выпуклого программирования (4.7)-(4.8) называется функция:

, (4.9)

2). Говорят, что задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности , если существует хотя бы одна внутренняя точка множества допустимых решений , определяемого строгими неравенствами, полученными из (4.8) (т.е. ).

3). Точка называется седловой точкой функции , если для всех выполнено:

Если целевая функция (убрать)

В теории нелинейного программирования центральное место занимает теорема Куна-Таккера, обобщающая классический метод множителей Лагранжа на случай, когда ограничения нелинейной задачи наряду с ограничениями в виде равенств содержат также и ограничения в виде неравенств.

Теорема Куна-Таккера. Если задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности, то точка является оптимальным решением этой задачи тогда и только тогда, когда существует такая точка с неотрицательными координатами, что является седловой точкой функции Лагранжа данной задачи.

Условия Каруша- Куна- Таккера в дифференциальной форме:

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

Пример .Теорема Куна-Таккера обосновывает сведение задачи выпуклого программирования к задаче поиска седловой точки функции Лагранжа. Чтобы такое сведение имело практический смысл, необходимо, чтобы получившаяся задача была в чём-то проще исходной. Это происходит не всегда, поэтому разработан ряд прямых методов поиска решения нелинейной задачи (4.5), (4.6). Рассмотрим некоторые из них.

(Документ)

Курсовой проект - Стили программирования. Практическая часть - игра 100 спичек (Курсовая)

Лабораторная работа №4. Многомерный поиск. Нелинейное программирование. Методы безусловной минимизации (Лабораторная работа)

Веселов С.Л. Программирование мини-АТС Samsung и Panasonic (Документ)

Презентация - Линейное программирование (Реферат)

Тихомирова Л.С. Методы минимизации булевых функций (Документ)

Кирсанова О.В., Семёнова Г.А. Математическое программирование (типовой расчёт) (Документ)

Козырев Д.В. 1C: Предприятие 7.7 Конфигурирование и программирование. Компонента Бухгалтерский учет. Курс дистанционного обучения (Документ)

Лабораторная работа №1. Безусловная одномерная оптимизация (Лабораторная работа)

Мощевикин А.П. Презентации лекций "Теория принятия решений" (Документ)

n1.doc

Выпуклое программирование. Теорема Куна-Таккера. Условия Куна-Таккера

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

При условиях

(1.3)

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

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

Составим функцию Лагранжа для данной задачи:

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

(1.5)

Теорема 1 (Теорема Куна-таккера). Пусть существует по крайней мере одна точка
, для которой
. Тогда необходимым и достаточным условием оптимальности вектора
, принадлежащего области допустимых решений задачи (1.1)-(1.5), является существование такого вектора
, что для всех и
имеют место неравенства (1.5)

Эту теорему примем без доказательства

Теорема Куна-Таккера также называется теоремой о седловой точке.

Если
и
- дифференцируемые функции, то неравенства в (1.5) эквивалентны следующим локальным условиям Куна-Таккера:

Данные выражения означают, что значения производных берутся в точке
.

1.2. Квадратичное программирование. Метод Баранкина-Дорфмана.

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

При линейных ограничениях

Матрица D предполагается симметрической и неотрицательно определенной. В этом случае функция (2.1) будет выпуклой.

Составим для задачи (2.1) - (2.3) локальные условия Куна-Таккера (1.6) – (1.7), являющиеся необходимыми и достаточными условиями оптимальности решения задачи (2.1) – (2.3).

Функция Лагранжа в данном случае имеет вид:

Найдем частные производные этой функции:

Обозначим

С учетом этих обозначений, соотношений (2.4) и (2.5) условия Куна-Таккера (1.6) – (1.7) примут следующий вид

Равенства (2.6) и (2.7) образуют систему N=n+m линейных уравнений с 2N=2(n+m) неизвестными: .

Итак, в соответствии с теоремой Куна-Таккера решение
задачи (2.1) – (2.3) квадратичного программирования является оптимальным тогда и только тогда, когда совместно с решением
существуют решения
и
такие, что является решением системы (2.6) – (2.8) при условии выполнения равенства (2.9).

Условие (2.9) для задачи (2.1) – (2.3) равносильно выполнению условия

Существует несколько методов решения задачи квадратичного программирования. Рассмотрим один из них – метод Баранкина-Дорфмана.

При этом методе сначала система уравнений (2.6) – (2.7) приводится к виду:

Где (базисные переменные) и
(свободные переменные) являются различными элементами некоторой перестановки переменных , а все являются неотрицательными числами (i=1,2,…,N).

Затем из системы (2.11) находится начальное опорное решение

Системы (2.6) – (2.8), причем компоненты вектора расположены в порядке .

Если для решения выполняется условие (2.10), то задача (2.1) – (2.3) решена и ее оптимальное решение
находится из соответствующих компонент вектора .

Если же для условие (2.10) не выполняется, то для перехода к другому опорному решению составляется нижеследующая таблица (табл. 2.1). В основную часть этой таблицы включаются строки для всех переменных, расположенных в порядке . Для базисных переменных элементы строк берутся из системы (2.11), а для свободных переменных – из соотношений

Параметры же дополнительной части таблицы 2.1 находятся следующим образом:

А) находятся из формулы где - вектор, составленный из элементов s-го столбца основной части таблицы;

Б) для тех s, для которых
, вычисляются остальные параметры:

(элементы соответствующих столбцов, доставляющих минимум , отмечаются звездочкой),
.

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

При этом:

В результате получается новое опорное решение системы (2.6) – (2.8). Этот процесс продолжается до тех пор, пока не будет выполнено условие (2.10). Если же все
, а
, то в качестве начального выбирается другое решение.

1.3 Пример решения задачи методом Баранкина-Дорфмана
Минимизировать функцию

При ограничениях:

;
.

Решение

Находим начальное опорное решение системы (2.12). При этом значение целевой функции равно .

То не выполняется условие (2.10) и, следовательно, решение не является оптимальным.

Составим таблицу 2.2 для перехода к новому опорному решению системы (2.12) - (2.13). Основную часть этой таблицы заполним, используя систему (2.12).

А) для дополнительной части таблицы найдем:

Б) для положительных и вычислим остальные параметры:

Четвертый столбец, которому соответствует наименьший отрицательный , назначаем разрешающим столбцом, строку с элементом 3 этого столбца – разрешающей строкой, а сам элемент 3 – разрешающим элементом, и с их помощью выполняем симплексное преобразование таблицы 2.2.

В результате получаем таблицу 2.3, содержащую новое опорное решение .

Для этого решения

Поэтому заполним дополнительную часть таблицы 2.3 аналогично тому, как это делалось в предыдущем случае, для перехода к новому опорному решению системы (2.12) – (2.13).

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

Тем самым найдено оптимальное решение
, при котором целевая функция Z данной задачи минимизируется. При этом

1.4 Индивидуальное задание: решение задачи методом Баранкина-Дорфмана