Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier

New hybrid methods for approximating the Pareto frontier of the feasible set of criteria vectors in nonlinear multicriteria optimization problems with nonconvex Pareto frontiers are considered. Since the approximation of the Pareto frontier is an ill-posed problem, the methods are based on approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set having the same Pareto frontier as the original feasible set of criteria vectors. The EPH approximation also makes it possible to visualize the Pareto frontier and to estimate the quality of the approximation. In the methods proposed, the statistical estimation of the quality of the current EPH approximation is combined with its improvement based on a combination of random search, local optimization, adaptive compression of the search region, and genetic algorithms.     

Multicriteria Engineering Optimization Problems: Statement, Solution and Applications

The majority of engineering optimization problems (design, identification, design of controlled systems, optimization of large-scale systems, operational development of prototypes, and so on) are essentially multicriteria. The correct determination of the feasible solution set is a major challenge in engineering optimization problems. In order to construct the feasible solution set, a method called PSI (Parameter Space Investigation) has been created and successfully integrated into various fields of industry, science, and technology. Owing to the PSI method, it has become possible to formulate and solve a wide range of multicriteria optimization problems. In addition to giving an overview of the PSI method, this paper also describes the methods for approximation of the feasible and Pareto optimal solution sets, identification, decomposition, and aggregation of the large-scale systems.     

Study of an adaptive single-phase method for approximating the multidimensional Pareto frontier in nonlinear systems

The problem of approximating the Pareto frontier (nondominated frontier) of the feasible set of criteria vectors in nonlinear multicriteria optimization problems is considered. The problem is solved by approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set with the same Pareto frontier as the original feasible set of criteria vectors. An EPH approximation method is studied that is based on the statistical accuracy estimation of the current approximation and on adaptive supplement of a metric net whose EPH approximates the desired set. The convergence of the method is proved, estimates for the convergence rate are obtained, and the efficiency of the method is studied in the case of a compact feasible set and continuous criteria functions. It is shown that the convergence rate of the method with respect to the number k of iterations is no lower than $ o\left( {k^{{1 \mathord{\left/ {\vphantom {1 {\overline {dm} Y}}} \right. \kern-\nulldelimiterspace} {\overline {dm} Y}}} } \right) $ o\left( {k^{{1 \mathord{\left/ {\vphantom {1 {\overline {dm} Y}}} \right. \kern-\nulldelimiterspace} {\overline {dm} Y}}} } \right) , where $ \overline {dm} Y $ \overline {dm} Y is the upper metric dimension of the feasible set of criteria vectors.     

Comparison of two Pareto frontier approximations

A method for comparing two approximations to the multidimensional Pareto frontier in nonconvex nonlinear multicriteria optimization problems, namely, the inclusion functions method is described. A feature of the method is that Pareto frontier approximations are compared by computing and comparing inclusion functions that show which fraction of points of one Pareto frontier approximation is contained in the neighborhood of the Edgeworth-Pareto hull approximation for the other Pareto frontier.     

Convergence analysis of two-phase methods for approximating the Edgeworth-Pareto hull in nonlinear multicriteria optimization problems

The convergence of two-phase methods for approximating the Edgeworth-Pareto hull (EPH) in nonlinear multicriteria optimization problems is analyzed. The methods are based on the iterative supplement of the finite set of feasible criteria vectors (approximation basis) whose EPH approximates the desired set. A feature of two-phase methods is that the criteria images of randomly generated points of the decision space approach the Pareto frontier via local optimization of adaptively chosen convolutions of criteria. The convergence of two-phase methods is proved for both an abstract form of the algorithm and for a two-phase method based on the Germeier convolution.     

Nonadaptive methods for polyhedral approximation of the Edgeworth—Pareto hull using suboptimal coverings on the direction sphere

