Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Would anyone mind helping me solve this problem

$$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$

where $x$ is a vector whose entries are positive integers and $Q$ is positive definite.

share|improve this question
    
In which context did you encounter this problem? –  Stefan Kohl Jun 28 '13 at 9:51
    
Actually the problem is that there are some integers which their summation is constant and I want to minimize the variance of them (which is a quadratic programming problem). I'm electrical engineering M.Sc. student. In my thesis I encountered this problem. –  Mahdi Khosravi Jun 28 '13 at 10:01
    
Could you tell us what exactly $Q$ and $b$ are? I think mathematica has some tools to help. –  Ali Jun 28 '13 at 11:05
    
yes they are integer-valued. actually, Q= 2*(I + [1]), b=λe where I is the Identity matrix and [1] is a matrix who all its elements are 1 and e = [1 1 .... 1]'. –  Mahdi Khosravi Jun 28 '13 at 11:40
    
If you know the sum of n integers you know there average and the variance will be minimized with the integers as close to the average as possible so I think you will have to consider at most two integers, the two closest to the average or the average itself if that is an integer. –  Kristal Jun 28 '13 at 16:47
show 1 more comment

migrated from mathoverflow.net Jul 4 '13 at 19:47

This question came from our site for professional mathematicians.

1 Answer

up vote 1 down vote accepted

These kinds of (mixed) integer quadratic programming (MIQP) problems are typically solved by branch and bound algorithms. One widely used commercial code is IBM's CPLEX. You might also be interested in Sven Leyffer's MIQPBB code.

More general codes for mixed integer nonlinear programming (MINLP) can also be used for this problem. See for example the BonMin code.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.