Is Lagrangian Multiplier Equivalent to Brute Force for binary decision variables

Question

I have a set of variables $x_{i} \in \{1,k\} $ in a non linear optimization problem. As this variable has only two possibilities I have encoded this into a constraint. I assumed having equality constraints will be computationally more efficient that having inequality constraint. However I am is doubt whether this assumption always holds or not. Is this assumption correct/safe ?

I have modeled a quadratic equation that yields two values $\{1,k\}$ for $x_{i}$ and added that equation as an equality constraint that equals to $0$. After building the lagrangian partial derivatives brings down the exact quadratic equations in the non linear system of equations. Thus solving this system of equation actually requires all possibilities of $x_{i}$ to be applied on other variables and calculate entire optimality region. It looks like kind of brute force. So I drew to the conclusion that in cases of binary possibility of decision variables using lagrangian multipliers is actually equivalent to doing brute force. Is this a correct conclusion ?

Will penalty method or Augmented Lagrangian converge faster in such cases ?

Answer 1

Of course if $x_{i} \in \{1,k\}$, or equivalently $(x_i - 1)(x_i - k) = 0$, is part of the constraints then you won't get any simpler in the KKT system. Theoretically speaking, depending on the other equations of the system, one may obtain a solution to the problem (which is specific) without doing brute force. However, for discrete optimization problems, like yours, the direct KKT system is in general even more difficult to solve than the original problem.

A usual approach for solving a discrete optimization problem is to solve its continuous relaxation, followed by a rounding step.

For example, you can perform a change of variables: $y_i = \frac{x_i - 1}{k - 1}$ to obtain $y_i \in \{0,1\}$ and then try solving the problem with the relaxed constraints $0 \le y \le 1$, which should be easier.