ParEGO extensions for multi-objective optimization of expensive evaluation functions

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.     

Approximating the irregularly shaped Pareto front of multi-objective reservoir flood control operation problem

Decomposition based multi-objective evolutionary algorithm (MOEA/D) has been proved to be effective on multi-objective optimization problems. However, it fails to achieve satisfactory coverage and uniformity on problems with irregularly shaped Pareto fronts, like the reservoir flood control operation (RFCO) problem. To enhance the performance of MOEA/D on the real-world RFCO problem, a Pareto front relevant (PFR) decomposition method is developed in this paper. Different front the decomposition method in the original MOEA/D which is based on a unique reference point (i.e. the estimated ideal point), the PFR decomposition method uses a set of reference points which are uniformly sampled from the fitting model of the obtained Pareto front. As a result, the PFR decomposition method can provide more flexible adaptation to the Pareto front shapes of the target problems. Experimental studies on benchmark problems and typical RFCO problems at Ankang reservoir have illustrated that the proposed PFR decomposition method significantly improves the adaptivity of MOEA/D to the complex Pareto front shape of the RFCO problem and performs better both in terms of coverage and uniformity.     

不确定性对混合CVaR约束库存系统的影响

运用应用概率中的随机占优研究需求不确定性对混合CVaR约束库存系统最优订购量和最优利润的影响。引入刻画决策者风险态度的“风险偏好系数”,得到系统最优订购量和最优利润关于风险偏好系数的单调性。研究表明随机大需求总会导致系统较高的最优订购量和最优利润;在割准则序意义下,最优订购量可能随需求可变性的增加而增加也可能随需求可变性的增加而减少;在二阶随机占优且风险偏好系数大于等于1的情况下系统最优利润具有随机单调性,然而当风险偏好系数小于1时最优利润在二阶随机占优意义下的结论不一定成立,我们通过一个数值例子来说明。     

Sample average approximation of stochastic dominance constrained programs

In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of ${\mathcal{C}}$ -dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an ${\epsilon}$ -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.     

Guaranteeing approach to solving quantile optimization problems

This paper presents a numerical method for solving quantile optimization problems, i.e. stochastic programming problems in which the quantile of the distribution of an objective function is the criterion to be optimized.     

Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.     

Stochastic Programming with Multivariate Second Order Stochastic Dominance Constraints with Applications in Portfolio Optimization

In this paper we study optimization problems with multivariate stochastic dominance constraints where the underlying functions are not necessarily linear. These problems are important in multicriterion decision making, since each component of vectors can be interpreted as the uncertain outcome of a given criterion. We propose a penalization scheme for the multivariate second order stochastic dominance constraints. We solve the penalized problem by the level function methods, and a modified cutting plane method and compare them to the cutting surface method proposed in the literature. The proposed numerical schemes are applied to a generic budget allocation problem and a real world portfolio optimization problem.     

两类随机控制风险秩序的等价性分析

本文首先对比分析了两类风险秩序:随机控制秩序与对偶随机控制秩序.得到并证明了下述命题:(1)效用自由秩序等价于随机控制秩序;(2)畸变自由秩序等价于对偶随机控制秩序;(3)第一、第二阶随机控制秩序等价于第一、第二阶的对偶随机控制秩序,但对高于三阶的情况由实例说明不一定成立.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

On the relative efficiency of nth order and DARA stochastic dominance rules

It is known that third order stochastic dominance implies DARA dominance while no implications exist between higher orders and DARA dominance. A recent contribution points out that, with regard to the problem of determining lower and upper bounds for the price of a financial option, the DARA rule turns out to improve the stochastic dominance criteria of any order. In this paper the relative efficiency of the ordinary stochastic dominance and DARA criteria for alternatives with discrete distributions are compared, in order to see if the better performance of DARA criterion is also suitable for other practical applications. Moreover, the operational use of the stochastic dominance techniques for financial choices is deepened.     

Convexity and decomposition of mean-risk stochastic programs

Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk objective, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various mean-risk objective functions in addressing risk in stochastic programming models. We prove that the classical mean-variance criterion leads to computational intractability even in the simplest stochastic programs. On the other hand, a number of alternative mean-risk functions are shown to be computationally tractable using slight variants of existing stochastic programming decomposition algorithms. We propose decomposition-based parametric cutting plane algorithms to generate mean-risk efficient frontiers for two particular classes of mean-risk objectives.     

Operational asymptotic stochastic dominance

Levy (2016) proposes asymptotic first-degree stochastic dominance as a distribution ranking criterion for all non-satiable decision makers with infinite investment horizons. Given Levy’s setting, this paper defines and offers the equivalent distributional conditions for asymptotic second-degree stochastic dominance, as well as operational asymptotic first- and second-degree stochastic dominance. Interestingly, the operational asymptotic stochastic dominance provides a full rank over assets with lognormal returns and different means. Empirical applications show that our conditions can be readily implemented in practice.     

