Optimization Online


Separation of convex polyhedral sets with uncertain data

Milan Hladik(milan.hladik***at***matfyz.cz)

Abstract: This paper is a contribution to the interval analysis and separability of convex sets. Separation is a familiar principle and is often used not only in optimization theory, but in many economic applications as well. In real problems input data are usually not known exactly. For the purpose of this paper we assume that data can independently vary in given intervals. We study two cases when convex polyhedral sets are described by a system of linear inequalities or by the list of its vertices. For each case we propose a way how to check whether given convex polyhedral sets are separable for some or for all realizations of the interval data. Some of the proposed problems can be checked efficiently, while the others are NP-hard.

Keywords: Separating hyperplane, convex polyhedra, interval analysis, linear interval equation, linear interval inequalities

Category 1: Convex and Nonsmooth Optimization (Other )

Category 2: Robust Optimization

Citation: Proceedings of the 24-th Int. Conf. Mathematical Methods in Economics MME06, Pilsen, 2006, pp. 227-234.

Download: [Postscript][PDF]

Entry Submitted: 02/28/2007
Entry Accepted: 03/01/2007
Entry Last Modified: 02/28/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society