For multicriteria convex optimization problems, new nonadaptive methods are proposed for polyhedral approximation of the multidimensional Edgeworth-Pareto hull (EPH), which is a maximal set having the same Pareto frontier as the set of feasible criteria vectors. The methods are based on evaluating the support function of the EPH for a collection of directions generated by a suboptimal covering on the unit sphere. Such directions are constructed in advance by applying an asymptotically effective adaptive method for the polyhedral approximation of convex compact bodies, namely, by the estimate refinement method. Due to the a priori definition of the directions, the proposed EPH approximation procedure can easily be implemented with parallel computations. Moreover, the use of nonadaptive methods considerably simplifies the organization of EPH approximation on the Internet. Experiments with an applied problem (from 3 to 5 criteria) showed that the methods are fairly similar in characteristics to adaptive methods. Therefore, they can be used in parallel computations and on the Internet.     

Multicriteria optimization of convex dynamical systems

We suggest an approach to the solution of multicriteria optimization problems for dynamical systems described by differential inclusions. The investigation is restricted to dynamical systems with concave differential inclusion, for which the trajectory tube is convex. Such systems are typical of economic models. We assume that the criteria for the choice of the solution depend on the system state at a given terminal time and are related to it by sufficiently arbitrary functions. The approach is based on the interactive visualization of the Pareto frontier, which is carried out by approximating the reachable set of the dynamical system and the Edgeworth-Pareto set of feasible criteria vectors.     

Properties of a method for polyhedral approximation of the feasible criterion set in convex multiobjective problems

The paper describes new results in the field of multiobjective optimization techniques. The Interactive Decision Maps (IDM) technique is based on approximation of Feasible Criterion Set (FCS) and subsequent visualization of the Pareto frontier of FCS by interactive displaying the bi-criteria slices of FCS. The Estimation Refinement (ER) method is now the main method for approximating convex FCS in the framework of IDM. The properties of the ER method are studied. We prove that the number of facets of the approximation constructed by ER and the number of the support function calculations of an approximated set are asymptotically optimal. These results are important from the point of view of real-life applications of ER.     

Study of convergence rate and efficiency of two-phase methods for approximating the Edgeworth-Pareto hull

The convergence rate and efficiency of two-phase methods for approximating the Edgeworth-Pareto hull in nonlinear multicriteria optimization problems is studied. A feature of two-phase methods is that the criteria images of randomly generated points of the decision space approach the Pareto frontier via local optimization of adaptively chosen convolutions of criteria. It is shown that the convergence rate of two-phase methods is determined by the metric properties of the set of local extrema of criteria convolutions, specifically, by its upper metric dimension. The efficiency of two-phase methods is examined; i.e., they are compared with hypothetical optimal methods of the same class. It is shown that the efficiency of two-phase methods is determined by the ratio of the ?-entropy and ?-capacity for the set of local extrema of criteria convolutions.     

On a measure of quasistability of a certain vector linearly combinatorial Boolean problem

We consider a multicriteria problem of finding the Pareto set in the case when linear forms (functions) are minimized both on a set of permutations and on a set of Boolean vectors. We obtain a formula for the radius of that type of the problem stability (with respect to perturbations of parameters of the vector criterion) that guarantees the preservation of all Pareto optimal solutions of the initial problem and allows the occurrence of new ones.     

基于直觉模糊集的多准则模糊决策问题

提出了一种基于直觉模糊集处理模糊决策问题的新方法.该方法用直觉模糊集描述方案关于准则集的满足程度与不满足程度.而且该方法允许决策者给出准则对于模糊集“重要”的隶属度与非隶属度,即准则的权重也由直觉模糊集表示.这种方法为决策者做出最优决策提供了一种方便有效的方法.     

Arcwise cone-quasiconvex multicriteria optimization

The aim of this paper is to study the structure of the efficient sets within a special class of multicriteria optimization problems, involving objective functions which are continuous and arcwise quasiconvex with respect to a certain family of cones. In particular, it is shown that such a problem is Pareto reducible and its efficient outcome set is strongly contractible.     

Continuous extragradient method for a parametric multicriteria equilibrium programming problem

