Semenalidery.com

IT Новости из мира ПК
5 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Задача выпуклого программирования

Задача выпуклого программирования

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

(4.7)

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

, (4.8)

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

при любых ,

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

при любых ,

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

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

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

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

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

,

, (4.9)

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

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

(4.10)

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

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

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

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

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

,

,

,

Пример.

Найти максимум функции

на множестве допустимых решений .

Решение:

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

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

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

.

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

Ответ:

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

Электронная библиотека

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

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

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

Рис. 3.3. Выпуклая функция

Рис. 3.4. Вогнутая функция

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

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

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

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

где – выпуклые функции; R – выпуклое множество. Это просто другая форма задачи.

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

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

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

Если бы функции ограничений были выпуклы, то для определяемого множества Х (3.14) выпуклость уже бы не следовала. В этом случае можно доказать выпуклость множества:

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

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

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

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

Если функция строго вогнута (строго выпукла) на выпуклом множестве Х, то у нее может быть только одна точка максимума (минимума).

Предположим противное, т.е. что существует две точки , , являющиеся точками максимума строго вогнутой функции на Х. Обозначив , имеем . Тогда для любого справедливо:

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

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

Обозначим матрицу вторых частных производных через .

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

то строго выпукла (строго вогнута).

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

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

Читать еще:  Выйти в безопасный режим xp

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

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

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

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

Однако нельзя утверждать на основании теоремы 1, что она имеет седловую точку, так как множество R не обязательно является замкнутым и ограниченным, а Y заведомо неограниченно. Тем не менее, можно ожидать, что при некоторых условиях седловая точка все же будет существовать.

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

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

То, что условие Слейтера является существенным, показывает следующий пример.

Дана задача выпуклого программирования:

Здесь, очевидно, что x = 0 есть решение задачи, но у функции Лагранжа седловой точки нет, так как внешняя грань в минимаксной задаче не достигается:

Разбиение ограничений в задаче выпуклого программирования на и , как уже говорилось, является условным. Поэтому обычно под R понимается множество простого вида, это либо все пространство En, либо неотрицательный ортант, либо параллелепипед. Сложность же задачи выпуклого программирования определяется системой ограничений:

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

Если множество R совпадает с En, то условия экстремума, как известно, имеют вид:

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

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

Вспомним, что градиент функции равен:

Таким образом, для нахождения седловой точки функции Лагранжа на произведении , а следовательно, и для нахождения решения задачи выпуклого программирования при R=En надо решить систему уравнений (3.16). Но в этой системе n уравнений, а неизвестных n+m, так как помимо n-мерного вектора нам неизвестен и m-мерный вектор множителей Лагранжа . Однако для седловой точки функции Лагранжа выполняется очень важное свойство:

Из уравнения (3.17) вытекает, что либо , либо , либо то и другое одновременно. Это свойство аналогично второй теореме двойственности (подразд. 2.5) линейного программирования. Ограничения, которые выполняются в некоторой точке как равенства, называются активными.

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

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

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

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

Если R является неотрицательным ортантом, т.е.

то для каждой компоненты решения задачи выпуклого программирования возможны две альтернативы: либо , либо . Для первой альтернативы условия оптимальности совпадают со случаем R=En, т.е. имеют вид (3.16) (при данном j). Для второй альтернативы это не так.

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

т.е. функция должна не возрастать по при движении внутрь области .

Но так как , то можно записать:

Объединяя обе альтернативы, т.е. учитывая выражения (3.16), (3.19), (3.20) для задачи выпуклого программирования в случае, можно представить в виде

Так как , то из условий (3.21) следует, что либо , либо . Таким образом, как и в случае R=En, имеем n уравнений, которые вместе с уравнениями для активных ограничений определяют и .

Найти при ограничении .

Здесь . Функция линейная и поэтому максимум достигается на границе допустимого множества. Используя условия (3.18), имеем систему трех уравнений с тремя неизвестными:

(другое решение дает минимум).

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

Задачи выпуклого программирования

Общий подход к решению задач нелинейного программирования.

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

Задача нелинейного программирования (задача НП) в общем виде формулируется следующим образом :

1(x1 ,x2 ,…, xn ) 1,

m(x1 ,x2 ,…, xn ) m,

