Numerical search for global solutions in problems of non-symmetric bilinear separability

A. V. Orlov

Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 1, pp. 64-85

Résumé

The paper is devoted to the bilinear separability problem of two sets (the non-symmetrical case). The optimization approach to the problem is applied. This approach is based on the reduction of the bilinear separability problem to an equivalent nonconvex bilinear optimization problem with disjoint constraints. The latter problem is solved by Global Search Theory developed by A. S. Strekalovsky. According to that theory, the local and global search methods for the problem under scrutiny were elaborated. Computational testing of the developed methods has shown the competitive efficiency of the approach on a rather large number of test problems of bilinear separability. Ill. 5, tab. 3, bibliogr. 29.

Détail

Keywords: classification problem, bilinear separability, optimization approach, local search, global search, test problem generation, numerical experiment.

Bibliographie

[1] V. N. Vapnik, Restoring Dependencies from Empirical Data, Nauka, Moscow, 1979 | MR | Zbl

[2] V. N. Vapnik, A. Ya. Chervonenkis, The Theory of Pattern Recognition, Nauka, Moscow, 1974 | MR | Zbl

[3] F. P. Vasiliev, Optimization Methods, Faktorial-Press, Moscow, 2002

[4] Yu. I. Zhuravlev, “On an algebraic approach to solving problems of recognition or classification”, Problems of Cybernetics, 33, ed. S. V. Yablonskii, Nauka, Moscow, 1978, 5–68 | Zbl

[5] A. V. Kel'manov, A. V. Pyatkin, “On complexity of some problems of cluster analysis of vector sequences”, J. Appl. Ind. Math., 7:3 (2013), 363–369 | DOI | MR

[6] A. V. Kel'manov, V. I. Khandeev, “A 2-approximation polynomial algorithm for a clustering problem”, J. Appl. Ind. Math., 7:4 (2013), 515–521 | DOI | MR

[7] V. D. Mazurov, The Committee Method in Problems of Optimization and Classification, Nauka, Moscow, 1990 | MR | Zbl

[8] V. D. Mazurov, M. Yu. Khachai, A. I. Rybin, “Committee constructions for solving problems of selection, diagnostics, and prediction”, Proc. Steklov Inst. Math., Supplement Issue 1, 2002, S67–S101 | MR | Zbl

[9] A. V. Orlov, “Numerical solution of bilinear programming problems”, Comput. Math. Math. Phys., 48:2 (2008), 225–241 | DOI | MR | Zbl

[10] A. V. Orlov, “Global search for optimistic solutions in a bilevel problem of optimal tariff choice by a telecommunication company”, Izv. Irkutsk. Gos. Univ., Ser. Mat., 6:1 (2013), 57–71 | Zbl

[11] A. V. Orlov, A. S. Strekalovsky, “On numerical search for the equilibria in bimatrix games”, Comput. Math. Math. Phys., 45:6 (2005), 947–960 | MR | Zbl

[12] K. V. Rudakov, On Some Classes of Pattern Recognition Algorithms: General Results, VTs AN SSSR, Moscow, 1980

[13] V. V. Ryazanov, “Committee synthesis of recognition and classification algorithms”, USSR Comput. Math. Math. Phys., 21:6 (1981), 172–182 | DOI | MR | Zbl | Zbl

[14] A. S. Strekalovsky, The Elements of Non-convex Optimization, Nauka, Novosibirsk, 2003

[15] A. S. Strekalovsky, A. V. Orlov, Bimatrix Games and Bilinear Programming, Fizmatlit, Moscow, 2007 | Zbl

[16] A. S. Strekalovsky, A. V. Orlov, A. V. Malyshev, “Local search in a quadratic-linear bilevel programming problem”, Numer. Anal. Appl., 3:1 (2010), 59–70 | DOI

[17] A. S. Strekalovsky, A. V. Orlov, A. V. Malyshev, “Numerical solution of a class of bilevel programming problems”, Numer. Anal. Appl., 3:2 (2010), 165–173 | DOI

[18] Astorino A., Gaudioso M., “Polyhedral separability through successive LP”, J. Optim. Theory Appl., 112:2 (2002), 265–293 | DOI | MR | Zbl

[19] Astorino A., Gaudioso M., “A fixed-center spherical separation algorithm with kernel transformations for classification problems”, Comput. Manage. Sci., 6:3 (2009), 357–372 | DOI | MR | Zbl

[20] Bagirov A. M., Rubinov A. M., Soukhoroukova N. V., Yearwood J., “Unsupervised and supervised data classification via nonsmooth and global optimization”, Top, 11:1 (2003), 1–75 | DOI | MR

[21] Bennett K. P., Mangasarian O. L., “Bilinear separation of two sets in $n$-space”, Comput. Optim. Appl., 2:3 (1993), 207–227 | DOI | MR | Zbl

[22] Mangasarian O. L., “Linear and nonlinear separation of patterns by linear programming”, Oper. Res., 13:3 (1965), 444–452 | DOI | MR | Zbl

[23] Mangasarian O. L., “Mathematical programming in neural networks”, ORSA J. Computing, 5:4 (1993), 349–360 | DOI | MR | Zbl

[24] Mangasarian O. L., “Misclassification minimization”, J. Global Optim., 5:4 (1994), 309–323 | DOI | MR | Zbl

[25] MATLAB – The language of technical computing, URL: , (data obrascheniya: 25.03.2014) http://www.mathworks.com/products/matlab/

[26] Megiddo N., “On the complexity of polyhedral separability”, Discrete Comput. Geom., 3:4 (1988), 325–337 | DOI | MR | Zbl

[27] Rosen J. B., “Pattern separation by convex programming”, J. Math. Anal. Appl., 10 (1965), 123–134 | DOI | MR | Zbl

[28] Shavlik J. W., Mooney R. J., Towell G. G., “Symbolic and neural network learning algorithms: An experimental comparison”, Machine Learning, 6:2 (1991), 111–143

[29] Zhang G. P., “Neural networks for classification: a survey”, IEEE Trans. Systems, Man and Cybernetics. Part C: Applications and reviews, 30:4 (2000), 451–462 | DOI