4
$\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$ Apr 5, 2014 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, 2015 at 8:36

1 Answer 1

3
$\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$ Oct 2, 2014 at 17:01
  • $\begingroup$ EDIT: Just saw this was an old question. Didn't mean to bring it up from the dead $\endgroup$ Oct 2, 2014 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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