С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 141
- Downloads 0
Numerical-analytical conception of decisions of the applied tasks based on charts of an increase order of exactness
The article is sanctified to the distributed modeling of visualization of decisions vectors of the applied tasks based on charts of an increase order of exactness. Higher acceleration of computation compared with the fin...
Stress-strain state of a three-layer circular plate connected with a complex base
In our time, compositional, including three-layer structural elements have found wide application in construction and mechanical engineering. This calls for the creation of appropriate mathematical models and methods for...
Discrete interpolation method for modeling multiparametric processes, systems and environments
The design of complex technical objects, the modeling of the predicted state of multiparametric systems and environments, for example, ecological, energy, climatic, hydrological, geomorphological, geological systems, is...
Математическое моделирование сборки составной оболочки
Сборка является заключительным этапом изготовления машин, аккумулирующим накопленные на предшествующих этапах несовершенства. Для составной оболоч- ки многоступенчатых ракет контейнерного базирования существующий уровень...
CLUSTER ANALYSIS APPROACHES TO ASSESSING THE FINANCIAL AND ECONOMIC ACTIVITIES OF ENTERPRISES
The article is devoted to the financial and economic assessment of the state of road transport enterprises in Ukraine through the use of multidimensional statistical cluster analysis. The article solved the task of analy...