Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Thanks!

share|improve this question

closed as off-topic by Benjamin Steinberg, Carlo Beenakker, John Pardon, David White, Andres 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, Andres 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
add comment