Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I haven't formulated my problem formally yet. But, the goal is to minimize the squared error i.e. $ (L - \sum_{i=1}^{N}{w_{i}l_{i}})^2$ where $l_{i}$ are constants, $w_{i}$ are weights to be optimized. Weight can only take values in binary space i.e. 0/1. Is there any way to run the optimization on these kinds of problems? I understand that I can formulate the constraints in the form $w_{i}(w_{i}-1) = 0$. But, it leads to exponential number of solutions which are intractable when N is very large.

share|cite|improve this question
I think the title "Least-squares optimization for discrete variables" would be more appropriate. Even if there turns out to be no analogue of Lagrange multipliers for discrete problems, there may still be a different way to efficiently solve your least-squares problem. – Rahul Apr 4 '12 at 3:47
There is such a theory, though I don't understand it well enough to post a full answer:… – Nick Alger Apr 4 '12 at 23:58

Your Answer


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

Browse other questions tagged or ask your own question.