Сonvex relaxation in multiextremal problems
Journal Title: Комп’ютерне моделювання: аналіз, управління, оптимізація - Year 2018, Vol 1, Issue 1
Abstract
In this paper multiextremal problems in a finite-dimensional Euclidean space are considered. Such problems arise in the mathematical modeling of complex systems in the economy, finance, management, technological processes, transport, design, computer science and other fields. It is known that this class of problems contains discrete problems, the problems of solving nonlinear equations and other applied problems To solve multiextremal problems branch and boundary methods, semidefinite programming, duality methods, genetic and evolutionary methods, and many others are used nowadays. These methods are used to solve applied problems and to solve numerous test problems. Numerous experiments show that only for some test problems the existing methods allow finding optimal solutions. These methods, however, do not guarantee the best solutions in applied problems. Convex relaxation of multiextremal problems allows one to transform them to convex one-extremal problems. For some multiextremal problems such a transformation will be exact. For semi-definite optimization, this will be when the found matrix has rank one. For dual relaxation, it will happen when the duality gap is zero. In the general case, convex relaxation allows one to obtain only an estimate of the optimal solution. Various types of convex relaxation are used: semidefinite, Lagrange duality, exact quadratic regularization, reformulation-linearization technique. The most effective method of convex relaxation is the exact quadratic regularization. With its use, we obtain the widest class of multiextremal problems, for which convex relaxation will be exact. This is achieved by transformation of the original problem and displacement of the space. The efficiency of exact quadratic regularization is confirmed by numerous experiments for solving testing and applied multiextremal problems.
Authors and Affiliations
А. И. Косолап
Keywords
Related Articles
- EP ID EP626345
- DOI -
- Views 133
- Downloads 0
Алгоритм розрахунку об’єму адсорбційного теплового акумулятора для системи децентралізованого опалювання
Робота присвячена розробці ефективного алгоритму для розрахунку обсягу адсорбційного пристрою для акумулювання теплової енергії для децентралізованої системи опалення в приватному будинку. Пропонується наступна методика...
The numerical efficiency of the method of exact quadratic regularization
In this paper we consider methods for solving the multi-extreme problems in Euclidean finite-dimensional space and compare their efficiency at the solution of test problems. Such multi-extreme problems arise at mathemati...
FINDING OF EFFECTIVE TOPOLOGY OF SPACE STRUCTURES USING SEMIDEFINITE PROGRAMMING
The paper considers the problem of topology optimization of space truss-like structures. The proposed algorithm combines convex optimization problem with non-convex conditions. The purpose of the algorithm is to minimize...
The calculating the characteristics of vapor-liquid feed at the mobile control of rectification processes
The paper presents mathematical and algorithmic bases for calculating the static characteristics of the multicomponent rectification process, taking into account the mobile control actions of different intensity. Since m...
Algorithm to solve a problem of optimum separation of sets with additional couplings
Problems of manufacturing arrangement have been considered for more than a century. However, they are still topical. For instance, despite the fact that a number of models and techniques to solve discrete problems of arr...