An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

On a class of quadratic programs

This paper considers a class of quadratic programs where the constraints ae linear and the objective is a product of two linear functions. Assuming the two linear factors to be non-negative, maximization and minimization cases are considered. Each case is analyzed with the help of a bicriteria linear program obtained by replacing the quadratic objective with the two linear functions. Global minimum (maximum) is attained at an efficient extreme point (efficient point) of the feasible set in the solution space and corresponds to an efficient extreme point (efficient point) of the feasible set in the bicriteria space. Utilizing this fact and certain other properties, two finite algorithms, including validations are given for solving the respective problems. Each of these, essentially, consists of solving a sequence of linear programs. Finally, a method is provided for relaxing the non-negativity assumption on the two linear factors of the objective function.     

The range of the efficient frontier in multiple objective linear programming

Because a rational decision maker should only select an efficient alternative in multiple criterion decision problems, the efficient frontier defined as the set of all efficient alternatives has become a central solution concept in multiple objective linear programming. Normally this set reduces the set of available alternatives of the underlying problem. There are several methods, mainly based on the simplex method, for computing the efficient frontier. This paper presents a quite different approach which uses a nonlinear parametric program, solved by Wolfe's algorithm, to determine the range of the efficient frontier.     

Nonlinear programming and stationary strategies in stochastic games

We show that an undiscounted stochastic game possesses optimal stationary strategies if and only if a global minimum with objective value zero can be found to an appropriate nonlinear program with linear constraints. This nonlinear program arises as a method for solving a certain bilinear system, satisfaction of which is also equivalent to finding a stationary optimal solution for the game. The objective function of the program is a nonnegatively valued quadric polynomial.This research was supported in part by the National Science Foundation under the grant #ECS-8503440. We wish to thank the referee for many helpful comments and in streamlining the presentation.     

A reduction algorithm for integer multiple objective linear programs

The efficient solutions of an integer multiple objective linear program are listed up in a lexicographic order. The lexicographic order is preserved by a new objective function which is constructed from the different objective functions of the linear program. Our algorithm finds also these efficient solutions which are not found by the usual parameter optimization.     

ON THE PROJECTION OF THE EFFICIENT SET AND POTENTIAL APPLICATIONS

Abstract

We study the efficient set X _E for a multiple objective linear program by using its projection into the linear space L spanned by the independent criteria. We show that in the orthogonally complementary space of L, the efficient points form a polyhedron, while in L an efficiency-equivalent polyhedron for the projection P(X _E ) of X _E can be constructed by algorithms of outer and inner approximation types. These algorithms can be also used for generating all extreme points of P(X _E ). Application to optimization over the efficient set for a multiple objective linear program is considered.     

Optimization over the efficient set

This paper deals with the problem of maximizing a function over the efficient set of a linear multiple objective program. The approach is to formulate a biobjective program with an appropriate efficient set. The penalty function approach is motivated by an auxiliary problem due to Benson.     

Error analysis for convex separable programs: Bounds on optimal and dual optimal solutions

Computable lower and upper bounds on the optimal and dual optimal solutions of a nonlinear, convex separable program are obtained from its piecewise linear approximation. They provide traditional error and sensitivity measures and are shown to be attainable for some problems. In addition, the bounds on the solution can be used to develop an efficient solution approach for such programs, and the dual bounds enable us to determine a subdivision interval which insures the objective function accuracy of a prespecified level. A generalization of the bounds to certain separable, but nonconvex, programs is given and some numerical examples are included.     

Solvability and stationarity for the optimal control of variational inequalities with point evaluations in the objective functional

Motivated by applications in economics and engineering, we consider the optimal control of a variational inequality with point evaluations of the state variable in the objective. This problem class constitutes a specific mathematical program with complementarity constraints (MPCC). In our context, the problem is posed in an adequate function space and the variational inequality involves second order linear elliptic partial differential operators. The necessary functional analytic framework complicates the derivation of stationarity conditions whereas the non-convex and non-differentiable nature of the problem challenges the design of an efficient solution algorithm. In this paper, we present a penalization and smoothing technique to derive first order type conditions related to C-stationarity in the associated Sobolev space setting. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Consolidating Maintenance Spares

The inventory of spare parts that a firm holds depends on the number of working parts and age of the equipment to be serviced, the expected failure rate associated with each working part, and the acceptable level of service. We model the problem of consolidation of spare parts to reduce overall inventory as an integer program with a nonlinear objective function. A linear reformulation of this model is obtained that helps solve some practical instances. A more compact implicit formulation is developed and solved using a specialized branch-and-price technique. We also demonstrate how this specialized branch-and-price technique is modified to devise a very effective heuristic procedure with a prespecifiable guarantee of quality of solution produced. This provides a practical and efficient methodology for maintenance spare consolidation.     

