Hi everyone!

This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called Aliens). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs, e. g., in linear programming problems.

Lagrange multipliers

Let $$$f : X \to \mathbb R$$$ be the objective function and $$$g : X \to \mathbb R^c$$$ be the constraint function. The constrained optimization problem

in some cases can be reduced to finding stationary points of the Lagrange function

Here $$$\lambda \cdot g(x)$$$ is the dot product of $$$g(x)$$$ and a variable vector $$$\lambda$$$, called the Lagrange multiplier. Mathematical optimization typically focuses on finding stationary points of $$$L(x,\lambda)$$$. However, in our particular case we're more interested in the function

which is called the Lagrange dual function. If $$$x^*$$$ is the solution to the original problem, then $$$t(\lambda) \leq L(x^*,\lambda)=f(x^*)$$$.

This allows to introduce the Lagrangian dual problem $$$t(\lambda) \to \max$$$. Note that $$$t(\lambda)$$$, as a point-wise infimum of concave (specifically, linear) functions, is always concave, even when the set $$$X$$$ is, e.g., discrete. If $$$\lambda^*$$$ is the solution to the dual problem, it holds that

for arbitrary $$$x$$$ and $$$\lambda$$$. The value $$$f(x^*) - t(\lambda^*)$$$ is called the duality gap and we're specifically interested in the case when it is equals zero, which is called then the strong duality.

References

• Duality (optimization) — English Wikipedia
• The Trick From Aliens — Serbanology
• My Take on Aliens' Trick — Mamnoon Siam's Blog
• Comment on Codeforces by _h_
• Part of the article was once revealed to me in a dream