Abstract

This work addresses the issue of separating two finite sets in Rn\mathbb{R}^n by means of a suitable revolution cone Γ(z,y,s)={x∈Rn:s ∥x−z∥−yT(x−z)=0}.\Gamma (z,y,s)= \{x \in \mathbb{R}^n: s\,\Vert x-z\Vert - y^T(x-z)=0\}. The specific challenge at hand is to determine the aperture coefficient ss, the axis yy, and the apex zz of the cone. These parameters have to be selected in such a way as to meet certain optimal separation criteria. Part I of this work focusses on the homogeneous case in which the apex of the revolution cone is the origin of the space. The homogeneous case deserves a separated treatment, not just because of its intrinsic interest, but also because it helps to built up the general theory. Part II of this work concerns the non-homogeneous case in which the apex of the cone can move in some admissible region. The non-homogeneous case is structurally more involved and leads to challenging nonconvex nonsmooth optimization problems.

Author information

Contact details are reproduced from the original publication and may be historical.

Annabella Astorino

Istituto di Calcolo e Reti ad Alte Prestazioni C.N.R., Università della Calabria, 87036 Rende, Italy

astorino@icar.cnr.it

Manlio Gaudioso

Dip. di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, Università della Calabria, 87036 Rende, Italy

gaudioso@deis.unical.it

Keywords

  • Conical separation
  • revolution cone
  • convex optimization
  • DC-optimization
  • proximal point techniques
  • classification

Mathematics Subject Classification

90C25, 90C26

References

  1. L. T. H. An, P. D. Tao: A D.C. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim. 8 (1998) 476–505.https://doi.org/10.1137/S1052623494274313Google Scholar
  2. A. Astorino, A. Fuduli, M. Gaudioso: DC models for spherical separation, J. Glob. Optim. 48 (2010) 657–669.https://doi.org/10.1007/s10898-010-9558-0Google Scholar
  3. A. Astorino, M. Gaudioso: Polyhedral separability through successive LP, J. Optim. Theory Appl. 112 (2002) 265–293.https://doi.org/10.1023/A:1013649822153Google Scholar
  4. A. Astorino, M. Gaudioso: Ellipsoidal separation for classification problems, Optim. Methods Softw. 20 (2005) 267–276.https://doi.org/10.1080/10556780512331318254Google Scholar
  5. A. Astorino, M. Gaudioso, A. Seeger: Conic separation of finite sets. II. The nonhomogeneous case, J. Convex Analysis 21(3) (2014), to appear.https://doi.org/10.68381/jca21044Google Scholar
  6. C. Bergeron, G. Moore, J. Zaretzki, C. M. Breneman, K. P. Bennett: Fast bundle algorithm for multiple instance learning, IEEE Trans. Pattern Anal. Mach. Intell. 34 (2011) 1068–1079,https://doi.org/10.1109/TPAMI.2011.194Google Scholar
  7. C.-C. Chang, C.-J. Lin: LIBSVM: A library for support vector machines, ACM Trans. Intell. Syst. Technol. 2 (2011) 27:1–27:27; software available at: www.csie.ntu.edu.tw/~cjlin/libsvm.https://doi.org/10.1145/1961189.1961199Google Scholar
  8. O. Chapelle, A. Zien: Semi-supervised classification by low density separation, in: Proc. 10th Intern. Workshop on Artificial Intelligence and Statistics (2005) 57–64.Google Scholar
  9. P. H. Dien, G. Mastroeni, M. Pappalardo, P. H. Quang: Regularity conditions for constrained extremum problems via image space: the nonlinear case, J. Optim. Theory Appl. 80 (1994) 19–37.https://doi.org/10.1007/BF02196591Google Scholar
  10. J. E. Falk, V. E. Karlov: Robust separation of finite sets via quadratics, Comput. Oper. Res. 28(6) (2001) 537–561.https://doi.org/10.1016/S0305-0548(99)00134-3Google Scholar
  11. A. Fuduli, M. Gaudioso, G. Giallombardo: Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim. 14 (2004) 743–756.https://doi.org/10.1137/S1052623402411459Google Scholar
  12. R. N. Gasimov, G. Ozturk: Separation via polyhedral conic functions, Optim. Methods Softw. 21 (2006) 527–540.https://doi.org/10.1080/10556780600723252Google Scholar
  13. E. G. Gilbert, D. W. Johnson, S. S. Keerthi: A fast procedure for computing the distance between complex objects, IEEE J. Robot. Autom. 4 (1988) 193–203.https://doi.org/10.1109/56.2083Google Scholar
  14. Y.-J. Gotoh, H. Konno, S. Uryasev, A. Yuki: Failure discrimination by semidefinite programming, in: Financial Engineering, E-Commerce and Supply Chain, P. M. Pardalos, V. K. Tsitsiringos (eds.), Kluwer, Dordrecht (2002) 379–396.https://doi.org/10.1007/978-1-4757-5226-7_21Google Scholar
  15. M. I. Henig: A cone separation theorem, J. Optim. Theory Appl. 36 (1982) 451–455.https://doi.org/10.1007/BF00934357Google Scholar
  16. M. L. Hoai, A. L. T. Hoai, P. D. Tao, V. N. Ngai: An efficient DCA for spherical separation, in: Intelligent Information and Database Systems, Part II (Daegu, 2011), N. T. Nguyen et al. (eds.), Lecture Notes in Computer Science 6592, Springer, Berlin (2011) 421–431.https://doi.org/10.1007/978-3-642-20042-7_43Google Scholar
  17. R. Kasimbeyli: A nonlinear cone separation theorem and scalarization in nonconvex vector optimization, SIAM J. Optim. 20 (2009) 1591–1619.https://doi.org/10.1137/070694089Google Scholar
  18. K. Kim, H. S. Ryoo: Data separation via a finite number of discriminant functions: a global optimization approach, Appl. Math. Comput. 190 (2007) 476–489.https://doi.org/10.1016/j.amc.2007.01.051Google Scholar
  19. O. L. Mangasarian: Linear and nonlinear separation of patterns by linear programming, Oper. Res. 13 (1965) 444–452.https://doi.org/10.1287/opre.13.3.444Google Scholar
  20. G. Mastroeni, M. Pappalardo: Separation and regularity in the image space, in: New Trends in Mathematical Programming, F. Giannessi, S. Komlósi, T. Rapcsák (eds.), Kluwer, Dordrecht (1998) 181–190.https://doi.org/10.1007/978-1-4757-2878-1_14Google Scholar
  21. P. M. Murphy, D. W. Aha: UCI repository of machine learning databases, available at: www.ics.uci.edu/~mlearn/MLRepository.html (1992).Google Scholar
  22. S. Odewahn, E. Stockwell, R. Pennington, R. Humphreys, W. Zumach: Automated star/galaxy discrimination with neural networks, Astrophys. J. 103 (1992) 318–331.https://doi.org/10.1086/116063Google Scholar
  23. M. Pappalardo: On the image regularity condition, J. Optim. Theory Appl. 121 (2004) 673–678.https://doi.org/10.1023/B:JOTA.0000037687.36868.5aGoogle Scholar
  24. R. T. Rockafellar: Convex Analysis, Princeton Univ. Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar

Suggested citation

A. Astorino, M. Gaudioso, A. Seeger. “Conic Separation of Finite Sets. I: The homogeneous case.” Journal of Convex Analysis 21 (2014), No. 1, 1–28. https://doi.org/10.68381/jca21001

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2014. Rights now held by Banach Press LLC.