A Linearly-Implicit Energy-Preserving Algorithm for the Two-Dimensional Space-Fractional Nonlinear Schrödinger Equation Based on the SAV Approach

The main objective of this paper is to present an efficient structure-preserving scheme, which is based on the idea of the scalar auxiliary variable approach, for solving the two-dimensional space-fractional nonlinear Schrödinger equation. First, we reformulate the equation as an canonical Hamiltonian system, and obtain a new equivalent system via introducing a scalar variable. Then, we construct a semi-discrete energy-preserving scheme by using the Fourier pseudo-spectral method to discretize the equivalent system in space direction. After that, applying the Crank-Nicolson method on the temporal direction gives a linearly-implicit scheme in the fully-discrete version. As expected, the proposed scheme can preserve the energy exactly and more efficient in the sense that only decoupled equations with constant coefficients need to be solved at each time step. Finally, numerical experiments are provided to demonstrate the efficiency and conservation of the scheme.     

Computational Study of the Relationships Between Feasible and Efficient Sets and an Approximation

The computational difficulty of obtaining the efficient set in multi-objective programming, specially in nonlinear problems, suggest the need of considering an approximation approach to this problem. In this paper, we provide the computational results of the relationships between an approximation to the efficient set and the feasible and efficient sets. Random problem generation is considered for different sizes of the feasible set and we study the implications with respect to the number of objective functions and various kinds of objective functions. Computational experience with this approximation suggests that we obtain a substantial improvement when it increases the number of objective functions.     

Existence and Boundedness of Solutions in Infinite-Dimensional Vector Optimization Problems

This work focuses on the nonemptiness and boundedness of the sets of efficient and weak efficient solutions of a vector optimization problem, where the decision space is a normed space and the image space is a locally convex Hausdorff topological linear space. By studying certain boundedness and coercivity concepts of vector-valued functions and via an asymptotic analysis, we extend to this kind of problems some well-known existence and boundedness results for efficient and weak efficient solutions of multiobjective optimization problems with Pareto or polyhedral orderings. Some of these results are proved under weaker assumptions.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

集值映射最优化问题的严有效解集的连通性及应用

本文对集值映射最优化问题引入严有效解的概念．证明了当目标函数为锥类凸的集值映射时,其目标空间里的严有效点集是连通的;若目标函数为锥凸的集值映射时,其严有效解集也是连通的．作为应用,讨论了超有效解集的连通性．     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

An algorithm for the mixed-integer nonlinear bilevel programming problem

The bilevel programming problem (BLPP) is a two-person nonzero sum game in which play is sequential and cooperation is not permitted. In this paper, we examine a class of BLPPs where the leader controls a set of continuous and discrete variables and tries to minimize a convex nonlinear objective function. The follower's objective function is a convex quadratic in a continuous decision space. All constraints are assumed to be linear. A branch and bound algorithm is developed that finds global optima. The main purpose of this paper is to identify efficient branching rules, and to determine the computational burden of the numeric procedures. Extensive test results are reported. We close by showing that it is not readily possible to extend the algorithm to the more general case involving integer follower variables.This work was supported by a grant from the Advanced Research Program of the Texas Higher Education Coordinating Board.     

The homotopy perturbation method applied to the nonlinear fractional Kolmogorov–Petrovskii–Piskunov equations

The fractional derivatives in the sense of Caputo, and the homotopy perturbation method are used to construct approximate solutions for nonlinear Kolmogorov–Petrovskii–Piskunov (KPP) equations with respect to time and space fractional derivatives. Also, we apply complex transformation to convert a time and space fractional nonlinear KPP equation to an ordinary differential equation and use the homotopy perturbation method to calculate the approximate solution. This method is efficient and powerful in solving wide classes of nonlinear evolution fractional order equations.     

Galerkin-Legendre spectral schemes for nonlinear space fractional Schrödinger equation

In the paper, we first propose a Crank-Nicolson Galerkin-Legendre (CN-GL) spectral scheme for the one-dimensional nonlinear space fractional Schrödinger equation. Convergence with spectral accuracy is proved for the spectral approximation. Further, a Crank-Nicolson ADI Galerkin-Legendre spectral method for the two-dimensional nonlinear space fractional Schrödinger equation is developed. The proposed schemes are shown to be efficient with second-order accuracy in time and spectral accuracy in space which are higher than some recently studied methods. Moreover, some numerical results are demonstrated to justify the theoretical analysis.