# Reformulation of nonlinear optimization problem as a semidefinite program (SDP)

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?

• You should be minimizing $z_i$, they are upper bounds on the terms you want to minimize Apr 12, 2018 at 10:42
• Correct, sorry I mistyped. Apr 12, 2018 at 10:50
• Are both $G$ and $H$ functions of $x$? Apr 12, 2018 at 10:52
• 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. Apr 12, 2018 at 10:54
• 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/… Apr 12, 2018 at 11:27

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$$
• 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? Apr 12, 2018 at 13:57
• Ok, thanks a lot. Would $||[2t~~x_i-y_i]||_2\leq x+y$ be correct? Apr 12, 2018 at 14:34
• Correction: $||[\sqrt{2}t~~x_i−y_i]||_2≤x_i+y_i$ Apr 12, 2018 at 15:00