IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v158y2013i1d10.1007_s10957-012-0155-x.html
   My bibliography  Save this article

A Linear Separability Criterion for Sets of Euclidean Space

Author

Listed:
  • Z. R. Gabidullina

    (Kazan Federal University)

Abstract

We prove new theorems which describe a necessary and sufficient condition for linear (strong and non-strong) separability and inseparability of the sets in a finite-dimensional Euclidean space. We propose a universal measure for the thickness of the geometric margin (both the strong separation margin (separator) and the margin of unseparated points (pseudo-separator)) formed between the parallel generalized supporting hyperplanes of the two sets which are separated. The introduced measure allows comparing results of linear separation obtained by different techniques for both linearly separable and inseparable sets. An optimization program whose formulation provides a maximum thickness of the separator for the separable sets is considered. When the sets are inseparable, the same solver is guaranteed to construct a pseudo-separator with a minimum thickness. We estimate the distance between the convex and closed sets. We construct a cone of generalized support vectors for hyperplanes, each one of which linearly separates the considered sets. The interconnection of the problem of different types of linear separation of sets with some related problems is studied.

Suggested Citation

  • Z. R. Gabidullina, 2013. "A Linear Separability Criterion for Sets of Euclidean Space," Journal of Optimization Theory and Applications, Springer, vol. 158(1), pages 145-171, July.
    • Handle: RePEc:spr:joptap:v:158:y:2013:i:1:d:10.1007_s10957-012-0155-x
    DOI: 10.1007/s10957-012-0155-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-012-0155-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-012-0155-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Z. R. Gabidullina, 2011. "A Theorem on Strict Separability of Convex Polyhedra and Its Applications in Optimization," Journal of Optimization Theory and Applications, Springer, vol. 148(3), pages 550-570, March.
    2. O. L. Mangasarian, 1965. "Linear and Nonlinear Separation of Patterns by Linear Programming," Operations Research, INFORMS, vol. 13(3), pages 444-452, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Emilio Carrizosa & Belen Martin-Barragan, 2011. "Maximizing upgrading and downgrading margins for ordinal regression," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(3), pages 381-407, December.
    2. Yu, Lean & Wang, Shouyang & Lai, Kin Keung, 2009. "An intelligent-agent-based fuzzy group decision making model for financial multicriteria decision support: The case of credit scoring," European Journal of Operational Research, Elsevier, vol. 195(3), pages 942-959, June.
    3. Brandner, Hubertus & Lessmann, Stefan & Voß, Stefan, 2013. "A memetic approach to construct transductive discrete support vector machines," European Journal of Operational Research, Elsevier, vol. 230(3), pages 581-595.
    4. Dimitris Bertsimas & Romy Shioda, 2007. "Classification and Regression via Integer Optimization," Operations Research, INFORMS, vol. 55(2), pages 252-271, April.
    5. Heydari Majeed & Yousefli Amir, 2017. "A new optimization model for market basket analysis with allocation considerations: A genetic algorithm solution approach," Management & Marketing, Sciendo, vol. 12(1), pages 1-11, March.
    6. B Baesens & C Mues & D Martens & J Vanthienen, 2009. "50 years of data mining and OR: upcoming trends and challenges," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 16-23, May.
    7. Pedro Duarte Silva, A., 2017. "Optimization approaches to Supervised Classification," European Journal of Operational Research, Elsevier, vol. 261(2), pages 772-788.
    8. J. J. Glen, 2004. "Dichotomous categorical variable formation in mathematical programming discriminant analysis models," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(4), pages 575-596, June.
    9. Xeniya Vladimirovna Grigor’eva, 2016. "Approximate Functions in a Problem of Sets Separation," Journal of Optimization Theory and Applications, Springer, vol. 171(2), pages 550-572, November.
    10. A. Astorino & A. Fuduli & M. Gaudioso, 2010. "DC models for spherical separation," Journal of Global Optimization, Springer, vol. 48(4), pages 657-669, December.
    11. Zhengyu Ma & Hong Seo Ryoo, 2021. "Spherical Classification of Data, a New Rule-Based Learning Method," Journal of Classification, Springer;The Classification Society, vol. 38(1), pages 44-71, April.
    12. Glen, J.J., 2006. "A comparison of standard and two-stage mathematical programming discriminant analysis methods," European Journal of Operational Research, Elsevier, vol. 171(2), pages 496-515, June.
    13. Meisel, Stephan & Mattfeld, Dirk, 2010. "Synergies of Operations Research and Data Mining," European Journal of Operational Research, Elsevier, vol. 206(1), pages 1-10, October.
    14. Lorenzo Gai & Federica Ielasi, 2014. "Operational drivers affecting credit risk of mutual guarantee institutions," Journal of Risk Finance, Emerald Group Publishing, vol. 15(3), pages 275-293, May.
    15. Lean Yu & Lihang Yu & Kaitao Yu, 2021. "A high-dimensionality-trait-driven learning paradigm for high dimensional credit classification," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 7(1), pages 1-20, December.
    16. Lean Yu & Xinxie Li & Ling Tang & Zongyi Zhang & Gang Kou, 2015. "Social credit: a comprehensive literature review," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 1(1), pages 1-18, December.
    17. J. Paul Brooks, 2011. "Support Vector Machines with the Ramp Loss and the Hard Margin Loss," Operations Research, INFORMS, vol. 59(2), pages 467-479, April.
    18. Wanpracha Art Chaovalitwongse, 2008. "Novel quadratic programming approach for time series clustering with biomedical application," Journal of Combinatorial Optimization, Springer, vol. 15(3), pages 225-241, April.
    19. Nieddu, Luciano & Patrizi, Giacomo, 2000. "Formal methods in pattern recognition: A review," European Journal of Operational Research, Elsevier, vol. 120(3), pages 459-495, February.
    20. R Fildes & K Nikolopoulos & S F Crone & A A Syntetos, 2008. "Forecasting and operational research: a review," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1150-1172, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:158:y:2013:i:1:d:10.1007_s10957-012-0155-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.