Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

A numerical method for hybrid optimal control based on dynamic programming

This contribution extends a numerical method for solving optimal control problems by dynamic programming to a class of hybrid dynamic systems with autonomous as well as controlled switching. The value function of the hybrid control system is calculated based on a full discretization of the state and input spaces. A bound for the error due to discretization is obtained from modeling the error as perturbation of the continuous dynamics and the cost terms. It is shown that the bound approaches zero and that the value function of the discretized variant converges to the value function of the original problem if the discretization parameters go to zero. The performance of a numerical scheme exploiting the discretized system is illustrated for two different examples treated previously in literature.     

The optimization technique for solving a class of non-differentiable programming based on neural network method

In this paper, the optimization techniques for solving a class of non-differentiable optimization problems are investigated. The non-differentiable programming is transformed into an equivalent or approximating differentiable programming. Based on Karush–Kuhn–Tucker optimality conditions and projection method, a neural network model is constructed. The proposed neural network is proved to be globally stable in the sense of Lyapunov and can obtain an exact or approximating optimal solution of the original optimization problem. An example shows the effectiveness of the proposed optimization techniques.     

Solving semi-infinite programs by smoothing projected gradient method

In this paper, we study a semi-infinite programming (SIP) problem with a convex set constraint. Using the value function of the lower level problem, we reformulate SIP problem as a nonsmooth optimization problem. Using the theory of nonsmooth Lagrange multiplier rules and Danskin’s theorem, we present constraint qualifications and necessary optimality conditions. We propose a new numerical method for solving the problem. The novelty of our numerical method is to use the integral entropy function to approximate the value function and then solve SIP by the smoothing projected gradient method. Moreover we study the relationships between the approximating problems and the original SIP problem. We derive error bounds between the integral entropy function and the value function, and between locally optimal solutions of the smoothing problem and those for the original problem. Using certain second order sufficient conditions, we derive some estimates for locally optimal solutions of problem. Numerical experiments show that the algorithm is efficient for solving SIP.     

Gap-free computation of Pareto-points by quadratic scalarizations

In multicriteria optimization, several objective functions have to be minimized simultaneously. For this kind of problem, approximations to the whole solution set are of particular importance to decision makers. Usually, approximating this set involves solving a family of parameterized optimization problems. It is the aim of this paper to argue in favour of parameterized quadratic objective functions, in contrast to the standard weighting approach in which parameterized linear objective functions are used. These arguments will rest on the favourable numerical properties of these quadratic scalarizations, which will be investigated in detail. Moreover, it will be shown which parameter sets can be used to recover all solutions of an original multiobjective problem where the ordering in the image space is induced by an arbitrary convex cone.     

An Algorithm for the Global Optimization of a Class of Continuous Minimax Problems

We propose an algorithm for the global optimization of continuous minimax problems involving polynomials. The method can be described as a discretization approach to the well known semi-infinite formulation of the problem. We proceed by approximating the infinite number of constraints using tools and techniques from semidefinite programming. We then show that, under appropriate conditions, the SDP approximation converges to the globally optimal solution of the problem. We also discuss the numerical performance of the method on some test problems. Financial support of EPSRC Grant GR/T02560/01 gratefully acknowledged.     

求解含平衡约束数学规划的熵函数法

提出求解含平衡约束数学规划问题(简记为MPEC问题)的熵函数法，在将原问题等价改写为单层非光滑优化问题的基础上，通过熵函数逼近，给出求解MPEC问题的序列光滑优化方法，证明了熵函数逼近问题解的存在性和算法的全局收敛性，数值算例表明了算法的有效性。     

Global optimization of robust chance constrained problems

We propose a stochastic algorithm for the global optimization of chance constrained problems. We assume that the probability measure with which the constraints are evaluated is known only through its moments. The algorithm proceeds in two phases. In the first phase the probability distribution is (coarsely) discretized and solved to global optimality using a stochastic algorithm. We only assume that the stochastic algorithm exhibits a weak* convergence to a probability measure assigning all its mass to the discretized problem. A diffusion process is derived that has this convergence property. In the second phase, the discretization is improved by solving another nonlinear programming problem. It is shown that the algorithm converges to the solution of the original problem. We discuss the numerical performance of the algorithm and its application to process design.     

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.     

