# Equivalence of constraint and regularizer under strong duality

## Question

Consider the constrained optimization problem in $\mathbb{R}^{n}$

\[\min_{x} \; f(x) \quad \text{s.t.} \quad h(x) \le \tau\]and the regularized optimization problem

\[\min_{x} \; f(x) + \lambda h(x)\]The question is: for each value of $\tau$, does there exist some $\lambda$ such that a minimizer of the constrained problem is also a minimizer of the regularized problem?

## Method

Let $x^{\star}$ denote a minimizer of the constrained problem, which therefore satisfies $h(x^{\star}) \le \tau$ (feasibility). We seek to show that $x^{\star}$ is also a minimizer of the regularized problem.

Let us consider the Lagrangian dual of the constrained problem, introducing the scalar dual variable $\alpha$.

\[L(x, \alpha) = f(x) + \alpha (h(x) - \tau)\]The dual function is obtained by the unconstrained minimization

\[g(\alpha) = \min_{x} L(x, \alpha) = \min_{x} \{ f(x) + \alpha (h(x) - \tau) \}\]and the dual problem is

\[\max_{\alpha} \; g(\alpha) \quad \text{s.t.} \quad \alpha \ge 0\]Let $\alpha^{\star}$ denote a maximizer of the dual problem, which therefore satisfies $\alpha^{\star} \ge 0$ (dual feasibility).
If the constrained problem possesses *strong duality* (for example, by Slaterâ€™s condition), then we know that $f(x^{\star}) = g(\alpha^{\star})$.
This enables us to construct the chain of inequalities which provides complementary slackness (taken from Boyd and Vandenberghe)

Since the first and last expressions are equal, all inequalities in the chain hold with equality. This enables us to find the minimum of the regularized problem with $\lambda = \alpha^{\star}$.

\[\begin{aligned} \min_{x} \{ f(x) + \alpha^{\star} (h(x) - \tau) \} & = f(x^{\star}) + \alpha^{\star} (h(x^{\star}) - \tau) \\ \min_{x} \{ f(x) + \alpha^{\star} h(x) \} & = f(x^{\star}) + \alpha^{\star} h(x^{\star}) \end{aligned}\]This shows that the minimum is attained at $x = x^{\star}$. Hence the minimizer of the constrained equation $x^{\star}$ is also a minimizer of the regularized problem with $\lambda = \alpha^{\star}$. If both problems have unique solutions, then we can see that the minimizers themselves are equal.

Note that the complementary slackness condition is

\[\alpha^{\star} (h(x^{\star}) - \tau) = 0\]and therefore either $h(x^{\star}) = \tau$ (the constraint is active) or $\alpha^{\star} = 0$ (both problems are equivalent to the unconstrained problem).