Truncated policy iteration methods

Policy iteration methods are important but often computationally expensive approaches for solving certain stochastic optimization problems. Modified policy iteration methods have been proposed to reduce the storage and computational burden. The asymptotic speed-of-convergence of such methods is, however, not well understood. In this paper we show how modified policy iteration methods may be constructed to achieve a preassigned rate-of-convergence. Our analysis provides a framework for analyzing the local behavior of such methods and provides impetus for perhaps more computationally efficient procedures than currently exist.     

A robust data envelopment analysis model with different scenarios

Input and output data, under uncertainty, must be taken into account as an essential part of data envelopment analysis (DEA) models in practice. Many researchers have dealt with this kind of problem using fuzzy approaches, DEA models with interval data or probabilistic models. This paper presents an approach to scenario-based robust optimization for conventional DEA models. To consider the uncertainty in DEA models, different scenarios are formulated with a specified probability for input and output data instead of using point estimates. The robust DEA model proposed is aimed at ranking decision-making units (DMUs) based on their sensitivity analysis within the given set of scenarios, considering both feasibility and optimality factors in the objective function. The model is based on the technique proposed by Mulvey et al. (1995) for solving stochastic optimization problems. The effect of DMUs on the product possibility set is calculated using the Monte Carlo method in order to extract weights for feasibility and optimality factors in the goal programming model. The approach proposed is illustrated and verified by a case study of an engineering company.     

A genetic algorithm based augmented Lagrangian method for constrained optimization

Among the penalty based approaches for constrained optimization, augmented Lagrangian (AL) methods are better in at least three ways: (i) they have theoretical convergence properties, (ii) they distort the original objective function minimally, thereby providing a better function landscape for search, and (iii) they can result in computing optimal Lagrange multiplier for each constraint as a by-product. Instead of keeping a constant penalty parameter throughout the optimization process, these algorithms update the parameters (called multipliers) adaptively so that the corresponding penalized function dynamically changes its optimum from the unconstrained minimum point to the constrained minimum point with iterations. However, the flip side of these algorithms is that the overall algorithm requires a serial application of a number of unconstrained optimization tasks, a process that is usually time-consuming and tend to be computationally expensive. In this paper, we devise a genetic algorithm based parameter update strategy to a particular AL method. The proposed strategy updates critical parameters in an adaptive manner based on population statistics. Occasionally, a classical optimization method is used to improve the GA-obtained solution, thereby providing the resulting hybrid procedure its theoretical convergence property. The GAAL method is applied to a number of constrained test problems taken from the evolutionary algorithms (EAs) literature. The number of function evaluations required by GAAL in most problems is found to be smaller than that needed by a number of existing evolutionary based constraint handling methods. GAAL method is found to be accurate, computationally fast, and reliable over multiple runs. Besides solving the problems, the proposed GAAL method is also able to find the optimal Lagrange multiplier associated with each constraint for the test problems as an added benefit??a matter that is important for a sensitivity analysis of the obtained optimized solution, but has not yet been paid adequate attention in the past evolutionary constrained optimization studies.     

A honey-bee mating optimization algorithm for educational timetabling problems

In this work, we propose a variant of the honey-bee mating optimization algorithm for solving educational timetabling problems. The honey-bee algorithm is a nature inspired algorithm which simulates the process of real honey-bees mating. The performance of the proposed algorithm is tested over two benchmark problems; exam (Carter’s un-capacitated datasets) and course (Socha datasets) timetabling problems. We chose these two datasets as they have been widely studied in the literature and we would also like to evaluate our algorithm across two different, yet related, domains. Results demonstrate that the performance of the honey-bee mating optimization algorithm is comparable with the results of other approaches in the scientific literature. Indeed, the proposed approach obtains best results compared with other approaches on some instances, indicating that the honey-bee mating optimization algorithm is a promising approach in solving educational timetabling problems.     

A novel method for solving linear programming problems with symmetric trapezoidal fuzzy numbers

Linear programming (LP) is a widely used optimization method for solving real-life problems because of its efficiency. Although precise data are fundamentally indispensable in conventional LP problems, the observed values of the data in real-life problems are often imprecise. Fuzzy sets theory has been extensively used to represent imprecise data in LP by formalizing the inaccuracies inherent in human decision-making. The fuzzy LP (FLP) models in the literature generally either incorporate the imprecisions related to the coefficients of the objective function, the values of the right-hand-side, and/or the elements of the coefficient matrix. We propose a new method for solving FLP problems in which the coefficients of the objective function and the values of the right-hand-side are represented by symmetric trapezoidal fuzzy numbers while the elements of the coefficient matrix are represented by real numbers. We convert the FLP problem into an equivalent crisp LP problem and solve the crisp problem with the standard primal simplex method. We show that the method proposed in this study is simpler and computationally more efficient than two competing FLP methods commonly used in the literature.     