Optimization with Variable Sets of Constraints and an Application to Truss Design

We discuss the minimization of a continuous function on a subset of Rⁿ subject to a finite set of continuous constraints. At each point, a given set-valued map determines the subset of constraints considered at this point. Such problems arise e.g. in the design of engineering structures.After a brief discussion on the existence of solutions, the numerical treatment of the problem is considered. It is briefly motivated why standard approaches generally fail. A method is proposed approximating the original problem by a standard one depending on a parameter. It is proved that by choosing this parameter large enough, each solution to the approximating problem is a solution to the original one. In many applications, an upper bound for this parameter can be computed, thus yielding the equivalence of the original problem to a standard optimization problem.The proposed method is applied to the problem of optimally designing a loaded truss subject to local buckling conditions. To our knowledge this problem has not been solved before. A numerical example of reasonable size shows the proposed methodology to work well.     

Convergence of algorithms for perturbed optimization problems

Infinite-dimensional optimization problems occur in various applications such as optimal control problems and parameter identification problems. If these problems are solved numerically the methods require a discretization which can be viewed as a perturbation of the data of the optimization problem. In this case the expected convergence behavior of the numerical method used to solve the problem does not only depend on the discretized problem but also on the original one. Algorithms which are analyzed include the gradient projection method, conditional gradient method, Newton's method and quasi-Newton methods for unconstrained and constrained problems with simple constraints.     

NUMERICAL SOLUTIONS OF PARABOLIC PROBLEMS ON UNBOUNDED 3-D SPATIAL DOMAIN

In this paper,the numerical solutions of heat equation on 3-D unbounded spatial do-main are considered. n artificial boundary Γ is introduced to finite the computationaldomain.On the artificial boundary Γ,the exact boundary condition and a series of approx-imating boundary conditions are derived,which are called artificial boundary conditions.By the exact or approximating boundary condition on the artificial boundary,the originalproblem is reduced to an initial-boundary value problem on the bounded computationaldomain,which is equivalent or approximating to the original problem.The finite differencemethod and finite element method are used to solve the reduced problems on the finitecomputational domain.The numerical results demonstrate that the method given in thispaper is effective and feasible.     

Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems

Discretization algorithms for semiinfinite minimax problems replace the original problem, containing an infinite number of functions, by an approximation involving a finite number, and then solve the resulting approximate problem. The approximation gives rise to a discretization error, and suboptimal solution of the approximate problem gives rise to an optimization error. Accounting for both discretization and optimization errors, we determine the rate of convergence of discretization algorithms, as a computing budget tends to infinity. We find that the rate of convergence depends on the class of optimization algorithms used to solve the approximate problem as well as the policy for selecting discretization level and number of optimization iterations. We construct optimal policies that achieve the best possible rate of convergence and find that, under certain circumstances, the better rate is obtained by inexpensive gradient methods.     

Numerical methods for controlled and uncontrolled multiplexing and queueing systems

We deal with a very useful numerical method for both controlled and uncontrolled queuing and multiplexing type systems. The basic idea starts with a heavy traffic approximation, but it is shown that the results are very good even when working far from the heavy traffic regime. The underlying numerical method is a version of what is known as the Markov chain approximation method. It is a powerful methodology for controlled and uncontrolled stochastic systems, which can be approximated by diffusion or reflected diffusion type systems, and has been used with success on many other problems in stochastic control. We give a complete development of the relevant details, with an emphasis on multiplexing and particular queueing systems. The approximating process is a controlled or uncontrolled Markov chain which retains certain essential features of the original problem. This problem is generally substantially simpler than the original physical problem, and there are associated convergence theorems. The non-classical associated ergodic cost problem is derived, and put into a form such that reliable and good numerical algorithms, based on multigrid type ideas, can be used. Data for both controlled and uncontrolled problems shows the value of the method.Supported by ARO contract DAAL-03-92-G-0115, AFOSR contract F49620-92-J-0081, and DARPA contract AFOSR-91-0375.Formerly at Brown University. Supported by DARPA contract AFOSR-91-0375.     

Optimization technique in solving laminar boundary layer problems with temperature dependent viscosity

