Peretiatko A. Semidefinite optimization for solving general quadratic problems

Research object - semidefinite optimization problems and their solution methods. The purpose of research is to prove convergence and to improve the semidefinite simplex method for solving semidefinite optimization problems, to use and improve the semidefinite relaxation for solving quadratic optimization applications. Research methods - multidimensional Euclidean geometry, convex analysis, mathematical modeling, theory and numerical methods of optimization were used. For solving general quadratic problems semidefinite relaxation method, the exact quadratic regularization, semidefinite simplex method and primal-dual interior point method were used. Research equipment - personal computer. Theoretical and practical results - improved semidefinite simplex method can be used for a wide range of practical problems. In particular, in data clustering, wireless sensor network localization, camera calibration algorithms, for graph coloring and others. The developed software for solving semidefinite optimization problems implements primal-dual interior point method and semidefinite simplex method, and its efficiency has been tested on the problems of different dimensions. Scientific novelty of the research consists in justification and improvement of semidefinite simplex method as an alternative to the existing primal-dual interior point methods for solving semidefinite optimization problems. In particular, inverse iteration procedure, which is used to determine the positive semidefiniteness of matrix, was improved by using the method of conjugate directions that allowed to improve the accuracy of calculations and to accelerate the convergence to the eigenvector. For the first time the convergence of semidefinite simplex method was proved, its theoretical and computational advantages were found. Semidefinite relaxation for the general quadratic problems and a wide range of applications was improved (with the help of precise quadratic regularization and other transformations), that in contrast to the existing methods allowed us to find the best solutions of the original problem. The accuracy of the semidefinite relaxation for certain classes of problems of maximizing the Euclidean vector norm on a convex set was proved. For the first time a new procedure for determining the upper and lower bounds of the objective function was proposed and tested in practice, which allowed to get the best solutions of general quadratic optimization problems. The research results were used: in the state budgetary research work which is part of the thematic plan of scientific research of SHEI "Ukrainian State University of Chemical Technology" (№ of state registration 0112U004341, 2012-2014); in the educational process at the Department of specialized computer systems of SHEI "Ukrainian State University of Chemical Technology" (Act of 10/22/2014).