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.

Is there a way to adapt the method of Lagrange multipliers to problems involving discrete variables? Unfortunately I don't have a specific problem to ask here (I haven't completely formulated it yet), but I do know that in this hypothetical problem the variables involved will have to be binary values. Thanks for any references or tips!

Edit: Here's an example of the type of problem I'm interested in solving. Given $ \sum_{i=1}^{n} A_nx_n$ for any $B \in R$ and $A_n \in R$ I want to find the sequence of $x_n$s that minimizes the squared error $[(\sum_{i=1}^{n} A_nx_n) - B]^2$ given arbitrary weights $A_n$, with the constraint that each $x_n$ can be binary valued (1 or 0).

Obviously if N is small I could just test every sequence, but if not?

share|improve this question
1  
Here's a reference for you: dx.doi.org/10.1115/1.2919393 –  process91 Nov 19 '11 at 5:14

1 Answer 1

up vote 1 down vote accepted

The constraint $x \in \{0,1\}$ can be formulated as $x (x-1) = 0$ and then you can use the usual KKT conditions. There are reports that this doesn't work very well in practice but I'll admit I haven't really tried it myself. You can apply a similar trick if $x$ is constrained to take only a finite number of integral values, e.g., $x \in \{1,2,3\}$ can be written $(x-1)(x-2)(x-3)=0$. Clearly, the larger the number of values allowed, the higher the degree of the polynomial in the constraint and the more likely you are of getting stuck at a local solution. Also this doesn't generalize to the condition $x \in \mathbb{N}$. That's why there is an entire field dedicated to this kind of problem, called mixed-integer nonlinear programs (or MINLPs).

share|improve this answer

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.