A stochastic production planning problem in hybrid manufacturing and remanufacturing systems with resource capacity planning

DIRECT is derivative-free global-search algorithm has been found to perform robustly across a wide variety of low-dimensional test problems. The reason DIRECT’s robustness is its lack of algorithmic parameters that need be “tuned” to make the algorithm perform well. In particular, there is no parameter that determines the relative emphasis on global versus local search. Unfortunately, the same algorithmic features that enable DIRECT to perform so robustly have a negative side effect. In particular, DIRECT is usually quick to get close to the global minimum, but very slow to refine the solution to high accuracy. This is what we call DIRECT’s “eventually inefficient behavior.” In this paper, we outline two root causes for this undesirable behavior and propose modifications to eliminate it. The paper builds upon our previously published “MrDIRECT” algorithm, which we can now show only addressed the first root cause of the “eventually inefficient behavior.” The key contribution of the current paper is a further enhancement that allows MrDIRECT to address the second root cause as well. To demonstrate the effectiveness of the enhanced MrDIRECT, we have identified a set of test functions that highlight different situations in which DIRECT has convergence issues. Extensive numerical work with this test suite demonstrates that the enhanced version of MrDIRECT does indeed improve the convergence rate of DIRECT.     

A Comparison of Global Optimization Methods for the Design of a High-speed Civil Transport

The conceptual design of aircraft often entails a large number of nonlinear constraints that result in a nonconvex feasible design space and multiple local optima. The design of the high-speed civil transport (HSCT) is used as an example of a highly complex conceptual design with 26 design variables and 68 constraints. This paper compares three global optimization techniques on the HSCT problem and two test problems containing thousands of local optima and noise: multistart local optimizations using either sequential quadratic programming (SQP) as implemented in the design optimization tools (DOT) program or Snyman's dynamic search method, and a modified form of Jones' DIRECT global optimization algorithm. SQP is a local optimizer, while Snyman's algorithm is capable of moving through shallow local minima. The modified DIRECT algorithm is a global search method based on Lipschitzian optimization that locates small promising regions of design space and then uses a local optimizer to converge to the optimum. DOT and the dynamic search algorithms proved to be superior for finding a single optimum masked by noise of trigonometric form. The modified DIRECT algorithm was found to be better for locating the global optimum of functions with many widely separated true local optima.     

A Modified DIviding RECTangles Algorithm for a Problem in Astrophysics

We present a modification of the DIRECT (DIviding RECTangles) algorithm, called DIRECT-G, to solve a box-constrained global optimization problem arising in the detection of gravitational waves emitted by coalescing binary systems of compact objects. This is a hard problem, since the objective function is highly nonlinear and expensive to evaluate, has a huge number of local extrema and unavailable derivatives. DIRECT performs a sampling of the feasible domain over a set of points that becomes dense in the limit, thus ensuring the everywhere dense convergence; however, it becomes ineffective on significant instances of the problem under consideration, because it tends to produce a uniform coverage of the feasible domain, by oversampling regions that are far from the optimal solution. DIRECT has been modified by embodying information provided by a suitable discretization of the feasible domain, based on the signal theory, which takes into account the variability of the objective function. Numerical experiments show that DIRECT-G largely outperforms DIRECT and the grid search, the latter being the reference algorithm in the astrophysics community. Furthermore, DIRECT-G is comparable with a genetic algorithm specifically developed for the problem. However, DIRECT-G inherits the convergence properties of DIRECT, whereas the genetic algorithm has no guarantee of convergence.     

基于引力搜索和粒子群混合优化算法的证券投资组合问题研究

本文研究考虑交易成本的投资组合模型,分别以风险价值(VAR)和夏普比率(SR)作为投资组合的风险评价指标和效益评价指标。为有效求解此模型,本文在引力搜索和粒子群算法的基础上提出了一种混合优化算法(IN-GSA-PSO),将粒子群算法的群体最佳位置和个体最佳位置与引力搜索算法的加速度算子有机结合,使混合优化算法充分发挥单一算法的开采能力和探索能力。通过对算法相关参数的合理设置,算法能够达到全局搜索和局部搜索的平衡,快速收敛到模型的最优解。本文选取上证50股2014年下半年126个交易日的数据,运用Matlab软件进行仿真实验,实验结果显示,考虑交易成本的投资组合模型可使投资者得到更高的收益率。研究同时表明,基于PSO和GSA的混合算法在求解投资组合模型时比单一算法具有更好的性能,能够得到满意的优化结果。     

