A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis

Adaptive regularized framework using cubics has emerged as an alternative to line-search and trust-region algorithms for smooth nonconvex optimization, with an optimal complexity among second-order methods. In this paper, we propose and analyze the use of an iteration dependent scaled norm in the adaptive regularized framework using cubics. Within such a scaled norm, the obtained method behaves as a line-search algorithm along the quasi-Newton direction with a special backtracking strategy. Under appropriate assumptions, the new algorithm enjoys the same convergence and complexity properties as adaptive regularized algorithm using cubics. The complexity for finding an approximate first-order stationary point can be improved to be optimal whenever a second-order version of the proposed algorithm is regarded. In a similar way, using the same scaled norm to define the trust-region neighborhood, we show that the trust-region algorithm behaves as a line-search algorithm. The good potential of the obtained algorithms is shown on a set of large-scale optimization problems.     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

Finding feasible vectors of Edmonds-Giles polyhedra

A combinatorial algorithm for finding a feasible vector of the Edmonds-Giles polyhedron is presented. The algorithm is polynomially bounded provided that an oracle is available for minimizing submodular functions. A feasibility theorem is also proved by the algorithm and, as a consequence, a good algorithm for finding an integer-valued modular function between a sub- and a supermodular function is deduced. An important idea in the algorithm is due to Schönsleben and Lawler and Martel: the shortest augmenting paths have to be chosen in a lexicographic order.     

The Finite Element Method for Computing the Stationary Distribution of an SRBM in a Hypercube with Applications to Finite Buffer Queueing Networks

This paper proposes an algorithm, referred to as BNAfm (Brownian network analyzer with finite element method), for computing the stationary distribution of a semimartingale reflecting Brownian motion (SRBM) in a hypercube. The SRBM serves as an approximate model of queueing networks with finite buffers. Our BNAfm algorithm is based on the finite element method and an extension of a generic algorithm developed by Dai and Harrison [14]. It uses piecewise polynomials to form an approximate subspace of an infinite-dimensional functional space. The BNAfm algorithm is shown to produce good estimates for stationary probabilities, in addition to stationary moments. This is in contrast to the BNAsm algorithm (Brownian network analyzer with spectral method) of Dai and Harrison [14], which uses global polynomials to form the approximate subspace and which sometimes fails to produce meaningful estimates of these stationary probabilities. Extensive computational experiences from our implementation are reported, which may be useful for future numerical research on SRBMs. A three-station tandem network with finite buffers is presented to illustrate the effectiveness of the Brownian approximation model and our BNAfm algorithm.     

Vector coding algorithms for multidimensional discrete Fourier transform

A new fast algorithm is presented for the multidimensional discrete Fourier transform (DFT). This algorithm is derived using an interesting technique called “vector coding” (VC), and we call it the vector-coding fast Fourier transform (VC-FFT) algorithm. Since the VC-FFT is an extension of the Cooley–Tukey algorithm from 1-D to multidimensional form, the structure of the program is as simple as the Cooley–Tukey fast Fourier transform (FFT). The new algorithm significantly reduces the number of multiplications and recursive stages. The VC-FFT therefore comprehensively reduces the complexity of the algorithm as compared with other current multidimensional DFT algorithms.     

An alternative to the Bathe algorithm

This paper presents a new composite sub-steps algorithm for solving reliable numerical responses in structural dynamics. The newly developed algorithm is a two sub-steps, second-order accurate and unconditionally stable implicit algorithm with the same numerical properties as the Bathe algorithm. The detailed analysis of the stability and numerical accuracy is presented for the new algorithm, which shows that its numerical characteristics are identical to those of the Bathe algorithm. Hence, the new sub-steps scheme could be considered as an alternative to the Bathe algorithm. Meanwhile, the new algorithm possesses the following properties: (a) it produces the same accurate solutions as the Bathe algorithm for solving linear and nonlinear problems; (b) it does not involve any artificial parameters and additional variables, such as the Lagrange multipliers; (c) The identical effective stiffness matrices can be obtained inside two sub-steps; (d) it is a self-starting algorithm. Some numerical experiments are given to show the superiority of the new algorithm and the Bathe algorithm over the dissipative CH-α algorithm and the non-dissipative trapezoidal rule.     

