MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an optimization problem:

$\max_{\bf{x}} Z(\bf{x})$,

s.t. $\bf{x} \in conv(\bf{S})$

where $\bf{x}$ is an $n$-dimensional vector, $Z(\bf{x})$ is a non-linear function. The domain of $\bf{x}$ is defined by the convex hull of a set $\bf{S}$ of $m$ $n$-dimensional points. m is as large as about $2^n$.

I tried to convert the convex hull defined by the point set $\bf{S}$ into a set of linear inequalities, but it seems to be infeasible because of the dimension is not low (around 20 - 30 dimension), and the size of $\bf{S}$ is very large.

Does anyone know how to solve such an optimization program? I think maybe some approximation of $conv(\bf{S})$ would be helpful, but I don't know how to approximate it. I also thought about some branch method, but no idea on how to adopt it to this case.


share|cite|improve this question

closed as off-topic by Benjamin Steinberg, Carlo Beenakker, John Pardon, David White, Andrés E. Caicedo Jul 12 '13 at 5:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Benjamin Steinberg, Carlo Beenakker, John Pardon, David White, AndrĂ©s E. Caicedo
If this question can be reworded to fit the rules in the help center, please edit the question.

The method of attack for such a problem would depend strongly on the nature of $S$. Without further information you're essentially out of luck. – Noah Stein Jul 11 '13 at 21:22