2
$\begingroup$

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?

  • 1
    Here's a re$f$erence for you: http://dx.doi.org/10.1115/1.29193932011-11-19

1 Answers 1

2

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).