GOSH: derivative-free global optimization using multi-dimensional space-filling curves

Global optimization is a field of mathematical programming dealing with finding global (absolute) minima of multi-dimensional multiextremal functions. Problems of this kind where the objective function is non-differentiable, satisfies the Lipschitz condition with an unknown Lipschitz constant, and is given as a “black-box” are very often encountered in engineering optimization applications. Due to the presence of multiple local minima and the absence of differentiability, traditional optimization techniques using gradients and working with problems having only one minimum cannot be applied in this case. These real-life applied problems are attacked here by employing one of the mostly abstract mathematical objects—space-filling curves. A practical derivative-free deterministic method reducing the dimensionality of the problem by using space-filling curves and working simultaneously with all possible estimates of Lipschitz and Hölder constants is proposed. A smart adaptive balancing of local and global information collected during the search is performed at each iteration. Conditions ensuring convergence of the new method to the global minima are established. Results of numerical experiments on 1000 randomly generated test functions show a clear superiority of the new method w.r.t. the popular method DIRECT and other competitors.     

A Locally-Biased form of the DIRECT Algorithm

In this paper we propose a form of the DIRECT algorithm that is strongly biased toward local search. This form should do well for small problems with a single global minimizer and only a few local minimizers. We motivate our formulation with some results on how the original formulation of the DIRECT algorithm clusters its search near a global minimizer. We report on the performance of our algorithm on a suite of test problems and observe that the algorithm performs particularly well when termination is based on a budget of function evaluations.     

Improved scheme for selection of potentially optimal hyper-rectangles in <Emphasis FontCategory="NonProportional">DIRECT</Emphasis>

We consider a box-constrained global optimization problem with a Lipschitz-continuous objective function and an unknown Lipschitz constant. The well known derivative-free global-search DIRECT (DIvide a hyper-RECTangle) algorithm performs well solving such problems. However, the efficiency of the DIRECT algorithm deteriorates on problems with many local optima and when the solution with high accuracy is required. To overcome these difficulties different regimes of global and local search are introduced or the algorithm is combined with local optimization. In this paper we investigate a different direction of improvement of the DIRECT algorithm and propose a new strategy for the selection of potentially optimal rectangles, what does not require any additional parameters or local search subroutines. An extensive experimental investigation reveals the effectiveness of the proposed enhancements.     

Dual subgradient algorithms for large-scale nonsmooth learning problems

“Classical” First Order (FO) algorithms of convex optimization, such as Mirror Descent algorithm or Nesterov’s optimal algorithm of smooth convex optimization, are well known to have optimal (theoretical) complexity estimates which do not depend on the problem dimension. However, to attain the optimality, the domain of the problem should admit a “good proximal setup”. The latter essentially means that (1) the problem domain should satisfy certain geometric conditions of “favorable geometry”, and (2) the practical use of these methods is conditioned by our ability to compute at a moderate cost proximal transformation at each iteration. More often than not these two conditions are satisfied in optimization problems arising in computational learning, what explains why proximal type FO methods recently became methods of choice when solving various learning problems. Yet, they meet their limits in several important problems such as multi-task learning with large number of tasks, where the problem domain does not exhibit favorable geometry, and learning and matrix completion problems with nuclear norm constraint, when the numerical cost of computing proximal transformation becomes prohibitive in large-scale problems. We propose a novel approach to solving nonsmooth optimization problems arising in learning applications where Fenchel-type representation of the objective function is available. The approach is based on applying FO algorithms to the dual problem and using the accuracy certificates supplied by the method to recover the primal solution. While suboptimal in terms of accuracy guaranties, the proposed approach does not rely upon “good proximal setup” for the primal problem but requires the problem domain to admit a Linear Optimization oracle—the ability to efficiently maximize a linear form on the domain of the primal problem.     

A new approach to improve ill-conditioned parabolic optimal control problem via time domain decomposition

