Previous |  Up |  Next


convex polyhedra; parameters; separating hyperplane; supporting hyperplane; solution set; stability set
We investigate diverse separation properties of two convex polyhedral sets for the case when there are parameters in one row of the constraint matrix. In particular, we deal with the existence, description and stability properties of the separating hyperplanes of such convex polyhedral sets. We present several examples carried out on PC. We are also interested in supporting separation (separating hyperplanes support both the convex polyhedral sets at given faces) and permanent separation (a hyperplane separates the convex polyhedral sets for all feasible parameters). Finally, we show how the developed theory is applicable in multiobjective linear programming.
[1] Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods. Cambridge University Press Cambridge (2001). MR 0202544 | Zbl 0994.68074
[2] Gal, T.: Postoptimal Analyses, Parametric Programming, and Related Topics. McGraw-Hill New York (1979). MR 0536349 | Zbl 0407.90052
[3] Gal, T., Greenberg, H. J., eds.: Advances in Sensitivity Analysis and Parametric Programming. Kluwer Academic Publishers Dordrecht (1997). MR 1482234 | Zbl 0881.00025
[4] Grünbaum, B.: Convex Polytopes, 2nd edition. Springer New York (2003). MR 1976856
[5] Grygarová, L.: A calculation of all separating hyperplanes of two convex polytopes. Optimization 41 (1997), 57-69. DOI 10.1080/02331939708844325 | MR 1460220
[6] Grygarová, L.: On a calculation of an arbitrary separating hyperplane of convex polyhedral sets. Optimization 43 (1998), 93-112. DOI 10.1080/02331939808844377 | MR 1638843
[7] Grygarová, L.: Separating support hyperplanes for a pair of convex polyhedral sets. Optimization 43 (1998), 113-143. DOI 10.1080/02331939808844378 | MR 1638847
[8] Grygarová, L.: On a supporting hyperplane for two convex polyhedral sets. Optimization 43 (1998), 235-255. DOI 10.1080/02331939808844386 | MR 1774340
[9] Grygarová, L.: Die Lösbarkeit eines linearen Optimierungsproblems unter Zufügung einer weiteren Restriktionsbedingung. Apl. Mat. 17 (1972), 352-387 German. MR 0342170
[10] Hladík, M.: Explicit description of all separating hyperplanes of two convex polyhedral sets with RHS-parameters. Proceedings of WDS'04, Part I J. Šafránková Matfyzpress Prague (2004), 63-70.
[11] Hladík, M.: Separation of convex polyhedral sets with column parameters. Kybernetika 44 (2008), 113-130. MR 2405059
[12] Intriligator, M. D.: Mathematical Optimization and Economic Theory. SIAM Philadelphia (2002). MR 1929542 | Zbl 1140.90302
[13] Kemp, M. C., Kimura, Y.: Introduction to Mathematical Economics. Springer New York (1978). MR 0506399 | Zbl 0387.90004
[14] Klee, V.: Separation and support properties of convex sets---a survey. Control Theory and the Calculus of Variations A. V. Balakrishnan Academic Press New York (1969), 235-303.
[15] Nožička, F., Guddat, J., Hollatz, H., Bank, B.: Theorie der linearen parametrischen Optimierung. Akademie-Verlag Berlin (1974), German.
[16] Nožička, F., Grygarová, L., Lommatzsch, K.: Geometrie konvexer Mengen und konvexe Analysis. Akademie-Verlag Berlin (1988). MR 0966885
[17] Padberg, M.: Linear Optimization and Extension. Springer Berlin (1999). MR 1741968
[18] Rockafellar, R. T., Tyrrel, R.: Convex Analysis. Princeton University Press Princeton (1970). MR 0274683
Partner of
EuDML logo