# Is there a way to solve or approximate the concave program with separable objective?

I would like to solve the following problem: "minimize $\sum_{i=1}^k \sqrt{x_i}$ subject to some polytope constaints." Is there a polynomial time algorithm to solve or approximate it? Thanks.

Jian.

• Note that we do not know a polynomial-time algorithm for even the following simple variation of the problem: decide whether $\sum_{i=1}^k \sqrt{x_i}$ is greater than a given integer or not (cf. the sum-of-square-roots problem). This means that in one of the natural formulations of your problem, a polynomial-time algorithm to exactly solve it is beyond the current knowledge. – Tsuyoshi Ito Nov 16 '11 at 13:43
• The exact version is NP-hard. One way to prove this is by reducing the feasibility version of 0-1 integer programming to the current problem. – Tsuyoshi Ito Nov 16 '11 at 13:58
• Something property of the minimum - The minimum always occurs at the boundary of polytope. This ofcourse does not give a polytime algorithm but is a heuristic that cuts the search space. – Ashwinkumar B V Nov 16 '11 at 16:55

I special cases of this problem are a convex optimization problem. If x_i>0, then the objective is a posynomial. If the polytope can be described using posynomials, then the problem becomes a convex optimization problem.

See the tutorial at http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf which discusses geometric programming and search for posynomial.

--clarification--

See page 73 of the above link.

If your polytope can be described by a posynomial, then you can solve the polytope as a convex programming problem, by converting the problem into an equivalent form.

Given:
Minimize f0(x)
s.t.
fi(x)<=0 for all i
fj(x)=0 for all j

Let x_k an element in x be equal to exp(y_k). Now, an equivalent problem is cast as:

Minimize log(f0(exp(y))
s.t.
log(fi(exp(y))<=0 for all i
log(fj(exp(y))=0 for all j

The restriction here is that the only a subset of all polytopes will work in this formulation. However if you can find a reasonable approximation where the polytope is approximated by a set of posynomial constraints, then you will have a computationally fast solution.