In this paper we present a new steepest-descent type algorithm for convex optimization problems. Our algorithm pieces the unknown into sub-blocs of unknowns and considers a partial optimization over each sub-bloc. In quadratic optimization, our method involves Newton technique to compute the step-lengths for the sub-blocs resulting descent directions. Our optimization method is fully parallel and easily implementable, we first presents it in a general linear algebra setting, then we highlight its applicability to a parabolic optimal control problem, where we consider the blocs of unknowns with respect to the time dependency of the control variable. The parallel tasks, in the last problem, turn “on” the control during a specific time-window and turn it “off” elsewhere. We show that our algorithm significantly improves the computational time compared with recognized methods. Convergence analysis of the new optimal control algorithm is provided for an arbitrary choice of partition. Numerical experiments are presented to illustrate the efficiency and the rapid convergence of the method.     

A nonmonotone GRASP

A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP).     

A modified quasisecant method for global optimization

This paper presents an algorithm for global optimization problem whose objective functions is Lipschitz continuous but not necessarily differentiable. The proposed algorithm consists of local and global search procedures which are based on and inspired by quasisecant method, respectively. The aim of the global search procedure is to identify “promising” basins in the search space. Once a promising basin is identified, the search procedure skips from an exhausted area to the obtained basin, and the local search procedure is then applied at this basin. It proves that the proposed algorithm converges to the global minimum solution if the local ones are finite and isolated. The proposed method is tested by academic benchmarks, numerical performance and comparison show that it is efficient and robust. Finally, The method is applied to solve the sensor localization problem.     

Lower bounds for a subexponential optimization algorithm

Recently Sharir and Welzl described a randomized algorithm for a certain class of optimization problems (including linear programming), and then a subexponential bound for the expected running time was established. We give an example of an (artificial) optimization problem fitting into the Sharir–Welzl framework for which the running time is close to the upper bound, thus showing that the analysis of the algorithm cannot be much improved without stronger assumptions on the optimization problem and/or modifying the algorithm. Further we describe results of computer simulations for a specific linear programming problem, which indicate that “one-permutation” and “move-to-front” variants of the Sharir–Welzl algorithm may sometimes perform much worse than the algorithm itself. © 1994 John Wiley & Sons, Inc.     

A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs

We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be second-order cone representable. The usefulness of these new relaxations is demonstrated both theoretically and computationally.     

Genetic algorithm with automatic termination and search space rotation

In the last two decades, numerous evolutionary algorithms (EAs) have been developed for solving optimization problems. However, only a few works have focused on the question of the termination criteria. Indeed, EAs still need termination criteria prespecified by the user. In this paper, we develop a genetic algorithm (GA) with automatic termination and acceleration elements which allow the search to end without resort to predefined conditions. We call this algorithm “Genetic Algorithm with Automatic Termination and Search Space Rotation”, abbreviated as GATR. This algorithm utilizes the so-called “Gene Matrix” (GM) to equip the search process with a self-check in order to judge how much exploration has been performed, while maintaining the population diversity. The algorithm also implements a mutation operator called “mutagenesis” to achieve more efficient and faster exploration and exploitation processes. Moreover, GATR fully exploits the structure of the GM by calling a novel search space decomposition mechanism combined with a search space rotation procedure. As a result, the search operates strictly within two-dimensional subspaces irrespective of the dimension of the original problem. The computational experiments and comparisons with some state-of-the-art EAs demonstrate the effectiveness of the automatic termination criteria and the space decomposition mechanism of GATR.     

Using DIRECT to Solve an Aircraft Routing Problem

In this paper we discuss a global optimization problem arising in the calculation of aircraft flight paths. Since gradient information for this problem may not be readily available, a direct-search algorithm (DIRECT), proposed by Jones et al., Journal of Optimization Theory and Applications, vol. 79, pp. 157–181, 1993, appears to be a promising solution technique. We describe some numerical experience in which DIRECT is used in several different ways to solve a sample problem.     

Dynamic Data Structures for a Direct Search Algorithm

