<p>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. </p>

<p>See the tutorial at <a href="http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf" rel="nofollow">http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf</a> which discusses geometric programming and search for posynomial. </p>

<p>--clarification-- </p>

<p>See page 73 of the above link.</p>

<p>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.</p>

<pre><code>    Given:
      Minimize f0(x)
      s.t.
      fi(x)&lt;=0 for all i
      fj(x)=0 for all j
</code></pre>

<p>Where f0(x) is your original objective and fi(x) is your polytope. </p>

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

<pre><code>      Minimize log(f0(exp(y))
      s.t.
      log(fi(exp(y))&lt;=0 for all i
      log(fj(exp(y))=0 for all j
</code></pre>

<p>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. </p>

<p>--- additional comments ----</p>

<p>The only other approach which might be faster than solving the primal problem is to use KKT conditions to as implied by Ashwinkumar. You can try solving the dual formed from the KKT conditions. Depending on the structure of the polytope, you might be able to find the answer faster.</p>

<p>See <a href="http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions" rel="nofollow">http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions</a>. </p>

CC BY-SA 3.0
2011-11-16T18:18:50.010Z
(1) For those who did not know the term “posynomial,” see [Wikipedia](http://en.wikipedia.org/wiki/Posynomial) or the linked article.  (2) In general, the problem in the question is not a convex optimization even if x_i > 0 for all i.  To recast the problem in the question as a convex optimization as stated in the linked article, all the constraints have to be in the form (posynomial function in x1,…,xk) ≤ (constant).
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-16T18:30:51.160Z
By the way, I think that this answer contains some interesting pieces of information.  I am happy to remove the down-vote if you edit the answer to make it accurate.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-16T18:46:31.150Z
I thought you can use convex optimization for minimizing a convex function or maximizing a convex function. I believe it is not convex optimization not because of the constraint(since a polytope is a convex set) but because of the objective function. (from http://en.wikipedia.org/wiki/Convex_optimization)
Ashwinkumar B V
CC BY-SA 3.0
2011-11-16T19:21:19.763Z
@Ashwinkumar: As I understand it from the linked article, the problem can be transformed into a convex program if all the constraints are in the form “(posynomial function in x1,…,xk) ≤ (constant)” by taking logarithm.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-16T22:04:19.197Z
@AshwinkumarBV basically once you do the log transform, the square root becomes exp(log x/2) which is then convex in log x
Suresh Venkat
CC BY-SA 3.0
2011-11-17T13:56:52.380Z
Your “additional comments” are still incorrect.  The 1/2-norm is not convex.  Please read Ashwinkumar’s comment and my second comment on the question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-17T16:31:45.960Z
"all norms are convex" is false.
Suresh Venkat
CC BY-SA 3.0
2011-11-17T17:43:34.170Z
Tsuyoshi, thanks for the feedback. It helped improve my response appreciably.
user1048258
CC BY-SA 3.0
2011-11-17T18:46:25.573Z
@Suresh: All norms are convex functions, but the so-called 1/2-“norm” is not subadditive and therefore not a norm.  I should have used the scare quotes also in my previous comment.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-18T04:41:40.017Z
arggh yes. of course.
Suresh Venkat
CC BY-SA 3.0
2011-11-16T17:18:48.837Z
2011-11-17T17:40:26.343Z
2011-11-17T17:40:26.343Z
user1048258
<p>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.</p>

<p>Jian.</p>

CC BY-SA 3.0
2011-11-16T13:43:34.517Z
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](http://maven.smith.edu/~orourke/TOPP/P33.html)).  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
CC BY-SA 3.0
2011-11-16T13:58:56.187Z
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
CC BY-SA 3.0
2011-11-16T16:55:34.137Z
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
<ds.algorithms><linear-programming>
Is there a way to solve or approximate the concave program with separable objective?
jian
# Is there a way to solve or approximate the concave program with separable objective?

(Asked by: username_0 on 2011-11-16)

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.

**Tags:** ds.algorithms, linear-programming
> **Comments:**
> **username_1**: 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](http://maven.smith.edu/~orourke/TOPP/P33.html)).  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.  
> **username_1**: 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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-11-16. Score: -3

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

Where f0(x) is your original objective and fi(x) is your polytope. 
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. 
--- additional comments ----
The only other approach which might be faster than solving the primal problem is to use KKT conditions to as implied by Ashwinkumar. You can try solving the dual formed from the KKT conditions. Depending on the structure of the polytope, you might be able to find the answer faster.
See http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions.

> **Comments:**
> **username_1**: (1) For those who did not know the term “posynomial,” see [Wikipedia](http://en.wikipedia.org/wiki/Posynomial) or the linked article.  (2) In general, the problem in the question is not a convex optimization even if x_i > 0 for all i.  To recast the problem in the question as a convex optimization as stated in the linked article, all the constraints have to be in the form (posynomial function in x1,…,xk) ≤ (constant).  
> **username_1**: By the way, I think that this answer contains some interesting pieces of information.  I am happy to remove the down-vote if you edit the answer to make it accurate.  
> **username_2**: I thought you can use convex optimization for minimizing a convex function or maximizing a convex function. I believe it is not convex optimization not because of the constraint(since a polytope is a convex set) but because of the objective function. (from http://en.wikipedia.org/wiki/Convex_optimization)  
> **username_1**: @Ashwinkumar: As I understand it from the linked article, the problem can be transformed into a convex program if all the constraints are in the form “(posynomial function in x1,…,xk) ≤ (constant)” by taking logarithm.  
> **username_4**: @AshwinkumarBV basically once you do the log transform, the square root becomes exp(log x/2) which is then convex in log x  
> **username_1**: Your “additional comments” are still incorrect.  The 1/2-norm is not convex.  Please read Ashwinkumar’s comment and my second comment on the question.  
> **username_4**: "all norms are convex" is false.  
> **username_3**: Tsuyoshi, thanks for the feedback. It helped improve my response appreciably.  
> **username_1**: @Suresh: All norms are convex functions, but the so-called 1/2-“norm” is not subadditive and therefore not a norm.  I should have used the scare quotes also in my previous comment.  
> **username_4**: arggh yes. of course.  

---

