Найти максимум

poojke

Найти max : [(a_1*x_1 + ...+ a_n*x_n)^2]/(b_1*x_1 + ...+ b_n*x_n
где x_i = 0 или 1; a_i, b_i (const) > 0

stream_24

Какое интересует решение и для каких n?
В нуле (0,0,...,0) максимизируемая функция доопределена нулем?
Как задаются параметры a_k, b_k и связаны ли они какими-либо соотношениями?
Возможно, имеет смысл перейти к 0<a_k<=1 и 0<b_k<=1.

poojke

n: любое натуральное
a_k, b_k > 0: нет никакие соотношения
x = (x_1, x_2, ...,x_n) != (0,0,..0)
Почему "имеет смысл" когда "перейти к 0<a_k<=1 и 0<b_k<=1"?

Vlad128

В нуле (0,0,...,0) максимизируемая функция доопределена нулем?
Как задаются параметры a_k, b_k и связаны ли они какими-либо соотношениями?
Первый вопрос не влияет на решение никак, второй тоже надуманный. Не сказано же, зачем выдумывать?

Vlad128

Ты лучше скажи: тебе формула нужна или алгоритм?

stream_24

Если они не связаны никакими вспомогательными соотношениями, то даже в случае n=2 ничего лучше переборного способа не будет.
Видимо, топикстартера интересует алгоритм.

Vlad128

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

gr_nik

А мы по каким параметрам максимизируем? То есть что из a_i, b_i, x_i и n зафиксировано, а что менять можно?

Vlad128

 
где x_i = 0 или 1; a_i, b_i (const) > 0

poojke

"Fractional Programming" будет вспомогательным?

griz_a

Нам надо максимизировать [math]$\frac{(a,x)^2}{(b,x)}$[/math], где a, b - фиксированны по x - вершинам заданного n-мерного куба.
Во-первых, ясно, что можно нормировать a, b, т.к. их нормы дают нам фиксированный множитель.
Теперь повернем систему так, чтобы a перешел в вектор (1, 0, ....0 b - в вектор [math]$(b^{(1)}, b^{(2)}, 0, 0, 0)$[/math] [math]$b^{(1)}=(a,b b^{(2)}=\sqrt{1-(a,b)^2}$[/math],
Тогда, т.к. скалярное произведение инвариантно относительно поворотов, то нам надо будет максимизировать [math]$\frac{x_1^2}{b^{(1)} x_1+b^{(2)} x_2}$[/math] по точкам x_1,...x_n - вершинам n-мерного куба с ребром 1 и вершиной (0, ... 0).
Заметим еще что точка (0,...,0,1,0,...0) при нашем повороте переходит в точку с первыми двумя координатами в новой системе
[math]$b^{(1)} \frac{b_k-a_k (a,b)}{1-(a,b)^2}+\frac{a_k-b_k (a,b)}{1-(a,b)^2}, b^{(2)} \frac{b_k-a_k (a,b)}{1-(a,b)^2}$[/math]
Пока дальше не додумал, но мне кажется, что в этом однопараметрическом семействе парабол выбирать нужную проще...

griz_a

В частности, из точек с положительной ординатой в новой системе сразу остается только точка с наибольшей абциссой, т.к. из выпуклости у остальных x в числителе меньше, а y/x в знаменателе больше.
Из точек с отрицательной надо выбирать из промежутка правее точки с наименьшей ординатой
И ясно, что последние можно выбирать только из тех, в которых содержатся с 1 все x с отрицательными
ординатами в новой системе - добавление каждого такого и y уменьшает и x увеличивает.

poojke

Подскажите как новую систему, новые векторы получить?

griz_a

Мы поворачиваем систему и если надо, симметрично отражаем, так, чтобы плоскость (a,b) стала плоскостью OXY, a стал единичным вектором, b - в 1 квадранте.
Соответственно, после этого нас от точек куба интерсуют только первые две координаты, т.е. проекции на эту плоскость

poojke


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