Abstract

[For part I of this article see this journal 21 (2013), Number 1.] We address 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\}. One has to select the aperture coefficient ss, the axis yy, and the apex zz in such a way as to meet certain optimal separation criteria. The homogeneous case z=0z=0 has been treated in Part I of this work. We now discuss the more general case in which the apex of the cone is allowed to move in a certain 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., Dip. di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, 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@dimes.unical.it

Keywords

  • Conical separation
  • revolution cone
  • alternating minimization
  • DC programming
  • classification

Mathematics Subject Classification

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, M. Gaudioso, A. Seeger: Conic separation of finite sets. I. The homogeneous case, J. Convex Analysis 21 (2014) 1–28.https://doi.org/10.68381/jca21001Google Scholar
  3. I. M. Bomze, M. Locatelli: Undominated d.c. decompositions of quadratic functions and applications to Branch-and-Bound approaches, Comput. Optim. Appl. 28 (2004) 227–245.https://doi.org/10.1023/B:COAP.0000026886.61324.e4Google Scholar
  4. 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
  5. 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
  6. P. Tseng: Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001) 475–494.https://doi.org/10.1023/A:1017501703105Google Scholar

Suggested citation

A. Astorino, M. Gaudioso, A. Seeger. “Conic Separation of Finite Sets. II: The Non-Homogeneous Case.” Journal of Convex Analysis 21 (2014), No. 3, 819–831. https://doi.org/10.68381/jca21044

Download BibTeXPublished by Heldermann Verlag.

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