×

Arbitrary-norm separating plane. (English) Zbl 1028.90037

Summary: A plane separating two point sets in \(n\)-dimensional real space is constructed such that it minimizes the sum of arbitrary-norm distances of misclassified points to the plane. In contrast to previous approaches that used surrogates for distance-minimization, the present work is based on a precise norm-dependent explicit closed form for the projection of a point on a plane. This projection is used to formulate the separating-plane problem as a minimization of a convex function on a unit sphere in a norm dual to that of the arbitrary norm used. For the 1-norm, the problem can be solved in polynomial time by solving \(2n\) linear programs or by solving a bilinear program. For a general \(p\)-norm, the minimization problem can be transformed via an exact penalty formulation to minimizing the sum of a convex function and a bilinear function on a convex set. For the one and infinity norms, a finite successive linearization algorithm can be used for solving the exact penalty formulation.

MSC:

90C25 Convex programming
49M37 Numerical methods based on nonlinear programming
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] E.F. Beckenbach, R. Bellman, Inequalities, Springer, Berlin, 1961.
[2] Bennett, K.P.; Mangasarian, O.L., Robust linear programming discrimination of two linearly inseparable sets, Optim. meth. software, 1, 23-34, (1992)
[3] Bennett, K.P.; Mangasarian, O.L., Bilinear separation of two sets in n-space, Comput. optim. appl., 2, 207-227, (1993) · Zbl 0795.90060
[4] P.S. Bradley, O.L. Mangasarian, W.N. Street, Clustering via concave minimization, in: M.C. Mozer, M.I. Jordan, T. Petsche (Eds.), Advances in Neural Information Processing Systems -9-, MIT Press, Cambridge, MA, 1997, pp. 368-374. ftp://ftp.cs.wisc.edu/math-prog/tech-reports/96-03.ps.Z.
[5] Bramley, R.; Winnicka, B., Solving linear inequalities in a least square sense, SIAM J. sci. comput., 17, 275-286, (1996) · Zbl 0844.65024
[6] A. Charnes, Some fundamental theorems of perceptron theory and their geometry, in: J.T. Lou, R.H. Wilcox (Eds.), Computer and Information Sciences, Spartan Books, Washington, D.C., 1964, pp. 67-74. · Zbl 0143.39801
[7] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval res. logistics Q., 3, 95-110, (1956)
[8] Glover, F., Improved linear programming models for discriminant analysis, Decision sci., 21, 771-785, (1990)
[9] Grinold, R.C., Mathematical methods for pattern classification, Management sci., 19, 272-289, (1972) · Zbl 0269.68056
[10] J. Hertz, A. Krogh, R.G. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, Redwood City, CA, 1991.
[11] Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[12] Mangasarian, O.L., Linear and nonlinear separation of patterns by linear programming, Oper. res., 13, 444-452, (1965) · Zbl 0127.36701
[13] O.L. Mangasarian, Multi-surface method of pattern separation, IEEE Trans. Inform. Theory IT-14 (1968) 801-807. · Zbl 0169.51108
[14] O.L. Mangasarian, Nonlinear Programming, McGraw-Hill, New York, 1969. Reprint: SIAM Classic in Applied Mathematics 10, 1994, Philadelphia.
[15] O.L. Mangasarian, Some applications of penalty functions in mathematical programming, in: R. Conti, E. De Giorgi, F. Giannessi (Eds.), Optimization and Related Fields, Lecture Notes in Mathematics, vol. 1190, Springer, Heidelberg, 1986, pp. 307-329.
[16] Mangasarian, O.L., Misclassification minimization, J. global optim., 5, 309-323, (1994) · Zbl 0814.90081
[17] Mangasarian, O.L., The linear complementarity problem as a separable bilinear program, J. global optim., 6, 153-161, (1995) · Zbl 0835.90102
[18] O.L. Mangasarian, Arbitrary-norm separating plane, Technical Report 97-07, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, May 1997. ftp://ftp.cs.wisc.edu/math-prog/tech-reports/97-07.ps.Z. · Zbl 1028.90037
[19] O.L. Mangasarian, J.-S. Pang, Exact penalty functions for mathematical programs with linear complementarity constraints, Optimization 42 (1997) 1-8. //ftp.cs.wisc.edu/math-prog/tech-reports/96-06.ps.Z. · Zbl 0888.90134
[20] O.L. Mangasarian, R. Setiono, W.H. Wolberg, Pattern recognition via linear programming: theory and application to medical diagnosis, in: T.F. Coleman, Y. Li, (Eds.), Large-Scale Numerical Optimization, SIAM, Philadelphia, PA, 1990, pp. 22-31. Proceedings of the Workshop on Large-Scale Numerical Optimization, Cornell University, Ithaca, New York, 19-20 October 1989. · Zbl 0726.90096
[21] Motzkin, T.S.; Schoenberg, I.J., The relaxation method for linear inequalities, Can. J. math., 6, 393-404, (1954) · Zbl 0055.35002
[22] N.J. Nilsson, Learning Machines, MIT Press, Cambridge, MA, 1966. · Zbl 0152.35705
[23] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[24] G.W. Stewart, Introduction to Matrix Computations, Academic Press, New York, 1973. · Zbl 0302.65021
[25] R.J. Vanderbei, Linear Programming: Foundations and Extensions, Kluwer Academic Publishers, Hingham, MA, 1997. · Zbl 0874.90133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.