inner product maximization with constraints

[vr7]

Hello,

I'm trying to maximize the inner product between two vectors (one is fixed), subject to the fact that the sum of the elements of the vector with respect to which I want to optimize is equal to a fixed number. The vector with respect to which I have to maximize must contain integer values.

In math it would be:

max_{y} x^{T} * y
s.t. sum(y) == Q & int(y) == y

Although it seems a convex problem I'm not able to solve it with KKT.

This is the code:

x = zeros(256, 1);

p = 0.003;

for b = 1:256

     pb = p * (1 - p)^(b-1);

      x(b) = pb;

end

Q = 512;

% Setup the problem using YALMIP

y = intvar(256, 1); 

obj = sum(x.*y);

cons = [sum(y) == Q];

sol = optimize(cons,-obj);

y = value(y);

The solution that I obtained is that the vector y is all zeros, and this is clearly not the maximum result for the inner product that I can have. Moreover, I obtain the message:

Root LP problem is unbounded.
Intlinprog stopped because the root LP problem is unbounded.

Could you please help me?

Thank you.

[Johan Löfberg]

that problem is trivially unbounded. simply let the y corresponding to the largest x tend to infinity, and the counter-act that with some other elements tending to -infinity but slightly less so that the sum is Q

[Johan Löfberg]

such as [r;zeros(256-2,1);-r+Q]  where you r tend to infinity

[vr7]

Thank you very much! This is clear now.

Would be in your opinion this problem:

max_{y} x^{T} * y

s.t. sum(y) == Q & int(y) == y & (y_i <=8 for all I)

solvable with KKT? I tried but I can only get the value of the multiplier associated with the first equality constraint if and only if I set one of the multipliers associated with the inequality constraints to zero. In that case, I obtain the same solution as YALMIP.

In YALMIP I obtained a reasonable solution with this code:

x = zeros(256, 1);

p = 0.003;

for b = 1:256

     pb = p * (1 - p)^(b-1);

      x(b) = pb;

end

Q = 512;

% Setup the problem using YALMIP

y = intvar(256, 1); 

obj = sum(x.*y);

cons = [y<=8, sum(y) == Q];

sol = optimize(cons,-obj);

y = value(y);

Thank you.

[Johan Löfberg]

since y is integer, there is no kkt duality theory

[vr7]

Many thanks!