An optimization method to find local minima or maxima of integer/combinatorial problems efficiently.
1. Summary
Let us consider an example of integer problem
\[ \max_{x} f(x) \text{ s.t. } x\in \{0, 1 \} \]
Then, the above problem can be rewritten as \(\max_{x} f(x), s.t. x\in[0,1], x-x^2\le0\) without loss of generality.
The abstract Lagrangian of the original problem can be defined by
\[ \max_{x} L(x,\mu)=f(x)-\mu(x-x^2), x\in[0,1] \]
2. Principal of the abstract Lagrangian Duality
For large values of \(\mu_i\), the optimization problem of abstract duality is equivalent to the original problem,
which means \(d^* = \min_{\mu}\max_{x}L(x,\mu)=\max_{x}\min_{\mu} L(x,\mu)=p^*.\)