Оптимизация.

[Alex-Yu]

В процессе заняти некой инженерной проблемой у меня возникла такая задача оптимизации:

$$ \left\{ \begin{array}{l} x^+Ax \to {\rm max} \\ 0<x^+B_1x\le 1 \\ \dots \\ 0<x^+B_Nx\le 1 \end{array} \right. $$

$x$ -- комплексный вектор-столбец размерностью $N$, матрицы $A$ и все $B_k$ эрмитовы, крест -- эрмитово сопряжение, $A$ положительно полуопределена (неотрицательно определена), ранг всех матриц $B_k$ ровно двойка, причем одно ненулевое собственное число положительно, другое -- отрицательно.

Прежде всего мне бы хотелось понять, а вообще реально ли решить такую задачу в том или ином смысле аналитически. Или тут метод монте-карло и ничего другого не придумать. Интересует конкретная реализация алгоритма решения, всякие теоремы -- лишь постольку, поскольку они выводят на конкретный алгоритм.


Известна задача линейного програмирования. Тут своего рода "задача квадратичного програмирования". Никогда не слышал про такое. Но может такое есть и можно где-нибудь почитать? Оптимизация --- не моя область, могу и просто не знать.

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

[Oleg Zubelevich]

максимум достигается на границе области

[Alex-Yu]

Oleg Zubelevich в сообщении #745406 писал(а):

максимум достигается на границе области

Это я и сам знаю. Мне нужен конкретный вектор, в цифирьках. Точнее алгоритм его вычисления.

[Aer]

Тема перемещена из форума «Помогите решить / разобраться (Ф)» в форум «Помогите решить / разобраться (М)»

[Oleg Zubelevich]

метод множителей Лагранжа

[Alex-Yu]

Oleg Zubelevich в сообщении #745414 писал(а):

метод множителей Лагранжа

А как искать лагранжевы множители? Эффективно в вычислительном отношении искать.

[Oleg Zubelevich]

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

[Alex-Yu]

Oleg Zubelevich в сообщении #745420 писал(а):

аналитическое решение -- это только если очень повезет.

ОК. Остается монте-карло? Мне, собственно, не важно элементарные функции, не элементарные. Лишь бы можно было на компьютере посчитать.

На сколько я понимаю, тут нет даже системы квадратных УРАВНЕНИЙ. Тут система неравенств. Или не так?

[Oleg Zubelevich]

думаю да. любые другие методы приведут к сложностям из-за неединственности решения

-- Пт июл 12, 2013 15:48:46 --

Alex-Yu в сообщении #745421 писал(а):

На сколько я понимаю, тут нет даже системы квадратных УРАВНЕНИЙ. Тут система неравенств. Или не так?

содержательно всетаки будет именно система уравнений, неравенства проверяются после того как решения уравнений найдены

[Alex-Yu]

Oleg Zubelevich в сообщении #745423 писал(а):

думаю да. любые другие методы приведут к сложностям из-за неединственности решения

ОК. Ваше предложение понятно. Посмотрим кто еще что скажет. Собственно неединственность --- не так уж страшно. Можно просто перебрать все решения (врядли тут бесконечный набор).

[Oleg Zubelevich]

может и бесконечный. даже если нет -- то отлавливать все решения нелинейной системы численно (с помощью скажем метода Ньютона) это кропотливая работа

[Alex-Yu]

Oleg Zubelevich в сообщении #745423 писал(а):

содержательно всетаки будет именно система уравнений, неравенства проверяются после того как решения уравнений найдены

Вот это мне не ясно. Вот если бы ранг всех $B_k$ был бы $N$.... А если бы были еще и положительно определены, то вообще делать нечего, я бы и вопросов не задавал.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Математика (общие вопросы)»

[Nemiroff]

Alex-Yu в сообщении #745400 писал(а):

Известна задача линейного програмирования. Тут своего рода "задача квадратичного програмирования". Никогда не слышал про такое. Но может такое есть и можно где-нибудь почитать? Оптимизация --- не моя область, могу и просто не знать.

QCQP - http://en.wikipedia.org/wiki/QCQP
Может, пригодится, там ссылки на некоторые солверы есть.

[Alex-Yu]

Nemiroff в сообщении #745915 писал(а):

QCQP - http://en.wikipedia.org/wiki/QCQP
Может, пригодится, там ссылки на некоторые солверы есть.

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