(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.
Best Answer
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.