We consider a multicriteria equilibrium programming problem including, as special cases, the mathematical programming problem, the problem of finding a saddle point, the multicriteria problem of finding a Pareto point, the minimization problem with an equilibrium choice of an admissible set, etc. We suggest a continuous version of the extragradient method with prediction and analyze its convergence.     

A new multi-objective discrete robust optimization algorithm for engineering design

This paper proposes a novel multi-objective discrete robust optimization (MODRO) algorithm for design of engineering structures involving uncertainties. In the present MODRO procedure, grey relational analysis (GRA), coupled with principal component analysis (PCA), was used as a multicriteria decision making model for converting multiple conflicting objectives into one unified cost function. The optimization process was iterated using the successive Taguchi approach to avoid the limitation that the conventional Taguchi method fails to deal with a large number of design variables and design levels. The proposed method was first verified by a mathematical benchmark example and a ten-bar truss design problem; and then it was applied to a more sophisticated design case of full scale vehicle structure for crashworthiness criteria. The results showed that the algorithm is able to achieve an optimal design in a fairly efficient manner attributable to its integration with the multicriteria decision making model. Note that the optimal design can be directly used in practical applications without further design selection. In addition, it was found that the optimum is close to the corresponding Pareto frontier generated from the other approaches, such as the non-dominated sorting genetic algorithm II (NSGA-II), but can be more robust as a result of introduction of the Taguchi method. Due to its independence on metamodeling techniques, the proposed algorithm could be fairly promising for engineering design problems of high dimensionality.     

Constructing a Pareto front approximation for decision making

An approach to constructing a Pareto front approximation to computationally expensive multiobjective optimization problems is developed. The approximation is constructed as a sub-complex of a Delaunay triangulation of a finite set of Pareto optimal outcomes to the problem. The approach is based on the concept of inherent nondominance. Rules for checking the inherent nondominance of complexes are developed and applying the rules is demonstrated with examples. The quality of the approximation is quantified with error estimates. Due to its properties, the Pareto front approximation works as a surrogate to the original problem for decision making with interactive methods.     

A Proximal Point-Type Method for Multicriteria Optimization

In this paper, we present a proximal point algorithm for multicriteria optimization, by assuming an iterative process which uses a variable scalarization function. With respect to the convergence analysis, firstly we show that, for any sequence generated from our algorithm, each accumulation point is a Pareto critical point for the multiobjective function. A more significant novelty here is that our paper gets full convergence for quasi-convex functions. In the convex or pseudo-convex cases, we prove convergence to a weak Pareto optimal point. Another contribution is to consider a variant of our algorithm, obtaining the iterative step through an unconstrained subproblem. Then, we show that any sequence generated by this new algorithm attains a Pareto optimal point after a finite number of iterations under the assumption that the weak Pareto optimal set is weak sharp for the multiobjective problem.     

Study of hybrid methods for approximating the Edgeworth-Pareto hull in nonlinear multicriteria optimization problems

Methods for approximating the Edgeworth-Pareto hull (EPH) of the set of feasible criteria vectors in nonlinear multicriteria optimization problems are examined. The relative efficiency of two EPH approximation methods based on classical methods of searching for local extrema of convolutions of criteria is experimentally studied for a large-scale applied problem (with several hundred variables). A hybrid EPH approximation method combining classical and genetic approximation methods is considered.     

Multicriteria Planar Ordered Median Problems

In this paper, we deal with the determination of the entire set of Pareto solutions of location problems involving Q general criteria. These criteria include median, center, or centdian objective functions as particular instances. We characterize the set of Pareto solutions of all these multicriteria problems for any polyhedral gauge. An efficient algorithm is developed for the planar case and its complexity is established. Extensions to the nonconvex case are also considered. The proposed approach is more general than previously published approaches to multicriteria location problems.The research of the third and fourth authors was partially supported by Grants BFM2001-2378, BFM2001-4028, BFM2004-0909, and HA2003-0121.     

Uniform convergence and Pareto optimality

In this paper we consider the following problem: Is it possible to obtain a good approximation of the set of Pareto (Slater) solutions to a multicriteria optimization problem if the objective function is approximated by another sufficiently close function ?.