2
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 16 '11 at 13:43
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 16 '11 at 13:58
  • $\begingroup$ 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. $\endgroup$ – Ashwinkumar B V Nov 16 '11 at 16:55
-3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ (1) For those who did not know the term “posynomial,” see Wikipedia 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). $\endgroup$ – Tsuyoshi Ito Nov 16 '11 at 18:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Nov 16 '11 at 19:21
  • 1
    $\begingroup$ @AshwinkumarBV basically once you do the log transform, the square root becomes exp(log x/2) which is then convex in log x $\endgroup$ – Suresh Venkat Nov 16 '11 at 22:04
  • 2
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 17 '11 at 13:56
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Nov 17 '11 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.