minimizing sum of reciprocal via socp

307 Views Asked by At

Given $x_1$, $x_2$,..., $x_n$, with $x_i>0 \forall i \in[1,n]$

I would like to minimize via SOCP the following cost function

$$J = ||\sum_{i=1}^n{\frac{\alpha_i}{x_i}}-K||$$, with $K>0$ and $\alpha_i$ given positive constants.

Any suggestion about how to formulate it? The problem should in general always have a solution, because for $x_i\rightarrow 0$ J can become very large, and for $x_i\rightarrow\infty$ the sum will tend to 0. It's just I don't see whether it can be properly cast in SOCP form...

Thanks in advance!

1

There are 1 best solutions below

8
On

Can't you just let $x_i = \alpha_i / K$ for each $i$? When you do so, $J = 0$, which is clearly a minimum. I know this doesn't use SOCP (partly because I have no idea what that is), but it does give a solution.

By the way, as $x_i \to \infty$, $J$ doesn't tend towards 0; it tends towards $Kn$.

Post-comment addition

It turns out that the thing to be minimized is $$ J = \| K - \sum_{i = 1}^n \frac{\alpha_i}{x_i} \|, $$ which wasn't clear (to me) from the initial formulation.

Even so, that too has got an easy solution: $$ x_i = \frac{\alpha_i n}{K} $$ for every $i$; then each term in the sum is $$ \frac{\alpha_i}{x_i} = \frac{\alpha_i}{\frac{\alpha_i n}{K}} = \frac{\alpha_i K}{{\alpha_i n}} = \frac{K}{n} $$ so that the sum is exactly $K$, and hence $J = 0$.

Further post-comment additions

An SOCP problem is (according to Wikipedia) one in the following form:

Minimize $$ {\displaystyle \ f^{T}x\ } $$ subject to $$ {\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}} \quad i=1,\dots ,m $$ and $$ {\displaystyle Fx=g\ } $$

OK. I'll formulate your problem that way.

Minimize

$$ 0^T x $$ subject to no norm conditions (i.e., $m = 0$ in this problem), and one linear condition, namely $$ Fx = g $$ where $F$ is the identity matrix, and $g_i = \frac{\alpha_i n}{K}. $$

That's an SOCP formulation of a problem completely equivalent to the one you posed. And it happens to be particularly easy to solve, because the solution's in the very last constraint.