0
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ This is smooth & convex, and actually unconstrained if you start at positive $q$ and are careful with step lengths. $\endgroup$ – Michael Grant Aug 2 '15 at 13:01
  • $\begingroup$ It can also be expressed as a semidefinite program but I can't explain that further from my phone ;-) $\endgroup$ – Michael Grant Aug 2 '15 at 13:02
  • $\begingroup$ Is it true that $Q\succeq0\Leftrightarrow q_j\geq0\forall j$ ? If so, I guess from my minimal optimization knowledge that it could be written as an SDP. Do you think there could be an analytical solution? If not, what solvers could perform such optimization? Thanks in advance for any help! $\endgroup$ – Dimpag Aug 2 '15 at 18:33
  • $\begingroup$ Yes, that's right. $\endgroup$ – Michael Grant Aug 2 '15 at 18:40
0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ How do we know that the Hessian $\nabla^2{f}$ is PSD? Just to make sure, the Newton iteration will be of the form $\vec{q}^{k+1}=\vec{q}^k+\lambda^k\vec{d}$, but how can the step $\lambda^k$ control the positiveness of all $q_i's$? Also, when you mention the inverse of $C^T Q C$ why would I need to compute it since I can just input it in the algorithm and it will evaluate the whole form? I suppose an analytical closed form solution is out of the question, right? Thanks again for all the help. $\endgroup$ – Dimpag Aug 3 '15 at 13:17
  • $\begingroup$ As you know, a convex function must have a positive semidefinite Hessian wherever it is differentiable. So if I already know the function is convex, then I already know that the Hessian (assuming I have derived it properly) will be PSD. In this case, I know it is convex because of its semidefinite representation. $\endgroup$ – Michael Grant Aug 3 '15 at 15:20
  • $\begingroup$ See my edit on how to implement a careful descend method. $\endgroup$ – Michael Grant Aug 3 '15 at 15:27
  • $\begingroup$ Don't we additionally need to guarantee that $f(q^k+\lambda^kd^k)<f(q^k)$ when performing line search, or we know it will converge? $\endgroup$ – Dimpag Aug 3 '15 at 16:14
  • $\begingroup$ Sure, a good Armijio-style criterion added to the backtracking line search is a good idea here. I'm not entirely sure it's necessary with a Newton search, but it may still be. $\endgroup$ – Michael Grant Aug 3 '15 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.