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


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

min xn, где D = {x|gi(x) ≥ 0, i = 1,2, …, m}. (7.97)

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

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

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

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

min x2 при условии, что — 1 ≤ x1 2; (7.98)
x2 ≤ 4; gi (х) ≥ 0,

которая имеет локальный минимум в точке х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 = D0. В качестве новой внутренней точки выбирается точка xBk ∈ D, полученная из наиболее удаленной от хλr точки хKr (пересечения касательной плоскости Гr (х) = 0 с границей области D) по следующей формуле:

хBk = хrK + (0, 0, …, 0, δ),

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

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



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

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



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

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

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

В задачах выпуклого программирования локальный минимум одновременно является и глобальным минимумом. Однако, если предположение о выпуклости допустимой области D снять, то это утверждение будет уже несправедливо. В связи с этим рассмотрим алгоритм, в котором задаче невыпуклого программирования:
min (cT, x), где D = {x|gi(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 = ∑ρxk для всех х∈D⊆D*, (7.101)

где вектор ρ = (ρ1, …, ρs).

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

D* = {x|x = ∑∑jxj} (7.102)

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

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

D = ∪Dj, (7103)

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

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

Dj = ajD0 +Vj, j = 1,2, …,s. (7.104)


Комментарии запрещены.




Статистика