Scatter search for chemical and bio-process optimization

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in 1960s for combining decision rules and problem constraints such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we develop a general purpose heuristic for a class of nonlinear optimization problems. The procedure is based on the scatter search methodology and treats the objective function evaluation as a black box, making the search algorithm context-independent. Most optimization problems in the chemical and bio-chemical industries are highly nonlinear in either the objective function or the constraints. Moreover, they usually present differential-algebraic systems of constraints. In this type of problem, the evaluation of a solution or even the feasibility test of a set of values for the decision variables is a time-consuming operation. In this context, the solution method is limited to a reduced number of solution examinations. We have implemented a scatter search procedure in Matlab (Mathworks, 2004) for this special class of difficult optimization problems. Our development goes beyond a simple exercise of applying scatter search to this class of problems, but presents innovative mechanisms to obtain a good balance between intensification and diversification in a short-term search horizon. Computational comparisons with other recent methods over a set of benchmark problems favor the proposed procedure.     

A successive quadratic programming method for a class of constrained nonsmooth optimization problems

In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations.     

A memetic algorithm for multi-objective dynamic location problems

This paper describes a new multiobjective interactive memetic algorithm applied to dynamic location problems. The memetic algorithm integrates genetic procedures and local search. It is able to solve capacitated and uncapacitated multi-objective single or multi-level dynamic location problems. These problems are characterized by explicitly considering the possibility of a facility being open, closed and reopen more than once during the planning horizon. It is possible to distinguish the opening and reopening periods, assigning them different coefficient values in the objective functions. The algorithm is part of an interactive procedure that asks the decision maker to define interesting search areas by establishing limits to the objective function values or by indicating reference points. The procedure will be applied to some illustrative location problems.     

Simple Sequential Quadratically Constrained Quadratic Programming Feasible Algorithm with Active Identification Sets for Constrained Minimax Problems

In this paper, the nonlinear minimax problems with inequality constraints are discussed. Based on the idea of simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization, an alternative algorithm for solving the discussed problems is proposed. Unlike the previous work, at each iteration, a feasible direction of descent called main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions. Then a high-order correction direction used to avoid the Maratos effect is computed by updating the main search direction with a system of linear equations. The proposed algorithm possesses global convergence under weak Mangasarian–Fromovitz constraint qualification and superlinear convergence under suitable conditions with the upper-level strict complementarity. At last, some preliminary numerical results are reported.     

Globally and Superlinearly Convergent QP-Free Algorithm for Nonlinear Constrained Optimization

A new, infeasible QP-free algorithm for nonlinear constrained optimization problems is proposed. The algorithm is based on a continuously differentiable exact penalty function and on active-set strategy. After a finite number of iterations, the algorithm requires only the solution of two linear systems at each iteration. We prove that the algorithm is globally convergent toward the KKT points and that, if the second-order sufficiency condition and the strict complementarity condition hold, then the rate of convergence is superlinear or even quadratic. Moreover, we incorporate two automatic adjustment rules for the choice of the penalty parameter and make use of an approximated direction as derivative of the merit function so that only first-order derivatives of the objective and constraint functions are used.     

求广义几何规划全局最优解的线性化方法

对广义几何规划问题(GGP)提出了一个确定型全局优化算法，这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中，使用指数变换及对目标函数和约束函数的线性下界估计，建立了GGP的松弛线性规划(RLP)，通过对RLP可行域的细分以及一系列RLP的求解过程，从理论上证明了算法能收敛到GGP的全局最优解，对一个化学工程设计问题应用本文算法，数值实验表明本文方法是可行的。     

Computing Aviation Sparing Policies: Solving a Large Nonlinear Integer Program