The DIRECT (DIviding RECTangles) algorithm of Jones, Perttunen, and Stuckman (Journal of Optimization Theory and Applications, vol. 79, no. 1, pp. 157–181, 1993), a variant of Lipschitzian methods for bound constrained global optimization, has proved effective even in higher dimensions. However, the performance of a DIRECT implementation in real applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice, since it is difficult to predict memory resource requirements in advance. This is especially critical in multidisciplinary engineering design applications, where the DIRECT optimization is just one small component of a much larger computation, and any component failure aborts the entire design process. To make the DIRECT global optimization algorithm efficient and robust on large-scale, multidisciplinary engineering problems, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus of this paper is on design issues of the dynamic data structures, and related memory management strategies. Numerical computing techniques and modifications of Jones' original DIRECT algorithm in terms of stopping rules and box selection rules are also explored. Performance studies are done for synthetic test problems with multiple local optima. Results for application to a site-specific system simulator for wireless communications systems (S ⁴ W) are also presented to demonstrate the effectiveness of the proposed dynamic data structures for an implementation of DIRECT.     

Linear scaling and the DIRECT algorithm

In this paper, we discuss the performance of the DIRECT global optimization algorithm on problems with linear scaling. We show with computations that the performance of DIRECT can be affected by linear scaling of the objective function. We also provide a theoretical result which shows that DIRECT does not perform well when the absolute value of the objective function is large enough. Then we present DIRECT-a, a modification of DIRECT, to eliminate the sensitivity to linear scaling of the objective function. We prove theoretically that linear scaling of the objective function does not affect the performance of DIRECT-a. Similarly, we prove that some modifications of DIRECT are also unaffected by linear scaling of the objective function, while the original DIRECT algorithm is sensitive to linear scaling. Numerical results in this paper show that DIRECT-a is more robust than the original DIRECT algorithm, which support the theoretical results. Numerical results also show that careful choices of the parameter ε can help DIRECT perform well when the objective function is poorly linearly scaled.     

Scheduling for a processor sharing system with linear slowdown

We consider the problem of scheduling arrivals to a congestion system with a finite number of users having identical deterministic demand sizes. The congestion is of the processor sharing type in the sense that all users in the system at any given time are served simultaneously. However, in contrast to classical processor sharing congestion models, the processing slowdown is proportional to the number of users in the system at any time. That is, the rate of service experienced by all users is linearly decreasing with the number of users. For each user there is an ideal departure time (due date). A centralized scheduling goal is then to select arrival times so as to minimize the total penalty due to deviations from ideal times weighted with sojourn times. Each deviation penalty is assumed quadratic, or more generally convex. But due to the dynamics of the system, the scheduling objective function is non-convex. Specifically, the system objective function is a non-smooth piecewise convex function. Nevertheless, we are able to leverage the structure of the problem to derive an algorithm that finds the global optimum in a (large but) finite number of steps, each involving the solution of a constrained convex program. Further, we put forward several heuristics. The first is the traversal of neighbouring constrained convex programming problems, that is guaranteed to reach a local minimum of the centralized problem. This is a form of a “local search”, where we use the problem structure in a novel manner. The second is a one-coordinate “global search”, used in coordinate pivot iteration. We then merge these two heuristics into a unified “local–global” heuristic, and numerically illustrate the effectiveness of this heuristic.     

Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle

Two parallel deterministic direct search algorithms are combined to find improved parameters for a system of differential equations designed to simulate the cell cycle of budding yeast. Comparing the model simulation results to experimental data is difficult because most of the experimental data is qualitative rather than quantitative. An algorithm to convert simulation results to mutant phenotypes is presented. Vectors of the 143 parameters defining the differential equation model are rated by a discontinuous objective function. Parallel results on a 2200 processor supercomputer are presented for a global optimization algorithm, DIRECT, a local optimization algorithm, MADS, and a hybrid of the two.     

组合优化算法中摆脱局部极小值的几种策略

局部搜索算法是一种非常有效的求解组合优化问题的算法 ,它具有通用、灵活等特点 .但是 ,由于搜索空间和目标函数的复杂性 ,目标函数在搜索空间中有许多局部极小值点 ,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果 .对于此问题 ,笔者查阅了大量文献资料 ,结合自己的研究实践 ,总结出几种跳出局部极小“陷井”的策略 .使用这些策略 ,有望使算法更加完善 ,在求解组合优化问题过程中更能发挥其作用 .