Given a symmetric positive semidefinite matrix $A \in \mathbb{R}^{n \times n}$, I would like to solve the following maximization problem:
$$\begin{array}{ll} \underset{t \in \mathbb{R}, \,\, x \in \mathbb{R}^n}{\text{maximize}} & t\\ \text{subject to} & x^T A x \leq{} 1\\ & x_i \geq t, \quad \forall i \in \{1,2\dots,n\}\end{array}$$
I've find a solution to solve its dual problem:
$$\begin{array}{ll} \underset{y \in \mathbb{R}^n}{\text{minimize}} & y^T A^{-1} y\\ \text{subject to} & 1^T y = 1\\ & y_i \geq 0, \quad \forall i \in \{1,2\dots,n\}\end{array}$$
However, to solve this problem, I need to calculate the matrix inverse of $A$, which requires large complexity. I wonder if there is a low complexity methods to solve the original convex optimization problem without doing full matrix size inverse?
Dual problem derivation:
- Derive the Lagrangian: $$L(x,t,c,y) = -t + c(x^T A x-1) + \sum_i\{y_i(t-x_i)\}$$ where $c$ and $y$ are dual variables.
- Formulate the KKT conditions: $\frac{\partial{L}}{\partial{t}} = 1^Ty-1=0,\ \frac{\partial{L}}{\partial{x}} = c(A+A^T)x-y=2cAx-y=0\\ c(x^TAx-1)=0,\ y_i(t-x_i) = 0\ \forall i \in \{1,2\dots,n\},\\ c\geq{0},\ y_i\geq{0}$
- By the second equality in 2., we get $x=\frac{1}{2c}A^{-1}y$.
- It is obviously that $c$ is not zero; otherwise, the first two equality will be violated. Therefore, by the third equality $x^TAx=1$.
- Substitute $x$ in 3. into 4., we can finally get $c=\sqrt{\frac{x^TA^{-1}x}{4}}$.
- It can be easily verify that the Slater's condition is satisfied, which means the dual gap is zero.
- The dual problem is $$\max_{c,y}\{\min_{x,t}\{L(\cdot)\}\} = \cdots = \max \left\{ -\sqrt{y^TA^{-1}y} \right\}$$
- By 2. & 7. we can get the dual problem fomulation.