Backgrounds
I would like to specify the conditions the Lagrange multiplier uniquely identifies the global minimum. (Actually, the main motivation is the derivation of Ridge estimator in Statistics).
It may be a very elementary problem in convex optimization, but I feel I do not have reached sufficient understanding.
Question
Say we would like to find the parameter $\beta^\dagger \in \mathbb{R}^p$ that globally minimize the constrained loss function $L1(\beta)$ and not constrained loss function $L2(\beta)$.
Show that the following two have the same, unique solution.
$\mathrm{argmin}_\beta L_1 (\beta) = \mathrm{argmin}_\beta \left( \beta^T A \beta – 2b^T \beta \right)$ subject to $\beta^T \beta < R$.
$\mathrm{argmin}_\beta L_2 (\beta) = \mathrm{argmin}_\beta \left( \beta^T A \beta – 2 b^T \beta + \lambda \beta^T \beta\right)$
where $A_{p \times p}$ : symmetric positive definite, $b \in \mathbb{R}^p$ and $\lambda >0, R>0$.
Try
Step1. The uniqueness of $\mathrm{argmin}_\beta L_2 (\beta)$.
In
$$L_2(\beta) = \beta^T (A + \lambda I ) \beta – 2 b^T \beta$$
we have $A + \lambda I$ : symmetric positive definite, since $\lambda I $ is symmetric positive definite. Thus we have $\beta^T (A + \lambda I ) \beta$ is strictly convex, and thus $L_2 (\beta) $ : strictly convex function of $\beta$.
From strict convexity and the fact that $\frac{\partial L_2}{\partial \beta} = 2(A + \lambda I)\beta – 2b=0$ has the unique solution $\beta = (A + \lambda I)^{-1} b$, thus we have $\mathrm{argmin}_\beta L_2 (\beta) = (A + \lambda I)^{-1} b$ is the global minimizer of $L_2$
Step2. The equivalence of 1 and 2.
As far as I know, the Lagrange multiplier method is a strategy for finding the local maxima and minima of a function subject to equality constraints.
Problems
But I have following two problems
- the problem has inequality constraints, so I'm not sure the method is applicable
- I have noticed the quadratic function $L_1(\beta) = \left( \beta^T A \beta – 2b^T \beta \right)$ also has the global minimum, since $A$ is symmetric positive definite. But I'm not sure how I should relate this to $\mathrm{argmin}_\beta \left( \beta^T A \beta – 2b^T \beta \right)$ subject to $\beta^T \beta < \lambda$ has the unique and same solution as $2$.
Any help will be appreciated.
Edited 1
Following the comment and the answer I came to understand that generally $R \neq \lambda$. (Actually there was $\lambda$ in place of $R$ above)
Now I edited $L_1(\beta)$, I would like to ask, that the 1 and 2 has the same and unique solution.
Edited 2
The whole above discussion may be misleading, due to my poor setting of the problem.
Thanks to the answer by @AngryAvian, the above statement should be "for a given value of $R$, there exists a value of $\lambda$ that makes the solutions of $L1$ and and $L2$ the same", and vice versa.
Best Answer
I don't believe your claim is true, only because the same $\lambda$ appears in both problems.
Here is a counterexample in $p=1$. Take $A=1$ and $b=1$ and $\lambda=2$. The minimum of $\beta^2 - 2 \beta$ subject to $\beta^2 < 2$ is attained at $\beta=1$. The minimum of $\beta^2 - 2 \beta + 2 \beta^2$ is attained at $\beta=1/3$.
Edit: A.Γ.'s counterexample is much better explanation and contains my above counterexample as a special case. The global minimizer of $\beta^\top A \beta - 2 b^\top \beta$ is $\beta_* := A^{-1} b$. As long as $\lambda > \beta_*^\top \beta_*$, the solution to $L_1$ is $\beta_* = A^{-1} b$. On the other hand, the solution to $L_2$ is $(A+\lambda I)^{-1} b$ which depends on $\lambda$, never mind being equal to $A^{-1} b$.
If you rewrite the constraint in $L_1$ as $\beta^\top \beta < R$, then there is some corresponding $\lambda$ such that $L_2$ gives the same solution, but it usually (actually almost never) is not the same as $R$. More generally, the Lagrange multiplier that arises when dealing with a constrained problem does not usually equal the constraint (or depend so explicitly on it).