An algorithm for large scale 0–1 integer programming with application to airline crew scheduling

We present an approximation algorithm for solving large 0–1 integer programming problems whereA is 0–1 and whereb is integer. The method can be viewed as a dual coordinate search for solving the LP-relaxation, reformulated as an unconstrained nonlinear problem, and an approximation scheme working together with this method. The approximation scheme works by adjusting the costs as little as possible so that the new problem has an integer solution. The degree of approximation is determined by a parameter, and for different levels of approximation the resulting algorithm can be interpreted in terms of linear programming, dynamic programming, and as a greedy algorithm. The algorithm is used in the CARMEN system for airline crew scheduling used by several major airlines, and we show that the algorithm performs well for large set covering problems, in comparison to the CPLEX system, in terms of both time and quality. We also present results on some well known difficult set covering problems that have appeared in the literature.     

A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem

This paper presents an efficient solution algorithm for the multiconstraint zero-one knapsack problem through a branch and bound search process. The algorithm has been coded in FORTRAN; and a group of thirty 5-constraint knapsack problems with 30-90 variables were run on IBM 360/75 using two other codes as well, in order to compare the computational efficiency of the proposed method with that of the original Balas and an improved Balas additive algorithms. The computational results show that the proposed method is markedly faster with regard to the total as well as the individual solution times for these test problems, and such superiority becomes more evident as the number of variables and the difficulty of the problems increase. The results also indicated that the original Balas method is extremely inefficient for the type of problems being considered here. The total solution time for the thirty problems is 13 min for the proposed method, 109 min for the improved Balas algorithm, and over 380 min for the original Balas algorithm. Extension of the solution algorithm to the generalized knapsack problem is also suggested.     

Minimization of the sum of three linear fractional functions

In this paper, we will propose an efficient and reliable heuristic algorithm for minimizing and maximizing the sum of three linear fractional functions over a polytope. These problems are typical nonconvex minimization problems of practical as well as theoretical importance. This algorithm uses a primal-dual parametric simplex algorithm to solve a subproblem in which the value of one linear function is fixed. A subdivision scheme is employed in the space of this linear function to obtain an approximate optimal solution of the original problem. It turns out that this algorithm is much more efficient and usually generates a better solution than existing algorithms. Also, we will develop a similar algorithm for minimizing the product of three linear fractional functions.     

A new multiobjective simulated annealing algorithm

A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions, suitable for the generation on non-convex fronts, are presented. The effectiveness of the algorithm is shown through five test problems. The parametric study presented shows that more fitness functions as well as more iteration gives more non-dominated points closer to the actual front. The study also compares the linear and elliptic fitness functions. The success of the algorithm is also demonstrated by comparing the quality metrics obtained to those obtained for a well-known evolutionary multiobjective algorithm.     

A BRANCH BOUND METHOD FOR SUBSET SUM PROBLEM

ＡＢＲＡＮＣＨＢＯＵＮＤＭＥＴＨＯＤＦＯＲＳＵＢＳＥＴＳＵＭＰＲＯＢＬＥＭＷＵＳＨＩＱＵＡＮ（吴士泉）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃ...     

An Extension of Least Angle Regression Based on the Information Geometry of Dually Flat Spaces

We extend the least angle regression algorithm using the information geometry of dually flat spaces. The extended least angle regression algorithm is used for estimating parameters in generalized linear regression, and it can be also used for selecting explanatory variables. We use the fact that a model manifold of an exponential family is a dually flat space. In estimating parameters, curves corresponding to bisectors in the Euclidean space play an important role. Originally, the least angle regression algorithm is used for estimating parameters and selecting explanatory variables in linear regression. It is an efficient algorithm in the sense that the number of iterations is the same as the number of explanatory variables. We extend the algorithm while keeping this efficiency. However, the extended least angle regression algorithm differs significantly from the original algorithm. The extended least angle regression algorithm reduces one explanatory variable in each iteration while the original algorithm increases one explanatory variable in each iteration. We show results of the extended least angle regression algorithm for two types of datasets. The behavior of the extended least angle regression algorithm is shown. Especially, estimates of parameters become smaller and smaller, and vanish in turn.     