где хотя бы одна из функций f, 1, 2. m не линейна.

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

1) в определении внутри допустимого множества всех стационарных точек функции f, удовлетворяющих условию =0; j=1,2,…, n;

2) в определении той стационарной точки, которая доставляет наибольшее значение функции f внутри области;

3) в нахождении максимума функции f внутри каждой границы области и выборе наибольшего ее значения по всем границам;

4) в нахождении наибольшего значении функции f в вершинах области;

5) в нахождении глобального максимума функции f.

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

Читать еще:  Язык программирования паскаль доклад кратко

Задачи выпуклого программирования

Определение I. Множество называется выпуклым, если отрезок, соединяющий любые две точки множества, также принадлежит этому множеству. Ниже приводятся графические примеры выпуклых (a) и невыпуклых (b) множеств. ( рис. 1)

Задача выпуклого программирования

Если хотя бы одна из этих функций — нелинейная или содержит произведения искомых переменных, то соответствующая задача — это задача нелинейного программирования. Среди них наиболее изучены задачи выпуклого программирования, в результате решения которых определяют минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. [c.104]

Из задач выпуклого программирования подробно разработаны задачи квадратичного программирования, в которых требуется найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных уравнений. [c.104]

Рассматриваемая стохастическая задача при этом преобразуется в детерминированную задачу выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.69]

Утверждение 3.2. Задача (3.98) -(3.1 00), (3.104) является задачей выпуклого программирования. [c.80]

Таким образом, приближенный детерминированный аналог многоэтапной стохастической задачи (3.92) -(3.96) при сделанных допущениях оказывается задачей выпуклого программирования, решение которой может быть осуществлено известными методами [46, 56]. [c.84]

Задача (3.120) —(3.123) является задачей выпуклого программирования с вогнутой целевой функцией и линейной системой ограничений. [c.85]

Модель (4.20) — (4.22), (4.25) является статической энтропийной моделью ЗОК. Она представляет собой (ввиду выпуклости каждого слагаемого и в связи с известной теоремой [56] о выпуклости функции, равной сумме выпуклых функций) задачу выпуклого программирования с ограничениями транспортного типа. [c.119]

Так как задача (4.29) — (4.31) является задачей выпуклого программирования, то к ней может быть применен любой из известных алгоритмов решения. Однако специальный тип ограничений обусловил возможность [c.125]

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

Наряду с (4.64) рассмотрим задачу выпуклого программирования с линейными ограничениями [c.133]

Согласно теореме 1 это задача выпуклого программирования. [c.36]

Запись многих задач стохастического программирования в терминах гильбертова пространства Hin более прозрачна, чем в первичных вероятностных терминах. Ряд естественных для стохастических задач целевых функций оказываются линейными или выпуклыми функционалами в Hin. Некоторые ограничения, используемые в разных постановках задач стохастического программирования, высекают в Htn выпуклые множества. Таким образом, многие задачи стохастического программирования могут рассматриваться как задачи выпуклого программирования в гильбертовом пространстве Н п. [c.20]

Рассмотрим задачу выпуклого программирования в банаховом пространстве В [c.23]

Таким образом, детерминированный эквивалент стохастической транспортной задачи представляет собой задачу выпуклого программирования [c.36]

При принятых допущениях об информационной структуре модели детерминированный эквивалент задачи перспективного планирования представляет собой следующую задачу выпуклого программирования [c.61]

В 1—2 рассматриваются стохастические задачи с вероятностными ограничениями, порожденные моделями линейного программирования. В 1 оператор вероятности применяется к каждой строке ограничений в отдельности, а в 2 — одновременно к совокупности всех ограничений. В обоих параграфах рассматриваются такие распределения случайных параметров условий, при которых эквивалентные детерминированные задачи оказываются задачами выпуклого программирования. Параграф 3 посвящен построению эквивалентных детерминированных моделей для общей одноэтапной стохастической задачи с вероятностными ограничениями, порожденной, вообще говоря, нелинейной моделью математического программирования. В 4 рассматриваются две простые, но представляющие интерес для приложений частные модели стохастических задач, в которых решения определяются в детерминированных векторах. Параграфы 5—6 посвящены стохастическим моделям оценки невязок с детерминированными оптимальными планами. В 5 рассматривается классификация таких моделей. В 6 исследуются условия, при которых соответствующие детерминированные эквивалентные задачи являются задачами выпуклого программирования. Ясно, что только в таких случаях можно говорить о конструктивных методах решения задачи. [c.62]

