Volume 22, No 1, 2015, P. 64–85

UDC 519.853.4 
A. V. Orlov
Numerical search for global solutions in problems of non-symmetric bilinear separability 

Abstract:
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.

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

DOI: 10.17377/daio.2015.22.450

Andrei V. Orlov ¹
1. Institute for System Dynamics and Control Theory SB RAS,
134 Lermontov St., 664033 Irkutsk, Russia 
е-mail: anor@icc.ru

Received 25 March 2014
Revised 26 August 2014

References

[1] V. N. Vapnik, Vosstanovlenie zavisimostei po empiricheskim dannym (Restoring Dependencies from Empirical Data), Nauka, Moscow, 1979.

[2] V. N. Vapnik and A. Ya. Chervonenkis, Teoriya raspoznavaniya obrazov (The Theory of Pattern Recognition), Nauka, Moscow, 1974.

[3] F. P. Vasiliev, Metody optimizatsii (Optimization Methods), Faktorial-Press, Moscow, 2002.

[4] Yu. I. Zhuravlev, On an algebraic approach to solving problems of recognition or classification, in S. V. Yablonskii, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 33, pp. 5–68, Nauka, Moscow, 1978.

[5] A. V. Kel’manov and A. V. Pyatkin, On complexity of some problems of cluster analysis of vector sequences, J. Appl. Ind. Math., 7, No. 3, 363–369, 2013.

[6] A. V. Kel’manov and V. I. Khandeev, A 2-approximation polynomial algorithm for a clustering problem, Diskretn. Anal. Issled. Oper., 20, No. 4, 36–45, 2013. Translated in J. Appl. Ind. Math., 7, No. 4, 515–521, 2013.

[7] V. D. Mazurov, Metod komitetov v zadachakh optimizatsii i klassifikatsii (The Committee Method in Problems of Optimization and Classification), Nauka, Moscow, 1990.

[8] V. D. Mazurov, M. Yu. Khachai, and A. I. Rybin, Committee constructions for solving problems of selection, diagnostics, and prediction, Tr. Inst. Mat. Mekh. UrO RAN, 8, No. 1, 66–102, 2002. Translated in Proc. Steklov Inst. Math., Supplement Issue 1, S67–S101, 2002.

[9] A. V. Orlov, Numerical solution of bilinear programming problems, Zh. Vychisl. Mat. Mat. Fiz., 48, No. 2, 237–254, 2008. Translated in Comput. Math. Math. Phys., 48, No. 2, 225–241, 2008.

[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, No. 1, 57–71, 2013.

[11] A. V. Orlov and A. S. Strekalovsky, On numerical search for the equilibria in bimatrix games, Zh. Vychisl. Mat. Mat. Fiz., 45, No. 6, 983–997, 2005. Translated in Comput. Math. Math. Phys., 45, No. 6, 947–960, 2005.

[12] K. V. Rudakov, O nekotorykh klassakh algoritmov raspoznavaniya: obshchie rezul’taty (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, Zh. Vychisl. Mat. Mat. Fiz., 21, No. 6, 1533–1543, 1981. Translated in USSR Comput. Math. Math. Phys., 21, No. 6, 172–182, 1981.

[14] A. S. Strekalovsky, Elementy nevypukloi optimizatsii (The Elements of Non-convex Optimization), Nauka, Novosibirsk, 2003.

[15] A. S. Strekalovsky and A. V. Orlov, Bimatrichnye igry i bilineinoe programmirovanie (Bimatrix Games and Bilinear Programming), Fizmatlit, Moscow, 2007.

[16] A. S. Strekalovsky, A. V. Orlov, and A. V. Malyshev, Local search in a quadratic-linear bilevel programming problem, Sib. Zh. Vychisl. Mat., 13, No. 1, 75–88, 2010. Translated in Numer. Anal. Appl., 3, No. 1, 59–70, 2010.

[17] A. S. Strekalovsky, A. V. Orlov, and A. V. Malyshev, Numerical solution of a class of bilevel programming problems, Sib. Zh. Vychisl. Mat., 13, No. 2, 201–212, 2010. Translated in Numer. Anal. Appl., 3, No. 2, 165–173, 2010.

[18] A. Astorino and M. Gaudioso, Polyhedral separability through successive LP, J. Optim. Theory Appl., 112, No. 2, 265–293, 2002.

[19] A. Astorino and M. Gaudioso, A fixed-center spherical separation algorithm with kernel transformations for classification problems, Comput. Manag. Sci., 6, No. 3, 357–372, 2009.

[20] A. M. Bagirov, A. M. Rubinov, N. V. Soukhoroukova, and J. Yearwood, Unsupervised and supervised data classification via nonsmooth and global optimization, Top, 11, No. 1, 1–75, 2003.

[21] K. P. Bennett and O. L. Mangasarian, Bilinear separation of two sets in n-space, Comput. Optim. Appl., 2, No. 3, 207–227, 1993.

[22] O. L. Mangasarian, Linear and nonlinear separation of patterns by linear programming, Oper. Res., 13, No. 3, 444–452, 1965.

[23] O. L. Mangasarian, Mathematical programming in neural networks, ORSA J. Comput., 5, No. 4, 349–360, 1993.

[24] O. L. Mangasarian, Misclassification minimization, J. Glob. Optim., 5, No. 4, 309–323, 1994.

[25] MATLAB — The Language of Technical Computing. Available at
http://www.mathworks.com/ products/matlab/. Accessed Mar. 25, 2014.

[26] N. Megiddo, On the complexity of polyhedral separability, Discrete Comput. Geom., 3, No. 4, 325–337, 1988.

[27] J. B. Rosen, Pattern separation by convex programming, J. Math. Anal. Appl., 10, 123–134, 1965.

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

[29] G. P. Zhang, Neural networks for classification: A survey, IEEE Trans. Syst. Man Cybern., Part C: Appl. Rev., 30, No. 4, 451–462, 2000.