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

[Pruntoff]

Добрый день!

Мне нужно научиться решать задачи квадратичного программирования, но возникли большие трудности с пониманием, если буду жестко тупить, заранее приношу извинения.
Что конкретно меня смущает, приведу пример:

При любом $\lambda ≥ 0$ надо найти N-мерный вектор $x = (x_1, x_2, … , x_n)$, при котором функция
$-\lambda \sum_{i=1}^{N} x_i E_i + \sum_{i=1}^{N}\sum_{j=1}^{N} x_ix_jC_{ij}$
достигает минимального значения (матрица положительно-определена).
Координаты вектора $x$ должны удовлетворять условиям
$\sum_{i=1}^{N}a_{ij}x_{i}=b_{j}$;
$j=\overline{1,m}$;
$x_1 \geq 0, x_2 \geq 0, ..., x_N \geq 0$.

Я почитал Тихомирова и Босса (7 том), для решения ЗКП применяется теорема Каруша-Куна-Такера, с помощью нее можно из задачи нелинейного программирования перейти к задаче ЛП с нелинейным ограничением, вот тут начинаются сложности. Я совершенно не понимаю, что с этим делать. Т.е. я могу записать условие Куна-Такера для целевой функции, а что происходит дальше? Решать условие как СЛАУ? Я абсолютно запутался.
Вот здесь (стр. 6) я нашел пример с решением. В приведенной лекции, я совершенно не понял момент с введением дополнительных векторов $Z, \hat_{Z}$, куда не плюнь, я везде тупой.
Также читал учебник Шведова по портфельной оптимизации (оттуда все и началось), приведено решение с помощью метода Вольфа (симплекс методом), но я опять застрял на введении дополнительных векторов (в том же месте, что и в предыдущем материале) и там совершенно не мой уровень математики, слишком сложно.
Возможно вы сможете дать мне несколько советов, что мне делать, как решать и в какую сторону двигаться?

[мат-ламер]

Pruntoff
В чём сотоит ваша задача? Решить конкретную задачу КП? Руками? Написать программу? Разобраться, как вообще можно решать задачу КП? Разобраться, как можно решать задачу КП каким-то конкретным методом? Каким? (Их несколько десятков). Если вас интересует конкретно метод из вашей ссылки, то я его не знаю. Если вас интересуют методы, основанные на решении системы Куна-Таккера, то да, есть такие. И популярны. Там в условии дополняющей нежёсткости $0$ заменяется на $\varepsilon$. Тем самым происходит некоторая регуляризация.

[Pruntoff]

мат-ламер, спасибо за ответ!

Мне хочется разобраться, как вообще решать задачи квадратичного программирования, план таков:
1) Научиться решать ЗКП
2) Разобраться с алгоритмом Марковица-Шарпа по поиску угловых точек и построением эффективного фронта
3) Заказать программку
4) Использовать это в портфельном анализе
5) Профит.

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

Цитата:

Если вас интересуют методы, основанные на решении системы Куна-Таккера, то да, есть такие. И популярны. Там в условии дополняющей нежёсткости $0$ заменяется на $\varepsilon$. Тем самым происходит некоторая регуляризация.

насколько я понимаю, так или иначе, в ЗКП везде применяется теорема Куна-Такера, иначе ее не решить (поправьте если я ошибаюсь).

Понимаете, моя проблема в том, что я имею набор теорем, которые смутно понимаю, но совершенно не вижу, что с ними делать. Не хватает алгоритма, типа:
1. Выдели условие Куна-Такера из целевой функции
2. Реши получившуюся систему уравнений
3. Найди вектор такой-то такой-то, таким-то способом
4. Используй симплекс метод
и так далее и тому подобное. Сейчас я взял первую попавшуюся задачу, выделил условие, сижу и радуюсь, не знаю, что с этим делать :)

И да, я очень не люблю что-то, что я не понимаю, увы, абстрактные знания - не мое, поэтому я бы очень хотел сесть и действительно руками попробовать решить задачу с тремя неизвестными (я просто нашел ее с ответами, для $\lambda=1$)

[мат-ламер]

Условия теоремы Куна-Таккера - это необходимые условия минимума. Они дают возможность проверить произвольную точку - является ли она минимумом или нет. А решить систему Куна-Таккера - дело очень сложное, поскольку там есть нелинейные уравнения. И тут возникает целая наука и разработано куча методов. Можете попробовать решить задачу с тремя неизвестными. Решите перебором. Для каждого ограничения типа неравенств рассмотреть два случая - когда оно строгое или когда оно равенство. Всего получится 7 вариантов - внутренность симплекса, три ребра и три вершины. Для каждого из семи случаев решите системк Куна-Таккера. Условие дополняющей нежёсткости при таком подходе упростится.

-- Вт окт 14, 2014 21:53:21 --

Pruntoff в сообщении #918818 писал(а):

Не хватает алгоритма

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

-- Вт окт 14, 2014 21:55:01 --

Pruntoff в сообщении #918818 писал(а):

3) Заказать программку

Я думаю, что лучше использовать готовую программу. А вот научиться ею правильно пользоваться - смысл имеет явный.

[Pruntoff]

Спасибо огромное!!

Цитата:

Они дают возможность проверить произвольную точку - является ли она минимумом или нет.

Т.е. решив условие Куна-Такера, я фактически и найду минимум? Вот чего я не понимал.

Цитата:

А решить систему Куна-Таккера - дело очень сложное, поскольку там есть нелинейные уравнения.

В задачах портфельного анализа, как я понял, условие Куна-Такера всегда будет принимать вид СЛАУ с одним нелинейным ограничением.

В общем обязательно попробую. Еще раз спасибо!

[мат-ламер]

мат-ламер в сообщении #918980 писал(а):

Они дают возможность проверить произвольную точку - является ли она минимумом или нет.

Pruntoff в сообщении #919131 писал(а):

Т.е. решив условие Куна-Такера, я фактически и найду минимум? Вот чего я не понимал.

По-отношению к условиям Куна-Таккера термин "решить" применяют редко. Попробуйте потренироваться на двухмерной задаче. Тогда поймёте, что реально означает этот термин.

-- Ср окт 15, 2014 21:10:07 --

Pruntoff в сообщении #919131 писал(а):

В задачах портфельного анализа, как я понял, условие Куна-Такера всегда будет принимать вид СЛАУ с одним нелинейным ограничением.

Сомнительно.