REDUCTION OF A CONSTRAINED OPTIMIZATION PROBLEM TO AN UNCONSTRAINED PROBLEM BY DOUBLE SPATIAL TRANSFORMATION

Abstract

The article considers a method of solving minimization and maximization problems with constraints using algorithms for solving optimization problems without constraints by constructing a mapping from a multidimensional space to a manifold formed by the constraints of an optimization problem. This construction is not convex, unlike the simplex, but nevertheless it is the complete set of combinations of vertices that form the space of options for the nonlinear optimization problem. Thus, using such a construction allows us to consider the problem without restrictions and use the principles of unconditional optimization, which compensates for possible computational difficulties due to the use of a manifold.

In fact, the article is the first stage in building a universal methodology for solving such problems, and in the process of analyzing and classifying modifications of this method, the requirements for the qualitative characteristics of such a solution method were described.

The reduction of a constrained optimization problem to an unconstrained problem by means of a double spatial transformation is carried out by operations that were more widespread in the field of computer graphics with bilinear transformations, which could be the reason for the underestimation of their effectiveness in nonlinear optimization problems. This gives a second breath to such a tool as the constrained optimization method by linear approximation (COBYLA), which was even quite recently classified as a secondary method, the efficiency of which was a priori less than the usual nonlinear optimization methods - Nelder-Mead, or gradient methods. Ambitious intentions to build a universal algorithm are initially considered on small-sized problems, which, however, do not represent simplified cases at all.

An example of such a mapping for a two-dimensional space and four linear constraints is presented, as well as an analysis of the practical potential of such an approach is performed for the problem of optimizing a quadratic objective function.

Keywords: conditional optimization; simplex; COBYLA; penalty parameter; multivariate; bilinear transformation; computational complexity; transformation of conditional optimization problems.