Как решать задачу оптимизации

katrinmania

Подскажите, есть ли алгоритм численного решения такой задачи оптимизации:
x'Ex -> min
s.t.
x'A = b
x_i >= 0 для всех i
и нелинейное условие: не больше K элементов x отличны от нуля
(x - вектор Nx1, E - неотрицательно определенная м-ца NxN, A - вектор, b, K - константы)

gala05

можно использовать ГА, который итерационно найдет один из локальных минимумов x'Ex

katrinmania

А он точно это осилит?

yupa33

х=0, что решать-то? А если max! то другое дело.
Это мой диплом кстати только и ограничения квадратичные.

katrinmania

>х=0, что решать-то?
0'A != b
а с квадратичными ограничениями проще гораздо

yupa33

А недочитал дэцл
находишь подпространство X = im(A-bE) и измеряешь до него квадрат растояние от 0.
Это и будет решение, а остальные x_i заменяешь бесконечно малой до к (некорректное условие в задаче)

yupa33

А ещё не дочитал
Е - оказывается произвольная матрица!
Тогда растояние до подпространства X измеряешь относительно меры E, т.е. задача своидится к поиску точки пересечения эллипса с радиусами из собственных векторов и гиперплоскости.

gala05

если бы я не смог придумать аналитического метода или решения, то юзал бы именно ГА (генетические алгоритмы)

katrinmania

Решение есть как минимум одно — решать C_N^K задач и среди них выбрать максимум. Вот только N порядка 300 а денег на такой компьютер у меня нет =)
А как здесь будет ГА работать?

katrinmania

>задача своидится к поиску точки пересечения эллипса с радиусами из собственных векторов и гиперплоскости.
Последнее условие (c K) никак не даст гиперплоскость =)

Zoltan

Решение есть как минимум одно — решать C_N^K задач и среди них выбрать максимум. Вот только N порядка 300 а денег на такой компьютер у меня нет =)

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

katrinmania

отче, проявил бы снисхождение, да подскзал бы по делу! =)

yupa33

говои задачу я тебе посчитаю, или посмотри здесь
www.pitbear.com

katrinmania

я прошу алгоритм

gala05

что значит - как? О_о
как должен, так и будет

katrinmania

то есть ему пофиг, что область невыпуклая и несвязная?

gala05

да, я думаю
Оставить комментарий
Имя или ник:
Комментарий: