Stability of compatible systems of linear inequalities and linear separability

O. V. Muraveva

Diskretnyj analiz i issledovanie operacij, Tome 21 (2014) no. 3, pp. 53-63.

Résumé

We consider methods of correction of matrices (or correction of all parameters) of systems of linear constraints (equations and inequalities). We show that the problem of matrix correction of an inconsistent system of linear inequalities with a non-negativity condition is reduced to a linear program. A stability measure of the feasible solution to a linear system is defined as the minimal possible variation of parameters at which this solution does not satisfy the system. The problem of finding the most stable solution to the system is considered. The results are applied to construct an optimal separating hyperplane that is the most stable to variations of the objects. Bibliogr. 15.

Détail

Keywords: stability of compatible system of linear inequalities, separating hyperplane.
Mots-clés : matrix correction

Bibliographie

[1] Barkalova O. S., “Korrektsiya nesobstvennykh zadach lineinogo programmirovaniya v kanonicheskoi forme po minimaksnomu kriteriyu”, Zhurn. vychisl. matematiki i mat. fiziki, 52:12 (2012), 2178–2189 | Zbl

[2] Vatolin A. A., “Korrektsiya rasshirennoi matritsy nesovmestnoi sistemy lineinykh neravenstv i uravnenii”, Matematicheskie metody optimizatsii v ekonomiko-matematicheskom modelirovanii, Nauka, M., 1991, 240–249

[3] Gorelik V. A., “Matrichnaya korrektsiya zadachi lineinogo programmirovaniya s nesovmestnoi sistemoi ogranichenii”, Zhurn. vychisl. matematiki i mat. fiziki, 41:11 (2001), 1697–1705 | MR | Zbl

[4] Gorelik V. A., Erokhin V. I., Pechënkin R. V., “Optimalnaya matrichnaya korrektsiya nesovmestnykh sistem lineinykh algebraicheskikh uravnenii s blochnymi matritsami koeffitsientov”, Diskret. analiz i issled. operatsii. Ser. 2, 12:2 (2005), 3–23 | MR | Zbl

[5] Gorelik V. A., Erokhin V. I., Pechënkin R. V., Chislennye metody korrektsii nesobstvennykh zadach lineinogo programmirovaniya i strukturnykh sistem uravnenii, VTs RAN, M., 2006, 150 pp. | MR

[6] Gorelik V. A., Erokhin V. I., Pechënkin R. V., “Minimaksnaya matrichnaya korrektsiya nesovmestnykh sistem lineinykh algebraicheskikh uravnenii s blochnymi matritsami koeffitsientov”, Izv. RAN. Teoriya i sistemy upravleniya, 2006, no. 5, 52–62 | MR | Zbl

[7] Gorelik V. A., Zoltoeva I. A., Pechënkin R. V., “Metody korrektsii nesovmestnykh lineinykh sistem s razrezhennymi matritsami”, Diskret. analiz i issled. operatsii. Ser. 2, 14:2 (2007), 62–75 | MR | Zbl

[8] Gorelik V. A., Ibatullin R. R., “Korrektsiya sistemy ogranichenii zadachi lineinogo programmirovaniya s minimaksnym kriteriem”, Modelirovanie, dekompozitsiya i optimizatsiya slozhnykh dinamicheskikh protsessov, VTs RAN, M., 2001, 89–107 | MR

[9] Gorelik V. A., Muraveva O. V., “Neobkhodimye i dostatochnye usloviya suschestvovaniya minimalnoi matritsy v zadache korrektsii nesovmestnoi sistemy lineinykh uravnenii”, Modelirovanie, dekompozitsiya i optimizatsiya slozhnykh dinamicheskikh protsessov, VTs RAN, M., 2000, 14–20 | MR

[10] Eremin I. I., Mazurov V. D., Astafev N. N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp. | MR

[11] Muraveva O. V., “Vozmuschenie i korrektsiya sistem lineinykh neravenstv”, Upravlenie bolshimi sistemami, 28, 2010, 40–57

[12] Muraveva O. V., “Robastnost i korrektsiya lineinykh modelei”, Avtomatika i telemekhanika, 2011, no. 3, 98–112 | MR | Zbl

[13] Fidler M., Nedoma I., Ramik Ya., Ron I., Tsimmermann K., Zadachi lineinoi optimizatsii s netochnymi dannymi, NITs “Regulyarnaya i khaoticheskaya dinamika”, Institut kompyuternykh issledovanii, M.–Izhevsk, 2008, 288 pp.

[14] Cortes C., Vapnik V., “Support vector networks”, Machine Learning, 20:3 (1995), 273–297 | Zbl

[15] Ben-Tal A., El Ghaoui L., Nemirovski A., Robust optimization, Princeton Univ. Press, Princeton, 2009, 542 pp. | MR | Zbl