Algorithmic problems on convex sets
Many problems in mathematical programming can be formulated as problems on convex sets or convex bodies. Six kinds of problems are particularly important:[1]: Sec.2 optimization, violation, validity, separation, membership and emptiness. Each of these problems has a strong (exact) variant, and a weak (approximate) variant.
In all problem descriptions, K denotes a compact and convex set in Rn.
Strong variants
The strong variants of the problems are:[1]: 47
- Strong optimization problem (SOPT): given a vector c in Rn, find a vector y in K such that cTy ≥ cTx for all x in K, or assert that K is empty.
- Strong violation problem (SVIOL): given a vector c in Rn and a number t, decide whether cTx ≤ t for all x in K, or find y in K such that cTy > t.
- Strong validity problem (SVAL): given a vector c in Rn and a number t, decide whether cTx ≤ t for all x in K.
- Strong nonemptyness problem (SNEMPT): Decide whether K is empty, and if not, find a point in K.
- Strong separation problem (SSEP): given a vector y in Rn, decide whether y in K, and if not, find a hyperplane that separates y from K, that is, find a vector c in Rn such that cTy > cTx for all x in K.
- Strong membership problem (SMEM): given a vector y in Rn, decide whether y in K.
From the definitions, it is clear that algorithms for some of the problems can be used to solve other problems:
- An algorithm for SOPT can solve SVIOL, by checking whether cTy > t;
- An algorithm for SVIOL solves SVAL trivially.
- An algorithm for SVIOL can solve SNEMPT, by taking c=0 and t=-1.
- An algorithm for SSEP solves SMEM trivially.
Weak variants
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. This template was placed by Erel Segal (talk · contribs). If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Erel Segal (talk | contribs) 15 months ago. (Update timer) |
References
- ^ a b Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419