Solving a continuous nonlinear problem of optimal set partition with arrangement of subset centers in the case of a conv
- PDF / 176,008 Bytes
- 15 Pages / 595 x 842 pts (A4) Page_size
- 13 Downloads / 160 Views
SOLVING A CONTINUOUS NONLINEAR PROBLEM OF OPTIMAL SET PARTITION WITH ARRANGEMENT OF SUBSET CENTERS IN THE CASE OF A CONVEX OBJECTIVE FUNCTIONAL
In memory of N. Z. Shor
UDC 519.8
E. M. Kiselyova and M. S. Dunaichuk
A continuous nonlinear single-commodity problem of optimal partition of a set W in an n-measurable Euclidean space into disjoint subsets with arrangement of their centers is analyzed using equality and inequality constraints in the case of a convex objective functional. A method and algorithm are proposed to solve this problem. Keywords: infinite-dimensional mathematical programming, optimal set partition, nonsmooth optimization. INTRODUCTION The book [1] presents a mathematical theory of continuous linear problems of optimal partition of sets (OPS) from an n-dimensional Euclidean space, which are nonclassical problems of infinite-dimensional mathematical programming with Boolean variables. The solution methods for OPS problems, developed and theoretically justified in the monograph [1], underlie the algorithms that include Shor’s r-algorithm or its modifications. The theory proposed in the monograph is based on a unified approach that reduces (using, for example, the Lagrange functional) the original infinite-dimensional optimization problems to nonsmooth, as a rule, finite-dimensional optimization problems. To solve such problems numerically, modern efficient methods of nondifferentiable optimization (various modifications of the r-algorithm developed under the guidance of N. Z. Shor at the V. M. Glushkov Institute of Cybernetics, NAS of Ukraine) are used. Such an approach differs in that the original infinite-dimensional optimization problems can be solved analytically in an explicit form, the analytical expression including the parameters derived as the optimal solution of the above-mentioned auxiliary finite-dimensional optimization problems with nonsmooth objective functions. Continuous OPS models are of interest since a rather wide class of theoretical and practical optimization problems can be reduced to these models in mathematical formulation. Typical representatives of continuous OPS problems are infinite-dimensional transportation problems or (more general) infinite-dimensional problems of the arrangement of enterprises with simultaneous partition of a given region, continuously filled with customers, into domains of customers. Each domain is serviced by one enterprise in order to minimize transportation and industrial costs. The customers may be telephone subscribers, students, voters, points of an irrigated territory, patients to be diagnosed, etc. A need to consider infinite-dimensional arrangement problems arises in case of a large number of customers such as TV and radio subscribers, school regions, constituencies, etc. It becomes inexpedient to formulate an arrangement problem as a discrete mathematical model since problems of excessively high dimension are difficult to solve. There are also problems, reducible to OPS problems, such that the structure of their set to be divided into
Data Loading...
