Сonvex relaxation in multiextremal problems

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

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...

Download PDF file
  • EP ID EP626345
  • DOI -
  • Views 141
  • Downloads 0

How To Cite

А. И. Косолап (2018). Сonvex relaxation in multiextremal problems. Комп’ютерне моделювання: аналіз, управління, оптимізація, 1(1), 26-34. https://europub.co.uk/articles/-A-626345