Deployed US Navy aircraft carriers must stock a large number of spare parts to support the various types of aircraft embarked on the ship. The sparing policy determines the spares that will be stocked on the ship to keep the embarked aircraft ready to fly. Given a fleet of ten or more aircraft carriers and a cost of approximately 50 million dollars per carrier plus the cost of spares maintained in warehouses in the United States, the sparing problem constitutes a significant portion of the Navy’s resources. The objective of this work is to find a minimum-cost sparing policy that meets the readiness requirements of the embarked aircraft. This is a very large, nonlinear, integer optimization problem. The cost function is piecewise linear and convex while the constraint mapping is highly nonlinear. The distinguishing characteristics of this problem from an optimization viewpoint are that a large number of decision variables are required to be integer and that the nonlinear constraint functions are essentially “black box” functions; that is, they are very difficult (and expensive) to evaluate and their derivatives are not available. Moreover, they are not convex. Integer programming problems with a large number of variables are difficult to solve in general and most successful approaches to solving nonlinear integer problems have involved linear approximation and relaxation techniques that, because of the complexity of the constraint functions, are inappropriate for attacking this problem. We instead employ a pattern search method to each iteration of an interior point-type algorithm to solve the relaxed version of the problem. From the solution found by the pattern search on each interior point iteration, we begin another pattern search on the integer lattice to find a good integer solution. The best integer solution found across all interations is returned as the optimal solution. The pattern searches are distributed across a local area network of non-dedicated, heterogeneous computers in an office environment, thus, drastically reducing the time required to find the solution.     

Model and algorithm for inventory/routing decision in a three-echelon logistics system

This paper addresses an integrated inventory and routing problem in a three-echelon logistics system, which consists of a supplier, a central warehouse and a group of retailers. The inventory decision of each member and the routing decision among members of the system are made simultaneously, with the objective of minimizing the overall average cost of the system. A strategy named fixed partition and power-of-two (FP–POT) is proposed for the considered problem and a variable large neighborhood search (VLNS) algorithm, which is a special case of variable neighborhood search (VNS) algorithm, is developed. The efficiency of the strategy as well as the algorithm is illustrated by comparing computational results with a lower bound. The advantage of the proposed VLNS algorithm is further shown by getting better results for the problems in a two-echelon logistics system, which have been solved by a Tabu Search algorithm recently.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

Interactive multiobjective complex search

An interactive procedure based on Box's complex search is used to solve the vector maximization problem. This method has the advantage that the decision maker's underlying value function need not be explicitly specified. Also, the problem may have nonlinear objective functions and nonlinear constraints. Several example problems are presented.     

A method for globally minimizing concave functions over convex sets

A method is described for globally minimizing concave functions over convex sets whose defining constraints may be nonlinear. The algorithm generates linear programs whose solutions minimize the convex envelope of the original function over successively tighter polytopes enclosing the feasible region. The algorithm does not involve cuts of the feasible region, requires only simplex pivot operations and univariate search computations to be performed, allows the objective function to be lower semicontinuous and nonseparable, and is guaranteed to converge to the global solution. Computational aspects of the algorithm are discussed.     

An approach to find redundant objective function(s) and redundant constraint(s) in multi-objective nonlinear stochastic fractional programming problems

Structural redundancies in mathematical programming models are nothing uncommon and nonlinear programming problems are no exception. Over the past few decades numerous papers have been written on redundancy. Redundancy in constraints and variables are usually studied in a class of mathematical programming problems. However, main emphasis has so far been given only to linear programming problems. In this paper, an algorithm that identifies redundant objective function(s) and redundant constraint(s) simultaneously in multi-objective nonlinear stochastic fractional programming problems is provided. A solution procedure is also illustrated with numerical examples. The proposed algorithm reduces the number of nonlinear fractional objective functions and constraints in cases where redundancy exists.     

仿射内点既约投影Hessian算法解非线性约束优化

本文结合非单调内点回代技术,提供了新的仿射信赖域方法解含有非负变量约束和非线性等式约束的优化问题.为求解大规模问题,采用等式约束的Jacobian矩阵的QR分解和两块校正的双边既约Hessian矩阵投影,将问题分解成零空间和值空间两个信赖域子问题.零空间的子问题为通常二次目标函数只带椭球约束的信赖域子问题,而值空间的子问题使用满足信赖域约束参数的值空间投影向量方向.通过引入Fletcher罚函数作为势函数,将由两个子问题结合信赖域策略构成的合成方向,并使用非单调线搜索技术回代于可接受的非负约束内点步长.在合理的条件下,算法具有整体收敛性且两块校正的双边既约Hessian投影法将保持超线性收敛速率.非单调技术将克服高度非线性情况,加快收敛进展.     

A dimension-reduced method of sensitivity analysis for stochastic user equilibrium assignment model

