Let's define a minimization problem:
$f_0(x) \to \min\limits_{x \in \mathbb{R}^{n} }\\ \text{s.t. } Ax = b,$
$f_0(x): \mathbb{R}^n \to\mathbb{R}$ is convex and differentiable, and $\alpha \in \mathbb{R}^{m \times n},\; rank(A)=m$.
In a quadratic penalty method, we form an auxiliary function $\phi(x) = f_0(x) + \alpha \|Ax - b\|_2^2,\;\;\alpha>0$ - parameter.
This auxiliary function consists of the objective plus the penalty term $\alpha \|Ax - b\|_2^2.$ The idea is that a minimizer of the auxiliary function, $\tilde{x}$, should be an approximate solution of the original problem. Intuition suggests that the larger the penalty weight $\alpha$, the better the approximation $\tilde{x}$ to a solution of the original problem.
Suppose $\tilde{x}$ is a minimizer of $\phi(x).$ How can we show how to find from $\tilde{x}$ a dual feasible point for the original problem? And find the corresponding lower bound on the optimal value of the original problem? I understand how it works for specific functions, but don't understand how to show for general situation.
Thanks in advance for your reply!
Since $\tilde{x}$ minimizes $\phi$ we have: $$ \nabla f_0(\tilde{x}) + 2 \alpha A^T(A\tilde{x} -b) = 0$$
And $\tilde{x}$ is also a minimizer of $x \mapsto f_0(x) + \nu^T (Ax-b)$ with $\nu = 2\alpha(A\tilde{x} -b)$, hence $\nu$ is dual feasible with the dual function $g(\nu) = \inf_x f_0(x) + \nu^T(Ax-b) = f_0(\tilde{x}) + 2\alpha(A\tilde{x} - b)^T (A\tilde{x} -b) = f_0(\tilde{x}) + 2\alpha\lVert A\tilde{x}-b \rVert_2^2$. In addition you have $f_0(\tilde{x}) + 2\alpha\lVert A\tilde{x}-b \rVert_2^2 \leq f_0(x^*)$ by weak duality.