Let $d,n$ be positive integers, $(\mu_i)_{1\leq i \leq n}$ and $(\eta_i)_{1\leq i \leq n}$ some scalars, and define
$$ A := \displaystyle \sum_{i=1}^{n} \mu_i y_i y_i^T, \qquad c := \displaystyle \sum_{i=1}^{n} \eta_i y_i $$
for some vectors $y_i \in \mathbb{R}^d$. Finally, let $\varepsilon>0$. I wish to solve the following optimization problem : \begin{aligned} &\displaystyle \min_{x \in \mathbb{R}^d} \frac{1}{2}x^TAx \\ &\text{such that} \text{ } x^Tc=\varepsilon \end{aligned}
I have defined the corresponding Lagrangian
$$L\left(x,\lambda\right)=\frac{1}{2}x^TAx-\lambda(x^Tc-\varepsilon)$$
The condition $\nabla_x L\left(x,\lambda\right) = 0$ yields $Ax=\lambda c$. When $A$ is invertible, $x$ can be expressed as $x=\lambda A^{-1}c$ and the optimization problem can then be straightforwardly solved : the constraint along with $Ax=\lambda c$ implies $x^TAx=\lambda\varepsilon$. We can then identify $\lambda$ by plugging $x=\lambda A^{-1}c$ in the previous equation and find the value of $\frac{1}{2}x^TAx$ (I get that the minimum equals $\frac{\varepsilon^2}{2c^TA^{-1}c}$).
What happens when $A$ is not invertible? Can the quadratic program still be solved explicitly in a similar way? If not, can we at least find an approximate solution?
EDIT : I may have part of an answer but I am not sure it is entirely correct.
- If $c \in \operatorname{Col}(A) $ where $\operatorname{Col}(A)$ is the vector space spanned by the columns of $A$, then $x=\lambda A^+c$ where $A^+$ is the moore-penrose pseudoinverse of $A$ is a solution of $Ax=\lambda c$. In fact, for $x^*=\lambda^* A^+c$ with $\lambda^*=\frac{\varepsilon}{c^TA^{+}c}$ (assuming that the denominator is non zero...), we have $\nabla_x L\left(x^*,\lambda^*\right) = 0$ and ${x^*}^Tc=\varepsilon$. Isn't this enough to ensure that this $x^*$ is an optimal solution of my problem in this case ?
- if $c \notin \operatorname{Col}(A)$, $Ax=\lambda c$ yields $\lambda=0$ which implies that $x^TAx=0$. Does that mean that the minimum is $0$ in this case ?