При сделанных предположениях линейная стохастическая задача (1.1) — (1.3), решение которой определяется в решающих правилах нулевого порядка, сводится к детерминированной задаче выпуклого программирования с линейной целевой функцией и квадратичными ограничениями. [c.66]

Задача (1.18) — (1.20) представляет собой задачу выпуклого программирования. Для решения ее может быть использован метод секущих плоскостей или один из вариантов метода возможных направлений. [c.69]

Оптимальный план полученной задачи выпуклого программирования равен =(0 0,68) А = 0,346. , [c.69]

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

Во всех этих случаях задача (2.1) — (2.4) — задача выпуклого программирования. Однако левые части ограничений (2.3) не являются выпуклыми вверх функциями. Замена условий (2.3) эквивалентными неравенствами [c.72]

Пусть два распределения случайных векторов b приводят к выпуклым детерминированным задачам вида (2.1) — (2.4). Тогда их свертке соответствует также задача выпуклого программирования. [c.74]

Пусть распределение Рь(Б) — компонент случайного вектора в задаче с вероятностными ограничениями — приводит к эквивалентной задаче выпуклого программирования. Тогда и распределение Fb[h(B)], где h(S) — неотрицательная выпуклая вниз возрастающая функция, не равная тождественно постоянной, сводит стохастическую задачу к эквивалентной детерминированной задаче выпуклого программирования. [c.74]

В этих обозначениях задача выпуклого программирования — детерминированный эквивалент задачи (1.1) — (1.3) — принимает вид [c.87]

К- задаче выпуклого программирования может быть сведена и -Р-модель [c.87]

Запишем задачу выпуклого программирования в Hni в виде [c.123]

Мы пришли к решающему правилу вида (7.12). Вычисление параметров К г сводится к решению детерминированной задачи выпуклого программирования, которая может быть получена подстановкой х из (9.19) в условия задачи (7.1) — (7.2). Легко видеть, что сформированная при этом задача может быть приведена к виду (7.11). [c.131]

В предыдущем пункте использованы процедуры итеративных методов решения задач выпуклого программирования в функциональных пространствах для установления вида решающих правил некоторых задач стохастического программирования. Следует, однако, подчеркнуть, что в приведенных рассуждениях существенной была не столько схема 1эе [c.132]

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

Смотреть страницы где упоминается термин Задача выпуклого программирования

Приближенное решение задач оптимального управления (1978) — [ c.373 ]

Читать еще:  Запуск пк в безопасном режиме

Образовательный блог — всё для учебы

Рассмотрим задачу нелинейного программирования следующего
вида:

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

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

Предположим, что имеется «внутреннее» множество допустимой области D = i(х) > 0, i = 1, 2, …, m>в котором определена начальная внутренняя точка xB∈D (Для задач невыпуклого программирования это принципиальное требование, которое должно быть обязательно выполнено.)

Применение рассмотренного ранее метода опорной гиперплоскости в случае невыпуклой допустимой области D может привести к решению, которое значительно отличается от точки истинного минимума x* задачи (7.97). В качестве примера рассмотрим задачу невыпуклого программирования:

которая имеет локальный минимум в точке х1* = (—0,33; 1,4) и глобальный минимум в точке x2* = (2; —1). Применение алгоритма для решения задачи (7.98), как видно из рис. 7.7, позволяет получить только точку локального минимума х1*.

Рис.7.7. Поиск точки минимума в невыпуклой области D при помощи метода опорной гиперплоскости

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

Во-первых, при образовании области D1 r для задачи линейного программирования, решаемой на r-м шаге, применяется следующее дополнительное правило. Если касательная плоскость Гr(х) = 0 пересекает границу допустимой области D в нескольких точках, то отсекающая плоскость Гr (х) ≥ 0 на следующем шаге не включается в систему ограничений, а задача линейного программирования решается в области Drr = D. В качестве новой внутренней точки выбирается точка xB k ∈ D, полученная из наиболее удаленной от хλ r точки хK r (пересечения касательной плоскости Гr (х) = 0 с границей области D) по следующей формуле:

