квадратичная задача математического программирования

[mas]

Оптимизационная задача имеет квадратичную целевую функцию и квадратичные ограничния. (Т.е. все выражения представляют собой суммы переменных, их произведений и квадратов, домноженных на различные коэффициенты и свободных членов.)
Размерность задачи очень велика. Можно ли её решить за приемлемое время?
Мне известно о существовании модификации симплекс-метода, позволяющей решать задачи с квадратичными целевыми функциями и линейными ограничениями, нельзя ли что-то аналогичное применить и к моему случаю ? (Или хотя бы каков будет наиболее подходящий чисто нелинейный алгоритм.)

[reader_st]

mas

Если Вы хотите применить уже известный метод к Вашей задаче, то просто линеаризуйте ограничения и все, но точность... Если ли обоснования сходимости?. Я полагаю, что ОДЗ образованное, ограничениями представляет собой довольно сложную конструкцию. Если это не так, то мое предложение --- метод проекции градиента, учтете ограничения, есть четкое обоснование сходимости. Если Вам не принципиальна теория, то можно получить решение в СКМ Maple, например, Maple 10 содержит богатый набор функций, для некоторых даже не нужно задавать начального приближения.

Попробуйте, также привести квадратичную форму к каноническому виду.

[mas]

reader_st писал(а):

mas
Я полагаю, что ОДЗ образованное, ограничениями представляет собой довольно сложную конструкцию.

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

reader_st писал(а):

mas
Если Вам не принципиальна теория...

Если найдётся алгоритм с подходящей временной сложностью -- буду писать программу для практического использования.

[reader_st]

mas

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