MULTIOBJECTIVE PROBLEMS OF CONVEX GEOMETRY *

The birth of the theory of extremal problems is usually tied with the mythical Phoenician Princess Dido. Dido had to decide about the choice of a tract of land near the future city of Carthage Now it is customary to think that the decision by Dido was reduced to the isoperimetric problem of finding a figure of greatest area among those surrounded by a curve whose length is given. It is not excluded that Dido and her subjects solved the practical versions of the problem when the tower was to be located at the sea coast and part of the boundary coastline of the tract was somehow prescribed in advance. The foundation of Carthage is usually dated to the ninth century B.C.E. when there was no hint of the Euclidean geometry, the cadastral surveying was the job of harpedonaptae, and measuring the tracts of land was used in decision making. Rope-stretching around stakes leads to convex figures. The Dido problem has a unique solution in the class of convex figures provided that the fixed nonempty part of the boundary is a convex polygonal line.

Decision making has become a science in the twentieth century. The presence of many contradictory conditions and conflicting interests is the main particularity of the social situations under control of today. Management by objectives is an exceptional instance of the stock of rather complicated humanitarian problems of goal agreement which has no candidates for a unique solution.

The extremal problems of optimizing several parameters simultaneously are collected nowadays under the auspices of vector or multiobjective optimization. Search for control in these circumstances is multiple criteria decision making. The mathematical apparatus of these areas of research is not rather sophisticated at present. The today’s research deals mostly with the concept of Pareto optimality. Formally speaking, this implies the search of maximal elements of the set comprising the tuples of the values of all goals at each state; i.e., some vectors of a finite-dimensional arithmetic space endowed with the coordinatewise order. Problems with many objectives have become the topic of research rather recently and noticeably beyond mathematics, which explains the substantial gap between the levels of complexity and power of the mathematical tools available for single objective and multiple objective problems. This challenges the task of enriching the stock of vector optimization problems within the theoretical core of mathematics.

For the sake of simplicity, it stands to reason to start with the problems using the concept of Pareto optimality. The point is that such a problem is in fact equivalent to a parametric family of single objective problems which can be inspected by the classical methods. For instance, there is a curve joining the Legendre and Chebyshev polynomials which consists of the polynomials Pareto-optimal with respect to the uniform and mean square metrics. Clearly, some physical processes admit description in terms of vector optimization. For instance, we may treat the Leidenfrost effect of evaporation of a liquid drop in the spheroidal state. as the problem of simultaneous minimization of the surface area and the width of a drop of a given volume.

There area quite a few geometrically meaningful vector optimization problems whose solutions can be found explicitly to some extend in terms of conditions on surface area measures. As model examples we give explicit solutions of the external and internal Urysohn-type problems aggravated by the flattening condition or the requirement to optimize the convex hull of a few figures.

Technically speaking, everything reduces to the parametric programming of isoperimetric type problems with many subsidiary constraints. The available functional-analytical technique of settling the extremal problem of convex geometry is still insufficiently popular, and so its somewhat uncommon applications could be of use in bridging the gaps between the research within mathematics and the application of mathematics in the art and science of multiple criteria decision making.

Returning to Dido, let us assume that she had known the isoperimetric property of the circle and had been aware of the symmetrization processes that were elaborated in the nineteenth century. Would this knowledge be sufficient for Dido to choose the tract of land? Definitely, it would not. The real coastline may be rather ragged and craggy. The photo snaps of coastlines are exhibited as the most visual examples of fractality. From a theoretical standpoint, the free boundary in Dido’s planar problem may be nonrectifiable, and so the concept of area as the quantity to be optimized is itself rather ambiguous. Practically speaking, the situation in which Dido made her decision was not as primitive as it seems at the first glance. Choosing the tract of land, Dido had no right to trespass the territory under the control of the local sovereign. She had to choose the tract so as to encompass the camps of her subjects and satisfy some fortification requirements. Clearly, this generality is unavailable in the mathematical models known as the classical isoperimetric problem.

Dido’s problem inspiring our ancestors remains the same intellectual challenge as Kant’s starry heavens above and moral law within.

* This is an abstract of a talk at the Sobolev Institute of Mathematics on 20.03.2009. As regards technicalities see Dido’s Problem and Pareto Optimality Preprint No.217, Sobolev Institute (2009) + Optimization Online.

File translated from TEX by TTH, version 3.81.
On 12 Feb 2009, 18:50.