Formulation and computation of general financial equilibrium

In this paper a model of competitive financial equilibrium is introduced, which yields the optimal composition of assets and liabilities in each sector's portfolio, as well as the market clearing prices for each instrument. The variational inequality formulation of the equilibrium conditions is then utilized to establish existence and uniqueness properties of the solution pattern. Finally, an algorithm is proposed for the computation of the equilibrium pattern; the algorithm resolves the problem into simple network subproblems which can then be solved in closed form. The algorithm is then applied to an example.     

Policy iteration for robust nonstationary Markov decision processes

Policy iteration is a well-studied algorithm for solving stationary Markov decision processes (MDPs). It has also been extended to robust stationary MDPs. For robust nonstationary MDPs, however, an “as is” execution of this algorithm is not possible because it would call for an infinite amount of computation in each iteration. We therefore present a policy iteration algorithm for robust nonstationary MDPs, which performs finitely implementable approximate variants of policy evaluation and policy improvement in each iteration. We prove that the sequence of cost-to-go functions produced by this algorithm monotonically converges pointwise to the optimal cost-to-go function; the policies generated converge subsequentially to an optimal policy.     

An effective heuristic algorithm to minimise stack shuffles in selecting steel slabs from the slab yard for heating and rolling

Steel production is a multi-stage process. A slab yard serves as a buffer between the continuous casting stage and the steel rolling stage. Steel slabs are stored in stacks in the yard. Shuffling is needed when picking up a slab for heating and rolling, if it is not in the top position of a stack. This paper studies the problem of selecting appropriate slabs in the yard for a given rolling schedule so as to minimise the total shuffling cost. The study uses the hot strip rolling mill in Shanghai Baoshan Iron and Steel Complex as an application background. We propose a new heuristic algorithm to solve the problem. This is a two-phase algorithm that first generates an initial feasible solution and then improves it using local search. The new algorithm is compared with the algorithm in use on randomly generated test problems and on real data. Experimental results show that the proposed algorithm yields significant better solutions. The average improvement over the old algorithm is 15%.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

An algorithm based on the generalized D-gap function for equilibrium problems

The equilibrium problem (EP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. In this paper, we propose an algorithm for minimizing the problem and analyze some convergence properties of the proposed algorithm. Under some reasonable conditions, we show that the iteration sequence generated by the algorithm is globally convergent and converges to a solution to the EP and the generalized D-gap function provides a global error bound for the algorithm.     

Harris Hawks optimization with information exchange

The basic Harris Hawks optimization algorithm cannot take full advantage of the information sharing capability of the Harris Hawks while cooperatively searching for prey, and it is difficult to balance the exploration and development capacities of this algorithm. These factors limit the Harris Hawks optimization algorithm, such as in terms of premature convergence and ease of falling into a local optimum. To this end, an improved Harris Hawks optimization algorithm based on information exchange is proposed to optimize the continuous function and its application to engineering problems. First, an individual Harris Hawk obtains information from the shared area of cooperative foraging and the location area of collaborators, thereby realizing information exchange and sharing. Second, a nonlinear escaping energy factor with chaos disturbance is designed to better balance the local searching and the global searching of the algorithm. Finally, a numerical experiment is conducted with four benchmark test functions and five CEC-2017 real-parameter numerical optimization problems as well as seven practical engineering problems. The results show that the proposed algorithm outperforms the basic Harris Hawks optimization algorithm and other intelligence optimization algorithms in terms of the convergence rate, solution accuracy, and robustness.     

A proposal for a hybrid meta-strategy for combinatorial optimization problems

In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。