Geodesic
Some approaches to the solution of optimization problems in supervised learning
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 11, pp. 1959-1966 
N. N. Katerinochkina. Some approaches to the solution of optimization problems in supervised learning. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 11, pp. 1959-1966. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_11_a13/
@article{ZVMMF_2015_55_11_a13,
     author = {N. N. Katerinochkina},
     title = {Some approaches to the solution of optimization problems in supervised learning},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1959--1966},
     year = {2015},
     volume = {55},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_11_a13/}
}
TY  - JOUR
AU  - N. N. Katerinochkina
TI  - Some approaches to the solution of optimization problems in supervised learning
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 1959
EP  - 1966
VL  - 55
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_11_a13/
LA  - ru
ID  - ZVMMF_2015_55_11_a13
ER  - 
%0 Journal Article
%A N. N. Katerinochkina
%T Some approaches to the solution of optimization problems in supervised learning
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 1959-1966
%V 55
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_11_a13/
%G ru
%F ZVMMF_2015_55_11_a13

Voir la notice de l'article provenant de la source Math-Net.Ru

There are some optimization problems that arise when highly accurate recognition algorithms are developed. One of them is to determine an optimal feasible (consistent) subsystem in a given system of linear inequalities. The optimality is defined by a number of constraints imposed on the subsystem, which can vary. Various approaches to the solution of this problem are proposed. Solution methods based on the search through the set of nodal subsystems of the given system of linear inequalities are developed. This can be exhaustive search or partial guided search that finds an approximate solution. A drastically different approximate method based on geometric considerations is proposed.

[1] Chakravarti N., “Some results concerning post-infeasibility analysis”, J. Oper. Res., 73 (1994), 139–143 | DOI | Zbl

[2] Chernikov S. N., Lineinye neravenstva, Nauka, M., 1968 | MR

[3] Parker M., Ryan J., “Finding the minimum weight IIS cover of an infeasible system of linear inequalities”, Ann. Math. Artif. Intell., 17:1–2 (1996), 107–126 | DOI | MR | Zbl

[4] Amaldi E., Hauser R., Randomized relaxation methods for the maximum feasible subsystem problem, Tech. Report 2001-90, DEI, Politecnico di Milano, 2001

[5] Chinneck J. W., “An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem”, Ann. Math. Artiff. Intell., 17:1–2 (1996), 127–144 | DOI | MR | Zbl

[6] Pfetsch M. E., The maximum feasible subsystem problem and vertex-facet incidences of polyhedra, PhD thesis, Dep. of Mathematics, Technische Universität Berlin, October 2002

[7] Eremin I. I., Lineinaya optimizatsiya i sistemy lineinykh neravenstv, Izdatelskii tsentr “Akademiya”, M., 2007

[8] Katerinochkina N. N., Metody vydeleniya maksimalnoi sovmestnoi podsistemy sistemy lineinykh neravenstv, Soobschenie po prikladnoi matematike, VTs RAN, M., 1997, 15 pp.

[9] Katerinochkina N. N., “Decision methods for some discrete extreme problems in recognition theory”, Pattern Recognition and Image Analysis, 18:4 (2008), 584–587 | DOI

[10] Katerinochkina N. N., Shmakov A. S., “Parallelnaya realizatsiya algoritma vydeleniya optimalnoi sovmestnoi podsistemy sistemy lineinykh neravenstv”, Tr. 13-i Vserossiiskoi konferentsii “Matematicheskie metody raspoznavaniya obrazov”, MAKS Press, M., 2007, 257–261

[11] Katerinochkina N. N., “Decision methods for some optimization problems in recognition theory”, Pattern Recognition and Image Analysis, 19:3 (2009), 441–446 | DOI

[12] Katerinochkina N. N., “On some optimization problem for systems of linear inequalities”, Pattern Recognition and Image Analysis, 20:4 (2010), 447–450 | DOI