In this paper, a novel numerical method is proposed to solve specific third order ODE on semi-infinite interval. These kinds of problems often occur in laminar boundary layer with temperature dependent viscosity. Runge-Kutta method incorporating with optimization techniques is used to solve the problem. First, the semi-infinite interval is transformed into a finite interval. Second, by converting the boundary value problem, with some initial and distributed unknowns, into an optimization problem, solving the original problem is limited to solving a multiobjective optimization problem. Third, we use shooting-Newton’s method for solving this optimization problem. It is shown that the Falkner-Skan problem with constant surface temperature, that arise during the solution for the laminar forced convection heat transfer from wedges to flow, can be solved accurately and simultaneously by this strategy. Numerical results for different values of wedge angle and Prandtl number are presented, which are in good agreement with some of the successful provided solutions in the literature.     

Modelling the discretization error of initial value problems using the Wishart distribution

This paper presents a new discretization error quantification method for the numerical integration of ordinary differential equations. The error is modelled by using the Wishart distribution, which enables us to capture the correlation between variables. Error quantification is achieved by solving an optimization problem under the order constraints for the covariance matrices. An algorithm for the optimization problem is also established in a slightly broader context.     

On the numerical solution of certain boundary control problems for vibrating media in one space-dimension

This paper is concerned with the numerical solution of control problems which consist of minimizing certain quadratic functionals depending on control functions in L ₂[0,1] for some given time T > 0 and bounded with respect to the maximum norm. These control functions act upon the boundary conditions of a vibrating system in one space-dimension which is governed by a wave equation of spatial order 2n They are to be chosen in such a way that a given initial state of vibration at time zero is transferred into the state of rest. This requirement can be expressed by an infinite system of moment equations to be satisfied by the control functions

The control problem is approximated by replacing this infinite system by finitely many, say N, equations (truncation) and by choosing piecewise constant functions as controls (discretization). The resulting problem is a quadratic optimization problem which is solved very efficiently by a multiplier method

Convergence of the solutions of the approximating problems to the solution of the control problem, as N tends to infinity and the discretization is infinitely refined, is shown under mild assumptions. Numerical results are presented for a vibrating beam     

Approximation of a population dynamics model by parabolic regularization

The basic linear model for describing an age structured population spreading in a limited habitat is considered with the purpose of investigating an approximation procedure based on parabolic regularization. In fact, a viscosity model is introduced by considering an appropriate approximating regularized parabolic problem and it is proved that the sequence of the approximating solutions tends to the solution to the original problem. The advantage of this approach is that it leads to the numerical solution of a parabolic problem that has more stable solutions than the hyperbolic‐parabolic original problem and avoids the restrictions (compatibility conditions) needed to treat the latter. Moreover, for the solution of the approximating problem, it is possible to take advantage of established software packages dedicated to parabolic problems. Some examples of the approach are provided using COMSOL Multiphysics. Copyright © 2012 John Wiley & Sons, Ltd.     

Stable barrier-projection and barrier-Newton methods in linear programming

The present paper is devoted to the application of the space transformation techniques for solving linear programming problems. By using a surjective mapping the original constrained optimization problem is transformed to a problem in a new space with only equality constraints. For the numerical solution of the latter problem the stable version of the gradient-projection and Newton's methods are used. After an inverse transformation to the original space a family of numerical methods for solving optimization problems with equality and inequality constraints is obtained. The proposed algorithms are based on the numerical integration of the systems of ordinary differential equations. These algorithms do not require feasibility of the starting and current points, but they preserve feasibility. As a result of a space transformation the vector fields of differential equations are changed and additional terms are introduced which serve as a barrier preventing the trajectories from leaving the feasible set. A proof of a convergence is given.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.Research was supported by the grant N93-012-450 from Russian Scientific Fund.     

Approximation of Markov decision processes with general state space

We deal with a discrete-time finite horizon Markov decision process with locally compact Borel state and action spaces, and possibly unbounded cost function. Based on Lipschitz continuity of the elements of the control model, we propose a state and action discretization procedure for approximating the optimal value function and an optimal policy of the original control model. We provide explicit bounds on the approximation errors. Our results are illustrated by a numerical application to a fisheries management problem.