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)

$\begin{aligned} f(x^{\star}) & = g(\alpha^{\star}) \\ & = \min_{x} \{ f(x) + \alpha^{\star} (h(x) - \tau) \} \\ & \le f(x^{\star}) + \underbrace{\underbrace{\alpha^{\star}}_{\ge 0} \underbrace{(h(x^{\star}) - \tau)}_{\le 0}}_{\le 0} \\ & \le f(x^{\star}) \end{aligned}$

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