Prove positive definiteness of the exact augmented Lagrangian function

Question

(not so important details) I have an optimization problem, where the objective is bilinear, and the constraint is a linear equality constraint. I want to show that minimizing the Exact Augmented Lagrangian function gives me the same result as of the original problem.

(important details) I need to show that the following matrix is positive definite for $\epsilon >0 , \eta >0$ (both sufficiently small):

$$\begin{bmatrix} 2\left(\dfrac{1}{\epsilon} + \eta\right) & 2\left(\dfrac{1}{\epsilon} + \eta\right) -1 & 1 - 4 \eta \\ 2\left(\dfrac{1}{\epsilon} + \eta\right) -1 & 2\left(\dfrac{1}{\epsilon} + \eta\right) & 1 - 4\eta \\ 1 - 4\eta & 1-4\eta & 8\eta \end{bmatrix}$$ I believe this matrix has a very special structure. Is it easy to see the positive definiteness? Or, do I really need to calculate the determinant of this 3-by-3 matrix?

Interesting edit: When we solve a problem like $\min \{f(x)= -x_1x_2 : \ g(x) = x_1+x_2 - 2=0 \}$ then the exact augmented Lagrangian function: $$ S(x,\lambda) = f(x) + \lambda^\top g(x) + \frac{1}{\epsilon}\|g(x)\|^2 + \eta \left\| \frac{\partial g(x)}{\partial x} \nabla_x L(x,\lambda)\right\|^2 $$ has first order condition results $x_1,x_2,\lambda = 1$, same with the original optimal solution. This FOC's do not depend on $\epsilon, \eta >0$. So, in such a simple problem there is no need to solve for any $\eta , \epsilon$. We can just fix some $\epsilon, \eta$ values such that the Hessian of $S(x,\lambda)$ is p.d., hence $S$ is convex, hence minimizing $S$ gives the same value as solving the original problem. In this case, fixing $\epsilon, \eta = 1$ is enough.

Answer 1

Call your matrix $A$. The determinant of its leading principal $2\times2$ submatrix $B$ is $4\left(\frac{1}{\epsilon}+\eta\right)-1$, while the Schur complement of $B$ in $A$ is given by $$ S=8\eta-(1-4\eta)^2e^TB^{-1}e =8\eta-\frac{2(1-4\eta)^2}{4(\frac{1}{\epsilon}+\eta)-1} =\frac{32\frac{\eta}{\epsilon}-2}{4(\frac{1}{\epsilon}+\eta)-1}. $$ Therefore $A$ is positive definite if and only if $4\left(\frac{1}{\epsilon}+\eta\right)>1$ and $16\eta>\epsilon$.

So, depending on the ratio $\frac{\eta}{\epsilon}$, $A$ may not be positive definite even when both $\eta$ and $\epsilon$ are small.

Answer 2

Letting $$\cases{a = 2\left(\dfrac{1}{\epsilon} + \eta\right) \\ b= 2\left(\dfrac{1}{\epsilon} + \eta\right) -1 \\c= 1 - 4 \eta\\d=8\eta}$$

It will have the form

$$\begin{bmatrix}a&b&c\\b&a&c\\c&c&d\end{bmatrix}$$

The only way to be non-full rank is if we can find a linear dependence of one column to the others. In other words, finding $\lambda_1,\lambda_2$ so that: $$\lambda_1 a+\lambda_2 b = c\\\lambda_1 b+\lambda_2 a = c\\\lambda_1 c+\lambda_2 c = d$$

So from subtracting the first two equations we get $(\lambda_1 - \lambda_2)a + (\lambda_2 - \lambda_1)b = 0$

if we factor the expression, we get: $(\lambda_2-\lambda_1)(b-a) = 0$

So either $\lambda_1 = \lambda_2$ or $b=a$ must hold.

Maybe you can finish from here?

Answer 3

Partial Answer.

According to Mathematica, the eigenvalues are $$1,\frac{-\sqrt{\varepsilon^2 (8 \eta (18 \eta -7)+9)-8 \varepsilon (4 \eta +1)+16}+\varepsilon (12 \eta -1)+4}{2 \varepsilon},\;\text{and}\;\frac{\sqrt{\varepsilon^2 (8 \eta (18 \eta -7)+9)-8 \varepsilon (4 \eta +1)+16}+\varepsilon (12 \eta -1)+4}{2 \varepsilon}.$$ As $\varepsilon(12\eta-1)$ can likely be taken as smaller in magnitude than $4,$ we can say the first and third eigenvalues are positive. (The $16$ inside the square roots clearly dominate everything else, so that we do not have complex eigenvalues, which we wouldn't expect, anyway, from a symmetric matrix.)

It's more difficult working with the second eigenvalue. It goes to zero as $\varepsilon$ and $\eta$ go to zero, but it's less clear how to prove that it's positive.

Answer 4

By the Gershgorin circle theorem, the eignevalues of this matrix fall within the union of the discs $$D\left(2(\varepsilon^{-1}+\eta),2(\varepsilon^{-1}-\eta)\right), \ D(8\eta,2-8\eta),$$ where $D(a,b)$ means the disc in the complex plane centered at $a$ with radius $b$. All that was assumed here is that $\varepsilon$ is small enough so that $\varepsilon^{-1}+\eta>1/2$ and that $\eta<1/4$, which also implies that $8\eta<2$. If neither of these discs touches the left half plane, we are done.

With $\varepsilon$ sufficiently small, the first disc is fine, since the radius is smaller than the absolute value of the center.

For the second disc, the leftmost point on the disc is $8\eta-(2-8\eta)=16\eta-2$, which is positive for $\eta>1/8$, so the matrix is spd in this case.

Not sure how to show for more general $\varepsilon$ and $\eta$.