Minimize sum of reciprocals under multiple linear constraints

convex optimizationoptimizationsecond-order-cone-programming

Given $A\in(\mathbb{R}_{>0})^{n\times m}$, $b\in(\mathbb{R}_{>0})^{m} $ and $c\in(\mathbb{R}_{>0})^{n}$,

$$ \begin{array}{ll} \underset{x \in (\Bbb R_{>0})^n}{\text{minimize}} & f(x) := \sum\limits_{i=1}^n \dfrac{c_i}{x_i} \\ \text{subject to} & Ax \leq b\end{array} $$

where $\leq$ denotes component-wise inequality.

I am stuck with this optimization problem in my projects. Currently, I am trying to solve the problem with numerical methods (e.g., fmincon on Matlab). I want to know whether an analytical solution exists or how to relax this problem to be convex.

Best Answer

The problem is convex, as demonstrated by the following second-order cone formulation, obtained by introducing $y_i$ to represent $1/x_i$: \begin{align} &\text{minimize} &\sum_i c_i y_i \\ &\text{subject to} & A x &\le b \\ && z &= \sqrt 2 \\ && 2 x_i y_i &\ge z^2 &&\text{for all $i$} \tag1\label1\\ && x_i &\ge 0 &&\text{for all $i$}\\ && y_i &\ge 0 &&\text{for all $i$} \end{align} Constraint \eqref{1} is a rotated second-order cone constraint. Everything else is linear.

Related Question