3
$\begingroup$

everyone! I have this optimization problem with constraint. $D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter. $x$ and $v$ are two known p-dimensional vectors. The objective function is $D=\mathrm{argmin}\, x^T(D+T)^{-1}x$. Assuming each row vector of $D$ is $D_i=(D_{i1},\ldots,D_{ip})$, the constraints are $|D_{i1}|+|D_{i2}|+...+|D_{ip}|<=|v_i|$. I think the constraint can be written as linear inequality by letting $\beta=\beta_+-\beta_-$ and $|\beta|=\beta_++\beta_-$. The problem is the objective function includes the inverse of $D+T$. It keeps bugging me for a long time. Is there any available algorithm for this kind of problem? Or is this kind of problem unsolvable? I do appreciate your suggestion!

$\endgroup$
2
  • $\begingroup$ I think you meant beta=(beta+)-(beta-) and |beta|=(beta+)+(beta-). $\endgroup$ – Cristóbal Guzmán Apr 5 '14 at 11:13
  • $\begingroup$ Have you tried to formulate the optimality system, e.g. by using this: en.wikipedia.org/wiki/… $\endgroup$ – Dirk Feb 2 '15 at 8:36
2
$\begingroup$

Let $B = xx^T$, and $Y=(D+T)$, then $x^TY^{-1}x=\mbox{Tr}[Y^{-1}B]=\mbox{Tr}[\sqrt{B}^T Y^{-1} \sqrt{B}]$, where $B=\sqrt{B}\sqrt{B}^T$ is the Cholesky factorization. Note that $$\min \mbox{Tr}[\sqrt{B}^T Y^{-1} \sqrt{B}] = \min \{\mbox{Tr}(F):\, F\succeq \sqrt{B} Y^{-1} \sqrt{B} \}. $$ Finally, the latter optimization problem is semidefinite representable. By the Lemma on Schur complements, we can re-write this problem as $$ \min \{\mbox{Tr}(F):\, \left[ \begin{array}{cc} (D+T) & \sqrt{B}\\ \sqrt{B}^T & F \end{array}\right] \succeq 0 \}. $$ Your bound constraints can be easily added to the formulation above.

I hope it helps

$\endgroup$
2
  • 1
    $\begingroup$ Why are you introducing $B$ and $F$? Introduce a scalar $t$ and simply minimize $t$ subject to $\begin{bmatrix}D+T & x^T\\x & tI\end{bmatrix}$. $\endgroup$ – Johan Löfberg Oct 2 '14 at 17:01
  • $\begingroup$ EDIT: Just saw this was an old question. Didn't mean to bring it up from the dead $\endgroup$ – Johan Löfberg Oct 2 '14 at 17:09

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.