QP-Free,Truncated Hybrid Methods for Large-Scale Nonlinear Constrained Optimization

1.IntroductionInthispaperweconsiderthefollowingnonlinearprogrammingproblemminimizef(x)subjecttogj(x)2o,jEJ={1,...,m}.(1'1)Extensionstoproblemincludingalsoequalityconstraintswillbepossible.Thefunctionf:W-Rlandgj:Rn-R',jEJaretwicecontinuouslydifferentiable.Inpaxticular,weapplyQP-free(withoutquadraticprogrammingsubproblems),truncatedhybridmethodsforsolvingthelarge-scaJenonlinearprogrammingproblems,inwhichthenumberofvariablesandthenumberofconstraiotsin(1.1)aregreat.Wediscussthecase,wheresecon…     

A hybrid optimization approach for multi-level capacitated lot-sizing problems

Solving multi-level capacitated lot-sizing problems is still a challenging task, in spite of increasing computational power and faster algorithms. In this paper a new approach combining an ant-based algorithm with an exact solver for (mixed-integer) linear programs is presented. A MAX–MIN ant system is developed to determine the principal production decisions, a LP/MIP solver is used to calculate the corresponding production quantities and inventory levels. Two different local search methods and an improvement strategy based on reduced mixed-integer problems are developed and integrated into the ant algorithm. This hybrid approach provides superior results for small and medium-sized problems in comparison to the existing approaches in the literature. For large-scale problems the performance of this method is among the best.     

求解大规模极大极小问题的光滑化三项共轭梯度算法

基于指数罚函数,对最近提出的一种求解无约束优化问题的三项共轭梯度法进行了修正,并用它求解更复杂的大规模极大极小值问题.证明了该方法生成的搜索方向对每一个光滑子问题是充分下降方向,而且与所用的线搜索规则无关.以此为基础,设计了求解大规模极大极小值问题的算法,并在合理的假设下,证明了算法的全局收敛性.数值实验表明,该算法优于文献中已有的类似算法.     

Modified subspace limited memory BFGS algorithm for large-scale bound constrained optimization

In this paper, a subspace limited memory BFGS algorithm for solving large-scale bound constrained optimization problems is developed. It is modifications of the subspace limited memory quasi-Newton method proposed by Ni and Yuan [Q. Ni, Y.X. Yuan, A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput. 66 (1997) 1509–1520]. An important property of our proposed method is that more limited memory BFGS update is used. Under appropriate conditions, the global convergence of the method is established. The implementations of the method on CUTE test problems are presented, which indicate the modifications are beneficial to the performance of the algorithm.     

Hierarchical generating method for large-scale multiobjective systems

This paper investigates large-scale multiobjective systems in the context of a general hierarchical generating method which considers the problem of how to find the set of all noninferior solutions by decomposition and coordination. A new, unified framework of the hierarchical generating method is developed by integrating the envelope analysis approach and the duality theory that is used in multiobjective programming. In this scheme, the vector-valued Lagrangian and the duality theorem provide the basis of a decomposition of the overall multiobjective system into several multiobjective subsystems, and the envelope analysis gives an efficient approach to deal with the coordination at a high level. The following decomposition-coordination schemes for different problems are developed: (i) a spatial decomposition and envelope coordination algorithm for large-scale multiobjective static systems; (ii) a temporal decomposition and envelope coordination algorithm for multiobjective dynamic systems; and (iii) a three-level structure algorithm for large-scale multiobjective dynamic systems.This work was supported by NSF Grant No. CEE-82-11606.     

An investigation of interior-point and block pivoting algorithms for large-scale symmetric monotone linear complementarity problems

In this paper we describe a computational study of block principal pivoting (BP) and interior-point predictor-corrector (PC) algorithms for the solution of large-scale linear complementarity problems (LCP) with symmetric positive definite matrices. This study shows that these algorithms are in general quite appropriate for this type of LCPs. The BP algorithm does not seem to be sensitive to bad scaling and degeneracy of the unique solution of the LCP, while these aspects have some effect on the performance of the PC algorithm. On the other hand, the BP method has not performed well in two LCPs with ill-conditioned matrices for which the PC algorithm has behaved quite well.A hybrid algorithm combining these two techniques is also introduced and seems to be the most robust procedure for the solution of large-scale LCPs with symmetric positive definite matrices.Support of this work has been provided by the Instituto de Telecomunicações.     

Multiobjective big data optimization based on a hybrid salp swarm algorithm and differential evolution

This paper developed a multiobjective Big Data optimization approach based on a hybrid salp swarm algorithm and the differential evolution algorithm. The role of the differential evolution algorithm is to enhance the capability of the feature exploitation of the salp swarm algorithm because the operators of the differential evolution algorithm are used as local search operators. In general, the proposed method contains three stages. In the first stage, the population is generated, and the archive is initialized. The second stage updates the solutions using the hybrid salp swarm algorithm and the differential evolution algorithm, and the final stage determines the nondominated solutions and updates the archive. To assess the performance of the proposed approach, a series of experiments were performed. A set of single-objective and multiobjective problems from the 2015 Big Data optimization competition were tested; the dataset contained data with and without noise. The results of our experiments illustrated that the proposed approach outperformed other approaches, including the baseline nondominated sorting genetic algorithm, on all test problems. Moreover, for single-objective problems, the score value of the proposed method was better than that of the traditional multiobjective salp swarm algorithm. When compared with both algorithms, that is, the adaptive DE algorithm with external archive and the hybrid multiobjective firefly algorithm, its score was the largest. In contrast, for the multiobjective functions, the scores of the proposed algorithm were higher than that of the fireworks algorithm framework.     

稀疏线性规划研究

稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.     

An algorithm for hierarchical optimization of large-scale problems with nested structure

This paper describes a general concept and a particular optimization algorithm for solving a class of large-scale nonlinear programming problems with a nested block-angular structured system of linear constraints with coupling variables. A primal optimization algorithm is developed, which is based on the recursive application of the partitioning concept to the nested structure in combination with a feasible directions method. The special column by column application of this partitioning concept finally leads to a very clear and efficient algorithm for nested problems, which is called ‘successive partitioning method’. It is shown that the reduced-gradient method can be represented as a special application of the concept.     

A hybrid optimization technique coupling an evolutionary and a local search algorithm

Evolutionary algorithms are robust and powerful global optimization techniques for solving large-scale problems that have many local optima. However, they require high CPU times, and they are very poor in terms of convergence performance. On the other hand, local search algorithms can converge in a few iterations but lack a global perspective. The combination of global and local search procedures should offer the advantages of both optimization methods while offsetting their disadvantages. This paper proposes a new hybrid optimization technique that merges a genetic algorithm with a local search strategy based on the interior point method. The efficiency of this hybrid approach is demonstrated by solving a constrained multi-objective mathematical test-case.     

An accurate active set conjugate gradient algorithm with project search for bound constrained optimization

In the paper, we propose an active set identification technique which accurately identifies active constraints in a neighborhood of an isolated stationary point without strict complementarity conditions. Based on the identification technique, we propose a conjugate gradient algorithm for large-scale bound constrained optimization. In the algorithm, the recently developed modified Polak-Ribiére-Polyak method is used to update the variables with indices outside of the active set, while the projected gradient method is used to update the active variables. Under appropriate conditions, we show that the proposed method is globally convergent. Numerical experiments are presented using bound constrained problems in the CUTEr test problem library.     

Augmented Lagrangian Algorithms Based on the Spectral Projected Gradient Method for Solving Nonlinear Programming Problems

The spectral projected gradient method SPG is an algorithm for large-scale bound-constrained optimization introduced recently by Birgin, Martínez, and Raydan. It is based on the Raydan unconstrained generalization of the Barzilai-Borwein method for quadratics. The SPG algorithm turned out to be surprisingly effective for solving many large-scale minimization problems with box constraints. Therefore, it is natural to test its perfomance for solving the sub-problems that appear in nonlinear programming methods based on augmented Lagrangians. In this work, augmented Lagrangian methods which use SPG as the underlying convex-constraint solver are introduced (ALSPG) and the methods are tested in two sets of problems. First, a meaningful subset of large-scale nonlinearly constrained problems of the CUTE collection is solved and compared with the perfomance of LANCELOT. Second, a family of location problems in the minimax formulation is solved against the package FFSQP.     

Finding the Maximal Eigenpair for a Large,Dense,Symmetric Matrix based on Mufa Chen's Algorithm

A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.     

An Improved Spectral Conjugate Gradient Algorithm for Nonconvex Unconstrained Optimization Problems

In this paper, an improved spectral conjugate gradient algorithm is developed for solving nonconvex unconstrained optimization problems. Different from the existent methods, the spectral and conjugate parameters are chosen such that the obtained search direction is always sufficiently descent as well as being close to the quasi-Newton direction. With these suitable choices, the additional assumption in the method proposed by Andrei on the boundedness of the spectral parameter is removed. Under some mild conditions, global convergence is established. Numerical experiments are employed to demonstrate the efficiency of the algorithm for solving large-scale benchmark test problems, particularly in comparison with the existent state-of-the-art algorithms available in the literature.     

A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization

In this paper, a novel stochastic extra-step quasi-Newton method is developed to solve a class of nonsmooth nonconvex composite optimization problems. We assume that the gradient of the smooth part of the objective function can only be approximated by stochastic oracles. The proposed method combines general stochastic higher order steps derived from an underlying proximal type fixed-point equation with additional stochastic proximal gradient steps to guarantee convergence. Based on suitable bounds on the step sizes, we establish global convergence to stationary points in expectation and an extension of the approach using variance reduction techniques is discussed. Motivated by large-scale and big data applications, we investigate a stochastic coordinate-type quasi-Newton scheme that allows to generate cheap and tractable stochastic higher order directions. Finally, numerical results on large-scale logistic regression and deep learning problems show that our proposed algorithm compares favorably with other state-of-the-art methods.

     

A three-term conjugate gradient algorithm for large-scale unconstrained optimization problems

In this paper, a three-term conjugate gradient algorithm is developed for solving large-scale unconstrained optimization problems. The search direction at each iteration of the algorithm is determined by rectifying the steepest descent direction with the difference between the current iterative points and that between the gradients. It is proved that such a direction satisfies the approximate secant condition as well as the conjugacy condition. The strategies of acceleration and restart are incorporated into designing the algorithm to improve its numerical performance. Global convergence of the proposed algorithm is established under two mild assumptions. By implementing the algorithm to solve 75 benchmark test problems available in the literature, the obtained results indicate that the algorithm developed in this paper outperforms the existent similar state-of-the-art algorithms.     

An evolutionary algorithm with the partial sequential forward floating search mutation for large-scale feature selection problems

Several meta-heuristic algorithms, such as evolutionary algorithms (EAs) and genetic algorithms (GAs), have been developed for solving feature selection problems due to their efficiency for searching feature subset spaces in feature selection problems. Recently, hybrid GAs have been proposed to improve the performance of conventional GAs by embedding a local search operation, or sequential forward floating search mutation, into the GA. Existing hybrid algorithms may damage individuals’ genetic information obtained from genetic operations during the local improvement procedure because of a sequential process of the mutation operation and the local improvement operation. Another issue with a local search operation used in the existing hybrid algorithms is its inappropriateness for large-scale problems. Therefore, we propose a novel approach for solving large-sized feature selection problems, namely, an EA with a partial sequential forward floating search mutation (EAwPS). The proposed approach integrates a local search technique, that is, the partial sequential forward floating search mutation into an EA method. Two algorithms, EAwPS-binary representation (EAwPS-BR) for medium-sized problems and EAwPS-integer representation (EAwPS-IR) for large-sized problems, have been developed. The adaptation of a local improvement method into the EA speeds up the search and directs the search into promising solution areas. We compare the performance of the proposed algorithms with other popular meta-heuristic algorithms using the medium- and large-sized data sets. Experimental results demonstrate that the proposed EAwPS extracts better features within reasonable computational times.     

A Hybrid Descent Method for Global Optimization

In this paper, a hybrid descent method, consisting of a simulated annealing algorithm and a gradient-based method, is proposed. The simulated annealing algorithm is used to locate descent points for previously converged local minima. The combined method has the descent property and the convergence is monotonic. To demonstrate the effectiveness of the proposed hybrid descent method, several multi-dimensional non-convex optimization problems are solved. Numerical examples show that global minimum can be sought via this hybrid descent method.     

修正HS共轭梯度法在大规模信号重构问题中的应用

本义研究了压缩感知在大规模信号恢复问题中应用的问题.利用修正HS共轭梯度法及光滑化方法,获得了具有较好重构效果的算法.数值实验表明用修正HS共轭梯度法解决大规模信号恢复问题是可行的.