Multivariate robust second-order stochastic dominance and resulting risk-averse optimization

ABSTRACT

By utilizing a min-biaffine scalarization function, we define the multivariate robust second-order stochastic dominance relationship to flexibly compare two random vectors. We discuss the basic properties of the multivariate robust second-order stochastic dominance and relate it to the nonpositiveness of a functional which is continuous and subdifferentiable everywhere. We study a stochastic optimization problem with multivariate robust second-order stochastic dominance constraints and develop the necessary and sufficient conditions of optimality in the convex case. After specifying an ambiguity set based on moments information, we approximate the ambiguity set by a series of sets consisting of discrete distributions. Furthermore, we design a convex approximation to the proposed stochastic optimization problem with multivariate robust second-order stochastic dominance constraints and establish its qualitative stability under Kantorovich metric and pseudo metric, respectively. All these results lay a theoretical foundation for the modelling and solution of complex stochastic decision-making problems with multivariate robust second-order stochastic dominance constraints.     

Optimization with multivariate stochastic dominance constraints

We consider stochastic optimization problems where risk-aversion is expressed by a stochastic ordering constraint. The constraint requires that a random vector depending on our decisions stochastically dominates a given benchmark random vector. We identify a suitable multivariate stochastic order and describe its generator in terms of von Neumann–Morgenstern utility functions. We develop necessary and sufficient conditions of optimality and duality relations for optimization problems with this constraint. Assuming convexity we show that the Lagrange multipliers corresponding to dominance constraints are elements of the generator of this order, thus refining and generalizing earlier results for optimization under univariate stochastic dominance constraints. Furthermore, we obtain necessary conditions of optimality for non-convex problems under additional smoothness assumptions.     

Optimal models with maximizing probability of first achieving target value in the preceding stages

Decision makers often face the need of performance guarantee with some sufficiently high probability. Such problems can be modelled using a discrete time Markov decision process (MDP) with a probability criterion for the first achieving target value. The objective is to find a policy that maximizes the probability of the total discounted reward exceeding a target value in the preceding stages. We show that our formulation cannot be described by former models with standard criteria. We provide the properties of the objective functions, optimal value functions and optimal policies. An algorithm for computing the optimal policies for the finite horizon case is given. In this stochastic stopping model, we prove that there exists an optimal deterministic and stationary policy and the optimality equation has a unique solution. Using perturbation analysis, we approximate general models and prove the existence of e-optimal policy for finite state space. We give an example for the reliability of the satellite sy     

An experimental analysis of evolutionary heuristics for the biobjective traveling purchaser problem

Given a set of markets and a set of products to be purchased on those markets, the Biobjective Traveling Purchaser Problem (2TPP) consists in determining a route through a subset of markets to collect all products, minimizing the travel distance and the purchasing cost simultaneously. As its single objective version, the 2TPP is an NP-hard Combinatorial Optimization problem. Only one exact algorithm exists that can solve instances up to 100 markets and 200 products and one heuristic approach that can solve instances up to 500 markets and 200 products. Since the Transgenetic Algorithms (TAs) approach has shown to be very effective for the single objective version of the investigated problem, this paper examines the application of these algorithms to the 2TPP. TAs are evolutionary algorithms based on the endosymbiotic evolution and other interactions of the intracellular flow interactions. This paper has three main purposes: the first is the investigation of the viability of Multiobjective TAs to deal with the 2TPP, the second is to determine which characteristics are important for the hybridization between TAs and multiobjective evolutionary frameworks and the last is to compare the ability of multiobjective algorithms based only on Pareto dominance with those based on both decomposition and Pareto dominance to deal with the 2TPP. Two novel Transgenetic Multiobjective Algorithms are proposed. One is derived from the NSGA-II framework, named NSTA, and the other is derived from the MOEA/D framework, named MOTA/D. To analyze the performance of the proposed algorithms, they are compared with their classical counterparts. It is also the first time that NSGA-II and MOEA/D are applied to solve the 2TPP. The methods are validated in 365 uncapacitated instances of the TPPLib benchmark. The results demonstrate the superiority of MOTA/D and encourage further researches in the hybridization of Transgenetic Algorithms and Multiobjective Evolutionary Algorithms specially the ones based on decomposition.     

Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

On the convergence of the UOBYQA method

We analyze the convergence properties of Powell's UOBYQA method. A distinguished feature of the method is its use of two trust region radii. We first study the convergence of the method when the objective function is quadratic. We then prove that it is globally convergent for general objective functions when the second trust region radius ρ converges to zero. This gives a justification for the use of ρ as a stopping criterion. Finally, we show that a variant of this method is superlinearly convergent when the objective function is strictly convex at the solution.