On generalized geometric programming problems with non-positive variables

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Some exponential-based decomposition methods have been developed for solving global optimization of GGP problems. However, the use of logarithmic/exponential transformations restricts these methods to handle the problems with strictly positive variables. This paper proposes a technique for treating non-positive variables with integer powers in GGP problems. By means of variable transformation, the GGP problem with non-positive variables can be equivalently solved with another one having positive variables. In addition, we present some computationally efficient convexification rules for signomial terms to enhance the efficiency of the optimization approach. Numerical examples are presented to demonstrate the usefulness of the proposed method in GGP problems with non-positive variables.     

Using multi-objective evolutionary algorithms for single-objective optimization

In recent decades, several multi-objective evolutionary algorithms have been successfully applied to a wide variety of multi-objective optimization problems. Along the way, several new concepts, paradigms and methods have emerged. Additionally, some authors have claimed that the application of multi-objective approaches might be useful even in single-objective optimization. Thus, several guidelines for solving single-objective optimization problems using multi-objective methods have been proposed. This paper offers a survey of the main methods that allow the use of multi-objective schemes for single-objective optimization. In addition, several open topics and some possible paths of future work in this area are identified.     

GOSAC: global optimization with surrogate approximation of constraints

We introduce GOSAC, a global optimization algorithm for problems with computationally expensive black-box constraints and computationally cheap objective functions. The variables may be continuous, integer, or mixed-integer. GOSAC uses a two-phase optimization approach. The first phase aims at finding a feasible point by solving a multi-objective optimization problem in which the constraints are minimized simultaneously. The second phase aims at improving the feasible solution. In both phases, we use cubic radial basis function surrogate models to approximate the computationally expensive constraints. We iteratively select sample points by minimizing the computationally cheap objective function subject to the constraint function approximations. We assess GOSAC’s efficiency on computationally cheap test problems with integer, mixed-integer, and continuous variables and two environmental applications. We compare GOSAC to NOMAD and a genetic algorithm (GA). The results of the numerical experiments show that for a given budget of allowed expensive constraint evaluations, GOSAC finds better feasible solutions more efficiently than NOMAD and GA for most benchmark problems and both applications. GOSAC finds feasible solutions with a higher probability than NOMAD and GOSAC.     

Zero weights and non-zero slacks: Different solutions to the same problem

This paper re-assesses three independently developed approaches that are aimed at solving the problem of zero-weights or non-zero slacks in Data Envelopment Analysis (DEA). The methods are weights restricted, non-radial and extended facet DEA models. Weights restricted DEA models are dual to envelopment DEA models with restrictions on the dual variables (DEA weights) aimed at avoiding zero values for those weights; non-radial DEA models are envelopment models which avoid non-zero slacks in the input-output constraints. Finally, extended facet DEA models recognize that only projections on facets of full dimension correspond to well defined rates of substitution/transformation between all inputs/outputs which in turn correspond to non-zero weights in the multiplier version of the DEA model. We demonstrate how these methods are equivalent, not only in their aim but also in the solutions they yield. In addition, we show that the aforementioned methods modify the production frontier by extending existing facets or creating unobserved facets. Further we propose a new approach that uses weight restrictions to extend existing facets. This approach has some advantages in computational terms, because extended facet models normally make use of mixed integer programming models, which are computationally demanding.     

A primal-dual approach to inexact subgradient methods

For optimization problems with computationally demanding objective functions and subgradients, inexact subgradient methods (IXS) have been introduced by using successive approximation schemes within subgradient optimization methods (Au et al., 1994). In this paper, we develop alternative solution procedures when the primal-dual information of IXS is utilized. This approach is especially useful when the projection operation onto the feasible set is difficult. We also demonstrate its applicability to stochastic linear programs.     

A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs

Progressive Hedging (PH) is a well-known algorithm for solving multi-stage stochastic convex optimization problems. Most previous extensions of PH for mixed-integer stochastic programs have been implemented without convergence guarantees. In this paper, we present a new framework that shows how PH can be utilized while guaranteeing convergence to globally optimal solutions of mixed-integer stochastic convex programs. We demonstrate the effectiveness of the proposed framework through computational experiments.     

SO-I: a surrogate model algorithm for expensive nonlinear integer programming problems including global optimization applications

This paper presents the surrogate model based algorithm SO-I for solving purely integer optimization problems that have computationally expensive black-box objective functions and that may have computationally expensive constraints. The algorithm was developed for solving global optimization problems, meaning that the relaxed optimization problems have many local optima. However, the method is also shown to perform well on many local optimization problems, and problems with linear objective functions. The performance of SO-I, a genetic algorithm, Nonsmooth Optimization by Mesh Adaptive Direct Search (NOMAD), SO-MI (Müller et al. in Comput Oper Res 40(5):1383–1400, 2013), variable neighborhood search, and a version of SO-I that only uses a local search has been compared on 17 test problems from the literature, and on eight realizations of two application problems. One application problem relates to hydropower generation, and the other one to throughput maximization. The numerical results show that SO-I finds good solutions most efficiently. Moreover, as opposed to SO-MI, SO-I is able to find feasible points by employing a first optimization phase that aims at minimizing a constraint violation function. A feasible user-supplied point is not necessary.     