This paper gives a new dimension-reduced method of sensitivity analysis for perturbed stochastic user equilibrium assignment (SUEA) model based on the relation between its Lagrange function and logarithmic barrier function combined with a Courant quadratic penalty term. The advantage of this method is of smaller dimension than general sensitivity analysis and reducing complexity. Firstly, it presents the dimension-reduced sensitivity results of the general nonlinear programming perturbation problem and the improved results when the objective or constraint functions are not twice continuously differentiable. Then it proves the corresponding conclusion of SUEA with smooth or non-smooth cost functions by the method of converting constraint conditions and decision variables. Finally, two corresponding examples (smooth and non-smooth) are given to illustrate the feasibility of this method.     

多变量、多约束连续或离散的非线性规划的一个通用算法

利用目标函数对约束函数关于设计变量的一阶微分或差分之比,给出了一个求解非线性规划的通用算法．不论变量和约束有多少,也不论变量是连续的还是离散的,这一算法都比较有效,尤其对离散非线性规划更有效．该方法是一种搜索法,勿需解任何数学方程,只需要计算函数值以及函数对变量的偏微分或差分值．许多数值例题和运筹学中一些经典问题,如1) 一、二维的背包问题;2) 一、二维资源分配问题;3) 复合系统工作可靠性问题;4) 机器负荷问题等,经用此法求解验证均较传统方法更有效和可靠．该方法的主要优点是:1) 不受问题的规模限制;2) 只要在可行域（集）内存在目标函数和约束函数及其一阶导数或差分的值,肯定可以搜索到最优的解,没有不收敛和不稳定的问题．     

INTERIOR POINT PROJECTED REDUCED HESSIAN METHOD WITH TRUST REGION STRATEGY FOR NONLINEAR CONSTRAINED OPTIMIZATION

§1　IntroductionIn this paper we analyze an interior point scaling projected reduced Hessian methodwith trust region strategy for solving the nonlinear equality constrained optimizationproblem with nonnegative constraints on variables:min　f(x)s.t.　c(x) =0 (1.1)x≥0where f∶Rn→R is the smooth nonlinear function,notnecessarily convex and c(x)∶Rn→Rm(m≤n) is the vector nonlinear function.There are quite a few articles proposing localsequential quadratic programming reduced Hessian methods…     

A modified Hooke and Jeeves algorithm with likelihood ratio performance extrapolation for simulation optimization

The Hooke and Jeeves algorithm (HJ) is a pattern search procedure widely used to optimize non-linear functions that are not necessarily continuous or differentiable. The algorithm performs repeatedly two types of search routines; an exploratory search and a pattern search. The HJ algorithm requires deterministic evaluation of the function being optimized. In this paper we consider situations where the objective function is stochastic and can be evaluated only through Monte Carlo simulation. To overcome the problem of expensive use of function evaluations for Monte Carlo simulation, a likelihood ratio performance extrapolation (LRPE) technique is used. We extrapolate the performance measure for different values of the decision parameters while simulating a single sample path from the underlying system. Our modified Hooke and Jeeves algorithm uses a likelihood ratio performance extrapolation for simulation optimization. Computational results are provided to demonstrate the performance of the proposed modified HJ algorithm.     

Random algorithms for convex minimization problems

This paper deals with iterative gradient and subgradient methods with random feasibility steps for solving constrained convex minimization problems, where the constraint set is specified as the intersection of possibly infinitely many constraint sets. Each constraint set is assumed to be given as a level set of a convex but not necessarily differentiable function. The proposed algorithms are applicable to the situation where the whole constraint set of the problem is not known in advance, but it is rather learned in time through observations. Also, the algorithms are of interest for constrained optimization problems where the constraints are known but the number of constraints is either large or not finite. We analyze the proposed algorithm for the case when the objective function is differentiable with Lipschitz gradients and the case when the objective function is not necessarily differentiable. The behavior of the algorithm is investigated both for diminishing and non-diminishing stepsize values. The almost sure convergence to an optimal solution is established for diminishing stepsize. For non-diminishing stepsize, the error bounds are established for the expected distances of the weighted averages of the iterates from the constraint set, as well as for the expected sub-optimality of the function values along the weighted averages.     

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.     

An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint

We propose an exact solution approach for solving nonlinear multi-objective optimization problems with separable discrete variables and a single constraint. The approach converts the multi-objective problem into a single objective problem by using surrogate multipliers from which we find all the solutions with objective values within a given range. We call this the surrogate target problem which is solved by using an algorithm based on the modular approach. Computational experiments demonstrate the effectiveness of this approach in solving large-scale problems. A simple example is presented to illustrate an interactive decision making process.