2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Задача квадратичного программирования
Сообщение13.10.2014, 11:42 


13/10/14
3
Добрый день!

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

При любом $\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}$, куда не плюнь, я везде тупой.
Также читал учебник Шведова по портфельной оптимизации (оттуда все и началось), приведено решение с помощью метода Вольфа (симплекс методом), но я опять застрял на введении дополнительных векторов (в том же месте, что и в предыдущем материале) и там совершенно не мой уровень математики, слишком сложно.
Возможно вы сможете дать мне несколько советов, что мне делать, как решать и в какую сторону двигаться?

 Профиль  
                  
 
 Re: Задача квадратичного программирования
Сообщение13.10.2014, 21:23 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача квадратичного программирования
Сообщение14.10.2014, 10:43 


13/10/14
3
мат-ламер, спасибо за ответ!

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Задача квадратичного программирования
Сообщение14.10.2014, 20:50 
Заслуженный участник


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

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

Pruntoff в сообщении #918818 писал(а):
Не хватает алгоритма

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

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

Pruntoff в сообщении #918818 писал(а):
3) Заказать программку

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

 Профиль  
                  
 
 Re: Задача квадратичного программирования
Сообщение15.10.2014, 10:09 


13/10/14
3
Спасибо огромное!!

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


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

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


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

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

 Профиль  
                  
 
 Re: Задача квадратичного программирования
Сообщение15.10.2014, 20:09 
Заслуженный участник


30/01/09
4694
мат-ламер в сообщении #918980 писал(а):
Они дают возможность проверить произвольную точку - является ли она минимумом или нет.

Pruntoff в сообщении #919131 писал(а):
Т.е. решив условие Куна-Такера, я фактически и найду минимум? Вот чего я не понимал.

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group