Embedding evolutionary strategy in ordinal optimization for hard optimization problems

This work proposes a method for embedding evolutionary strategy (ES) in ordinal optimization (OO), abbreviated as ESOO, for solving real-time hard optimization problems with time-consuming evaluation of the objective function and a huge discrete solution space. Firstly, an approximate model that is based on a radial basis function (RBF) network is utilized to evaluate approximately the objective value of a solution. Secondly, ES associated with the approximate model is applied to generate a representative subset from a huge discrete solution space. Finally, the optimal computing budget allocation (OCBA) technique is adopted to select the best solution in the representative subset as the obtained “good enough” solution. The proposed method is applied to a hotel booking limits (HBL) problem, which is formulated as a stochastic combinatorial optimization problem with a huge discrete solution space. The good enough booking limits, obtained by the proposed method, have promising solution quality, and the computational efficiency of the method makes it suitable for real-time applications. To demonstrate the computational efficiency of the proposed method and the quality of the obtained solution, it is compared with two competing methods – the canonical ES and the genetic algorithm (GA). Test results demonstrate that the proposed approach greatly outperforms the canonical ES and GA.     

Improved scatter search for the global optimization of computationally expensive dynamic models

A new algorithm for global optimization of costly nonlinear continuous problems is presented in this paper. The algorithm is based on the scatter search metaheuristic, which has recently proved to be efficient for solving combinatorial and nonlinear optimization problems. A kriging-based prediction method has been coupled to the main optimization routine in order to discard the evaluation of solutions that are not likely to provide high quality function values. This makes the algorithm suitable for the optimization of computationally costly problems, as is illustrated in its application to two benchmark problems and its comparison with other algorithms.     

Integrated data envelopment analysis: Global vs. local optimum

Chiou et al. (2010) (A joint measurement of efficiency and effectiveness for non-storable commodities: integrated data envelopment analysis approaches. European Journal of Operational Research 201, 477–489) propose an integrated data envelopment analysis model in measuring decision making units (DMUs) that have a two-stage internal network structure with multiple inputs, outputs, and consumptions. They claim that any optimal solutions determined by their DEA model are a global optimum, not a local optimum. We show that such a conclusion is a false statement due to their misuse of Hessian matrix in examining the concavity of the objective function, and their DEA model is actually a non-convex optimization problem. As a result, their DEA model is unusable in practice due to a lack of efficient algorithm for this particular non-convex DEA model. We further show that Chiou et al.’s (2010) model is a special case of a well-known two-stage network DEA model, and it can be transformed into a parametric linear program for which an approximate global optimal solution can be obtained by solving a sequence of linear programs in combination with a simple search algorithm.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).     

A bi-objective weighted model for improving the discrimination power in MCDEA

Lack of discrimination power and poor weight dispersion remain major issues in Data Envelopment Analysis (DEA). Since the initial multiple criteria DEA (MCDEA) model developed in the late 1990s, only goal programming approaches; that is, the GPDEA-CCR and GPDEA-BCC were introduced for solving the said problems in a multi-objective framework. We found GPDEA models to be invalid and demonstrate that our proposed bi-objective multiple criteria DEA (BiO-MCDEA) outperforms the GPDEA models in the aspects of discrimination power and weight dispersion, as well as requiring less computational codes. An application of energy dependency among 25 European Union member countries is further used to describe the efficacy of our approach.     

Nonlinear conjugate gradient methods with structured secant condition for nonlinear least squares problems

In this paper, we deal with conjugate gradient methods for solving nonlinear least squares problems. Several Newton-like methods have been studied for solving nonlinear least squares problems, which include the Gauss-Newton method, the Levenberg-Marquardt method and the structured quasi-Newton methods. On the other hand, conjugate gradient methods are appealing for general large-scale nonlinear optimization problems. By combining the structured secant condition and the idea of Dai and Liao (2001) [20], the present paper proposes conjugate gradient methods that make use of the structure of the Hessian of the objective function of nonlinear least squares problems. The proposed methods are shown to be globally convergent under some assumptions. Finally, some numerical results are given.     

Bayesian methods in global optimization

This paper reviews methods which have been proposed for solving global optimization problems in the framework of the Bayesian paradigm.     

Applying integrated DEA/AHP to evaluate the economic performance of local governments in China

This paper aims at integrating data envelopment analysis (DEA) and analytic hierarchy process (AHP) to evaluate the economic development achieved by local governments in China. Since most similar evaluations are multi-objection problems, which both DEA and AHP are capable of solving, the integration of these two approaches is shown to be even more powerful. The proposed integrated DEA/AHP model can evaluate and rank different alternatives. In addition, a time-scale comparison of the economic performances of local governments in China was carried out using the malmquist productivity index (MPI), which indicated that there is a trend of economic growth. However, empirical results indicate that after discounting the advantages of location and political connections, the east district provinces of China do not have superior economic performance or a better MPI index, as compared with other districts. This result is contrary to our original hypothesis.