0
$\begingroup$

Let $G \in \mathbb{R}^{n \times n}$, $H \in \mathbb{R}^{p \times n}$ and $x_i \in \mathbb{R}$ for all $i \in [1...m]$ be decision variables. Let $A\in \mathbb{R}^{p \times p}$ be a known invertible matrix. Consider the problem $$\min_{G\succeq 0,~x_i\geq 0, \forall i \in [1...m]} \sum_{i=1}^m \frac{1}{x_i}$$ $$\begin{bmatrix}G& H^T\\ H&A\left(\sum_{i=1}^{m}\frac{1}{x_i}\right)^{-1}\end{bmatrix}\succeq 0.$$

Can this be equivalently reformulated as a SDP?

A first step can be to add the SOCP constraint $$|| \begin{bmatrix}x_i-z_i&2\end{bmatrix}||_2\leq x_i+z_i\,,$$ so that $z_i \geq \frac{1}{x_i}$ and the problem becomes

$$\min_{G\succeq 0,~x_i\geq 0,~z_i,~\forall i \in [1...m]} \sum_{i=1}^m z_i$$ $$\begin{bmatrix}G& H^T\\ H&A\left(\sum_{i=1}^{m}z_i\right)^{-1}\end{bmatrix}\succeq 0.$$ $$|| \begin{bmatrix}x_i-z_i&2\end{bmatrix}||_2\leq x_i+z_i\,, \forall i \in [1...m]\,.$$

Is it possible to remove the nonlinearity in $z_i$ in the positive-semidefinite matrix?

$\endgroup$
  • $\begingroup$ You should be minimizing $z_i$, they are upper bounds on the terms you want to minimize $\endgroup$ – Johan Löfberg Apr 12 '18 at 10:42
  • $\begingroup$ Correct, sorry I mistyped. $\endgroup$ – pinochino Apr 12 '18 at 10:50
  • $\begingroup$ Are both $G$ and $H$ functions of $x$? $\endgroup$ – Johan Löfberg Apr 12 '18 at 10:52
  • $\begingroup$ Yes, G is coupled with $x_i$ through other constraints. H and G are also coupled through other constraints. By "coupled" I mean there are other constraints which involve G and x together, and G and H together. These constraints I didn't write are standard SDP constraints. $\endgroup$ – pinochino Apr 12 '18 at 10:54
  • $\begingroup$ Depending on what you want to achieve it may or may not be helpful to directly write $z\leq (\sum_i\frac{1}{x_i})^{-1}$ using SOCP (at least when $x_i>0$) themosekblog.blogspot.dk/2018/03/… $\endgroup$ – Michal Adamaszek Apr 12 '18 at 11:27
2
$\begingroup$

Let $f(x)$ denote the harmonic mean. The objective is a scaled inverse of the harmonic mean, hence you are effectively maximizing the harmonic mean (which is concave and SOCP representable). Similarily, the term in the constraint is also the harmonic mean divided by $m$. An equivalent hypograph model is

$$\max t$$ $$\begin{bmatrix}G& H^T\\ H&A\frac{t}{m}\end{bmatrix}\succeq 0, f(x) \geq t$$

$\endgroup$
  • $\begingroup$ Thank you. the harmonic mean can be represented as $$t^2\leq 2x_i y_i~\forall i,~~2\sum_{i=1}^m y_i==t$$. I can express $t^2\leq 2x_i y_i$ as $[t~x_i~y_i]M[t~x_i~y_i]'\leq 0$ where $M=\begin{bmatrix}1&0&0\\0&0&-1\\0&-1&0\end{bmatrix}$, which is not positive semi-definite. How can I express it with a positive definite matrix? $\endgroup$ – pinochino Apr 12 '18 at 13:57
  • $\begingroup$ @pinochino see this paper. Johan, it's called 'SOCO' now ;) $\endgroup$ – LinAlg Apr 12 '18 at 14:23
  • $\begingroup$ Ok, thanks a lot. Would $||[2t~~x_i-y_i]||_2\leq x+y$ be correct? $\endgroup$ – pinochino Apr 12 '18 at 14:34
  • $\begingroup$ Correction: $||[\sqrt{2}t~~x_i−y_i]||_2≤x_i+y_i$ $\endgroup$ – pinochino Apr 12 '18 at 15:00
  • $\begingroup$ @LinAlg it will always be SOCP to me... old dog, new tricks, etc $\endgroup$ – Michael Grant Apr 12 '18 at 17:54

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.