Improvement of the estimations of solutions in the semidefinite programmin

Authors

  • A. I. Kosolap Department of specialized computer systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipropetrovsk 49005, Ukraine

DOI:

https://doi.org/10.30838/P.CMM.2415.270818.68.232

Keywords:

complex systems, semidefinite relaxation, quadratic problems, primer-dual interior point method, modification of semidefinite programming problems.

Abstract

Purpose. We develop new methods for solving optimization models of complex systems. Such models arise in technology, artificial intelligence, design, construction and management of complex systems. Solving such optimization problems is a complex computational problem. This problem is to develop effective methods for solving such classes. Methodology. In this paper, we propose to transform the classes of problems to problems of semidefinite programming and to use their solutions for primer-dual interior point methods. We propose an iterative procedure for modifying the corresponding problem of semidefinite programming, which makes it possible to find exact solutions of the original problem. Findings. To solve the problems of quadratic optimization, semi-definite relaxation and a direct-dual method of the interior point are used. An iterative procedure for modifying semidefinite programming problems is constructed, which makes it possible to obtain an exact solution of the original problem. The obtained results are confirmed by numerical experiments. Originality. A new methodology for solving complex optimization problems that arise in modeling complex systems using semidefinite relaxation is developed. A sequential modification of the problems of semidefinite optimization is proposed. Practical value. We considered technique for solving complex quadratic optimization problems is realized in the form of software. Comparative experiments confirm the effectiveness of this technique in solving classes of problems of quadratic optimization.

Author Biography

A. I. Kosolap, Department of specialized computer systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipropetrovsk 49005

Dr. Sc. (Phys.-Math.), Prof.

References

Kosolap A.I. Metody globalnoy optimizatsii [Methods of global optimization]. Dnipropetrovsk, Nauka i obrazovanie Publ., 2013, 316 p. (in Russian).

Kosolap A.I. and Peretiatko A.S. Poluopredelennoe programmirovanie i ego prilozheniya [Semidefinite programming and its applications]. Dnepr, PGASA, 2018, 148 p. (in Russian).

Dur M. Duality in Global Optimization: Optimality Conditions and Algorithmical Aspects /M. Dur. – Shaker Verlag, 1999, – 117 p.

Floudas, C.A. Deterministic global optimization: theory, algorithms and applications. Kluwer Academic Publishers, 2000, 57 p.

Floudas, С.A. and Gounaris C.E. A review of recent advances in global optimization. J. Glob. Optim., 2009, v. 45, no. 1. pp. 3–38.

Horst, R. and Tuy H. Global Optimization: Deterministic Approaches. 3rd ed., Berlin, Springer–Verlag, 1996, 727 p.

Kenneth, V.P., Storn R.M. and Lampinen J.A. Differential Evolution. A Practical Approach to Global Optimization. Berlin Heidelberg, Springer-Verlag, 2005, 542 p.

Nocedal, J. and Wright S. J. Numerical optimization. Springer, 2006, 685 p.

Sherali H. D. and Adams W. P. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Springer Publ., 2010, 518 p.

Ye Y. Semidefinite programming. Stanford, Stanford University, 2003, 161 p.

Published

2018-11-27

Issue

Section

Computer systems and information technologies in education, science and management