Maximize $\sum_{i=1}^n 1/x_i$ subject to an SDP constraint

Question

I would like to solve the following problem: \begin{align}\max_{x_1, \ldots, x_n}&\quad\frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n}\\\text{s.t.}&\quad\sum_{i=1}^n x_i A_i \succeq A_0\\&\quad x_1, \ldots, x_n \geq 0\end{align}

Here $A_0, A_1, \ldots, A_n$ is a collection of symmetric matrices.

I'm not sure what is a good way to solve this, since the objective is the maximization (rather than minimization) of a convex function. Can this be done in polynomial time, and, if not, what are some good heuristics for this?

Answer 1

This is a concave programming problem, i.e., concave objective with convex constraints. It is a nonlinear, non-convex SDP. However, the constraints are not compact, so the theorem which says that there is a global optimum of a concave programming problem at an extreme of the constraints, does not apply. You can forget about polynomial time.

If you want to try to solve this to global optimality, my suggestion is to specify BMIBNB as solver using YALMIP under MATLAB. Since the latter part of last year, BMIBNB has the capability of solving non-convex SDPs to global optimality, and is the only publicly available solver which can do so as far as I know. Whether it succeeds may depend on the uppersolver and lowersolver you specify for BMIBNB to call, as well as the difficulty of the problem. If you need help, you can post at https://groups.google.com/g/yalmip.