Find the minimum of a function for only positive values of the vector variable

Question

Let variable vector $\vec{q}$ of size $m\times1$, and its diagonal counterpart $m\times m$ matrix $Q=diag(\vec{q})$, for some $m\in\mathbb{N}$. Define fixed parameter $n\times1$ vectors $\vec{p}, \vec{K}, \vec{L}, \vec{M}, \vec{N}$, the fixed parameter $m\times n$ matrix $C$, and fixed scalar $R\in\mathbb{R}$, where $n\in\mathbb{N}$ and all entries of the vectors and matrices are real numbers. Let the scalar function be defined as \begin{equation} f(Q)=\vec{p}^T(C^TQC)^{-1}\vec{p}+\vec{K}^TC^TQC\vec{L}+\vec{M}^TC^TQC\vec{N}-R \end{equation}
The desired optimization is then \begin{equation} \begin{array}{rrclcl} \displaystyle \min_{\vec{q}} & {f(Q)} \\ \textrm{s.t.} & q_j & \geq & 0 & \forall & j\in\{1,2,...,m\} \\ \end{array} \end{equation}

Answer 1

I'd say the easiest way to solve this is with a descent method. The partial derivatives are \begin{aligned} \frac{\partial f}{\partial q_i} &= -p^T(C^TQC)^{-1}C^Te_ie_i^TC(C^TQC)^{-1}p+K^TC^Te_ie_i^TCL+MC^Te_ie_i^TCN \\ &= -(e_i^TC(C^TQC)^{-1}p)^2+(e_i^TCK)(e_i^TCL)+(e_i^TCM)(e_i^TCN) \end{aligned} \begin{aligned} \frac{\partial^2 f}{\partial q_i\partial q_j} &= -2(e_i^TC(C^TQC)^{-1}p)\cdot - (e_i^TC(C^TQC)^{-1}C^Te_je_j^TC(C^TQC)^{-1}p) \\ &= 2(e_i^TC(C^TQC)^{-1}p)(e_j^TC(C^TQC)^{-1}p)(e_i^TC(C^TQC)^{-1}e_j) \end{aligned} So if you're willing to compute the full inverse of $C^TQC$, you can build a Newton's method out of this. Just make sure to do a backtracking line search so that $q$ remains positive, and you should be good.

You can also express this as a semidefinite program: \begin{array}{ll} \text{minimize}_{r,Q} & r + K^TC^TQCL+M^TC^TQCN \\ \text{subject to} & \begin{bmatrix} r & p^T \\ p & C^TQC \end{bmatrix} \succeq 0 \\ & Q \succeq 0, ~ Q \text{ diagonal} \end{array} This works because the $(n+1)\times(n+1)$ LMI is positive definite if and only if $C^TQC\succeq 0$ and $r-p^T(C^TQC)^{-1}p\geq 0$.

EDIT: I realized there may be an important subtlety: it could be possible, depending on $C$, that $C^TQC\succ 0$ even if some of the values of $q$ are negative zero. In other words, while the smoothness of $f(Q)$ ensures that $C^TQC\succ 0$ at the solution, it doesn't necessarily ensure that $q\succeq 0$.

So if you're going to implement a smooth method, and I recommend it still, you will need to do a sort of projected gradient or projected Newton method, which iterates as follows:

1. Compute the step $d$ from the gradient, Newton step, whatever.
2. Do backtracking line search: start with $\lambda=1$, and try $q^{k+1}=q^{k}+\lambda d$. If $C^TQC\succ 0$, keep that value of $\lambda$. Otherwise, set $\lambda\leftarrow\lambda/2$ and try again.
3. If any of the values of $q^{k+1}$ are negative, set them to zero.