где δ — заданная положительная константа.

Задача определения числа точек пересечения касательной плоскости Гr (х) = 0 с границей области D является одномерной задачей минимизации многоэкстремальной функции и может быть решена с помощью одного из методов глобального поиска, рассмотренного ранее. Если граница области D имеет с гиперплоскостью Гr (х) = 0 единственную точку пересечения в хα r то касательная плоскость применяется как отсекающая плоскость, а задача линейного программирования решается в области Dr+1 = Dr∩Гr(х) ≥ 0, т. е. в многограннике D, без той его части, где Гr (х)

Рис. 7.8. Пример поиска точки минимума X* в невыпуклой области, иллюстрирующий использование первого дополнительного правила

Во-вторых, для заданной внутренней точки хB 0 ∈ D модифицированный метод опорной гиперплоскости должен не просто сходиться к расположенному рядом с точкой хB 0 локальному минимуму, а на каждой итерации пытаться выйти из зоны его притяжения, чтобы попасть в зону следующего более глубокого минимума. С этой целью проверяется, принадлежит ли точка xЛ r , (оптимальное решение задачи линейного программирования, полученное на r-м шаге) области D. Если нет, то поиск по эвристическому алгоритму аналогичен поиску по методу опорной гиперплоскости и ведется в области Dr+1 = Dr∩Гr(х) ≥ 0. В противном случае, если имеется несколько пересечений отрезка хЛ r хα r с границей области D, точка хЛ r ∈D считается новой внутренней точкой и относительно нее весь процесс поиска повторяется сначала. При этом все отсекающие плоскости, полученные для старой внутренней точки, из рассмотрения исключаются, и алгоритм продолжает поиск на (r + 1)-й итерации в области Dr+1 = D. На рис. 7.9 приведен пример, иллюстрирующий использование второго дополнительного правила для поиска точки минимума х* с помощью эвристического алгоритма в невыпуклой области D.

Рис. 7.9. Пример поиска точки минимума X* в невыпуклой области, иллюстрирующий использование второго дополнительного правила

Для локализации точки глобального минимума х* задачи невыпуклого программирования (7.97) необходимо многократное применение эвристического алгоритма из разных внутренних точек хB k ∈ D, k = 1,2, …, N, расположение которых в допустимой области D задается, например, случайным образом.

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

В задачах выпуклого программирования локальный минимум одновременно является и глобальным минимумом. Однако, если предположение о выпуклости допустимой области D снять, то это утверждение будет уже несправедливо. В связи с этим рассмотрим алгоритм, в котором задаче невыпуклого программирования:
min (c T , x), где D = i(x) ≥ 0, i = 1,…, m> (7.99) — невыпуклое множество, ставится в соответствие задача выпуклого программирования:
min (с T , х), где D* — выпуклое множество. (7.100)

При ЭТОМ задачи (7.99) и (7.100) считаются эквивалентными в том смысле, что оптимальное решение задачи (7.100) х* совпадает с точкой глобального минимума х* задачи (7.99). В качестве допустимой области D* можно рассматривать выпуклую оболочку множества D, которая включает в себя все точки допустимой области. В том случае, когда область D — не выпуклое или многосвязное множество, образованное системой неравенств, выпуклая оболочка D* строится в вида замкнутого выпуклого многогранника, являющегося линейной комбинацией своих крайних точек х k , k = 1, 2, …, s:

x = ∑ρx k для всех х∈D⊆D*, (7.101)

В дальнейшем под выпуклой оболочкой D* допустимой области D будем понимать множество всех линейных комбинаций точек из D:

Общей методики построения выпуклой оболочки D8, связанной о задачей выпуклого программирования (7.100), пока не существует.

Поэтому рассмотрим вопрос построения множества D* в частном случае, когда невыпуклая область D является объединением конечного числа выпуклых множеств:

где Dj = j (х) ≥ 0>, j = 1, 2, …, s, — выпуклые множества.

Кроме этого будем считать, что каждая область Dj задается при помощи обратимого преобразования базового выпуклого множества D, в качестве которого может быть выбрано любое из множеств Dj:

Ссылка на основную публикацию
Adblock
detector