  We investigate several problems in entanglement theory from the perspective
of convex optimization. This list of problems comprises (A) the decision
whether a state is multi-party entangled, (B) the minimization of expectation
values of entanglement witnesses with respect to pure product states, (C) the
closely related evaluation of the geometric measure of entanglement to quantify
pure multi-party entanglement, (D) the test whether states are multi-party
entangled on the basis of witnesses based on second moments and on the basis of
linear entropic criteria, and (E) the evaluation of instances of maximal output
purities of quantum channels. We show that these problems can be formulated as
certain optimization problems: as polynomially constrained problems employing
polynomials of degree three or less. We then apply very recently established
known methods from the theory of semi-definite relaxations to the formulated
optimization problems. By this construction we arrive at a hierarchy of
efficiently solvable approximations to the solution, approximating the exact
solution as closely as desired, in a way that is asymptotically complete. For
example, this results in a hierarchy of novel, efficiently decidable sufficient
criteria for multi-particle entanglement, such that every entangled state will
necessarily be detected in some step of the hierarchy. Finally, we present
numerical examples to demonstrate the practical accessibility of this approach.
