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

Категория реферата: Рефераты по экономико-математическому моделированию
Теги реферата: реферат легкая атлетика, баллов
Добавил(а) на сайт: Smetanin.

Для решения задачи (3.1.2) предлагается использовать метод субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.

Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x) на множестве
L, задаваемом ограничениями типа равенств.

|[pic] | |
| |(3.4.1) |

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

|[pic] | |
| | |
| |(3.4.2) |

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

Предположим, что для задачи (3.4.2) нахождение оптимального решения существенно проще, чем для исходной задачи (3.4.1). В этом случае, перебирая каким-либо образом всевозможные множества индексов (k, являющиеся подмножествами полного набора индексов {1,..n}, и решая для каждого из них задачу (3.4.2), используя (k вместо (*, определить искомое множество индексов (*.

Предположим также, что задача (3.4.2) обладает свойством единственности, т.е система векторов {L1, .. Lm, ej (j( ((x*)}- линейно независима. В случае нарушения свойства единственности задача поиска оптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случай рассматриваться не будет.

Алгоритм перебора множеств индексов (k основан на следующей лемме.

Основная лемма:

Пусть x* является оптимальной точкой задачи:

|[pic] |(3.4.3) |

где X( - линейное многообразие, определяемое следующим образом:

|[pic] |(3.4.4) |

Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди (j, удовлетворяющих условиям Куна-Таккера существует отрицательное (j0, т.е.

|[pic] |(3.4.5) |

Пусть ( ' - множество индексов, полученное из ( вычитанием индекса j0:

|[pic] |(3.4.6) |

Тогда, если x*' - оптимальный вектор задачи

|[pic] |(3.4.7) |

то справедливо неравенство:

|f(x*')

Поделитесь этой записью или добавьте в закладки