Computer Science and Information Technologies, Computer Science and Information Technologies 2010

Font Size: 
A Spinor-Based Approach to Constrained Optimization in the Design of Correct Estimation Algorithms
Alexander Yu. Smetanin

Last modified: 2021-03-29

Abstract


The problem of building correct algorithms of pattern recognition is considered. For some classes of estimation algorithms, criteria for correct algorithms are obtained. Conditions of correctness are formulated in terms of solving a constrained optimization problem. An optimization algorithm based on variable elimination using the spinor
method is proposed. Under the conditions of correctness, the proposed method significantly reduces the computational complexity of synthesizing a correct algorithm.

Keywords


Spinor-Based; Estimation algorithms; Optimization

References


1. Zhuravlev Yu. I. “Correct Algorithms over Sets of Incorrect (Heuristic) Algorithms: Part II”. Kibernetika 1977; 6:21-27.

2. Zhuravlev Yu. I. “Correct Algorithms over Sets of Incorrect (Heuristic) Algorithms: Part III”. Kibernetika 1978; 2:35-43.

3. Zhuraviev Yu. LL, Isaev I. V. “Constructing Recognition Algorithms That are Correct for a Given Validation Sample”. Zh. Vychisl. Mat. Mat. Fiz. 1979; 19:726-738.

4. Rudakov K. V. “On Certain Classes of Recognition Algorithms (General Results)”. Vychisl. Tsentr Akad. Nauk SSSR, Moscow, 1980.

5. Rudakov K. V. “On Certain Classes of Recognition Algorithms (Parametric Models)”. Vychisl. Tsentr Akad. Nauk SSSR, Moscow, 1981.

6. Ryazanov V. V. “Optimization of Estimation Algorithms Using Parameters Describing — the Representative Property of Reference Rows”. Zh, Vychisl. Mat. Mat. Fiz. 1976; 16:1559-1570 (1976).

7, Ryazanov V. V. Optimal Group Decisions in Recognition and Classification. Doctoral Dissertation in Mathematics and Physics, VITs RAN, Moscow, 1994,

8. Katerinochkina N. N. “Methods for Finding a Maximal Consistent Subsystem of a System of Linear Inequalities”. Communications in Applied Mathematics, Vychisl. Tsentr, Ross. Akad. Nauk, Moscow, 1997.

9. Polyak B. T. “Introduction to Optimization”. Nauka, Moscow, 1983. 10. Pshenichnikov S. B., Shtern A. G. “Methods for Solving Systems of Nonlinear Algebraic Equations”. Mathematical Methods and Computer-Aided Systems in Geology: A Survey, Moscow, 1995.

10. Pshenichnikov S. B., Shtern A. G. “Methods for Solving Systems of Nonlinear Algebraic Equations”. Mathematical Methods and Computer-Aided Systems in Geology: A Survey, Moscow, 1995.

11. Pshenichnikov S. B. “Spinor Elimination and Formulae for Relations between Unknowns in Systems of Nonlinear Algebraic Equations”. Latv. Mat. Ezhegodnik 1986; 30:150-161.

12.Zaitsev G. A. “Algebraic Problems in Mathematical and Theoretical Physics” Nauka, Moscow, 1974.

13.Rybnikov K. A. “Introduction to Combinatorial Analysis”. Mosk. Gos. Univ., Moscow, 1985. 14.Edmonds J. “Matroids and the Greedy Algorithm”. Math. Program. 1971; 1:127 — 136.

14. Edmonds J. "Matroids and the Greedy Algorithm". Math. Program. 1971; 1:127 - 136.


Full Text: PDF