Efficient Algorithms for Large Scale Global Optimization: Lennard-Jones Clusters

A stochastic global optimization method is applied to the challenging problem of finding the minimum energy conformation of a cluster of identical atoms interacting through the Lennard-Jones potential. The method proposed incorporates within an already existing and quite successful method, monotonic basin hopping, a two-phase local search procedure which is capable of significantly enlarging the basin of attraction of the global optimum. The experiments reported confirm the considerable advantages of this approach, in particular for all those cases which are considered in the literature as the most challenging ones, namely 75, 98, 102 atoms. While being capable of discovering all putative global optima in the range considered, the method proposed improves by more than two orders of magnitude the speed and the percentage of success in finding the global optima of clusters of 75, 98, 102 atoms.     

Primal separation algorithms

Given an integer polyhedron , an integer point , and a point , the primal separation problem is the problem of finding a linear inequality which is valid for P _I , violated by x ^*, and satisfied at equality by . The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well-known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.Received: November 2002, Revised: March 2003,     

Cut sharing for multistage stochastic linear programs with interstage dependency

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms. Research leading to this work was partially supported by the Department of Energy Contract DE-FG03-92ER25116-A002; the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089; and the Electric Power Research Institute Contract RP 8010-09, CSA-4O05335. This author's work was supported in part by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem

Airline crew scheduling problem is a complex and difficult problem faced by all airline companies.To tackle this problem, it was often decomposed into two subproblems solved successively. First, the airline crew-pairing problem, which consists on finding a set of trips – called pairings – i.e. sequences of flights, starting and ending at a crew base, that cover all the flights planned for a given period of time. Secondly, the airline crew rostering problem, which consists on assigning the pairings found by solving the first subproblem, to the named airline crew members. For both problems, several rules and regulations must be respected and costs minimized.It is sure that this decomposition provides a convenient tool to handle the numerous and complex restrictions, but it lacks, however, of a global treatment of the problem. For this purpose, in this study we took the challenge of proposing a new way to solve both subproblems simultaneously. The proposed approach is based on a hybrid genetic algorithm. In fact, three heuristics are developed here to tackle the restriction rules within the GA’s process.     

Multi-objective Bayesian Artificial Immune System: Empirical Evaluation and Comparative Analyses

Recently, we have proposed a Multi-Objective Bayesian Artificial Immune System (MOBAIS) to deal effectively with building blocks (high-quality partial solutions coded in the solution vector) in combinatorial multi-objective problems. By replacing the mutation and cloning operators with a probabilistic model, more specifically a Bayesian network representing the joint distribution of promising solutions, MOBAIS takes into account the relationships among the variables of the problem, avoiding the disruption of already obtained high-quality partial solutions. The preliminary results have indicated that our proposal is able to properly build the Pareto front. Motivated by this scenario, this paper better formalizes the proposal and investigates its usefulness on more challenging problems. In addition, an important enhancement regarding the Bayesian network learning was incorporated into the algorithm in order to speed up its execution. To conclude, we compare MOBAIS with state-of-the-art algorithms taking into account quantitative aspects of the Pareto front found by the algorithms. MOBAIS outperforms the contenders in terms of the quality of the obtained solutions and requires an amount of computational resource inferior or compatible with the contenders.     

Necessary conditions for constrained optimization problems with semicontinuous and continuous data

We consider nonsmooth constrained optimization problems with semicontinuous and continuous data in Banach space and derive necessary conditions without constraint qualification in terms of smooth subderivatives and normal cones. These results, in different versions, are set in reflexive and smooth Banach spaces.

     

Convergence of the Augmented Lagrangian Method for Nonlinear Optimization Problems over Second-Order Cones

The paper analyzes the rate of local convergence of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Under the constraint nondegeneracy condition and the strong second order sufficient condition, we demonstrate that the sequence of iterate points generated by the augmented Lagrangian method locally converges to a local minimizer at a linear rate, whose ratio constant is proportional to 1/τ with penalty parameter τ not less than a threshold . Importantly and interestingly enough, the analysis does not require the strict complementarity condition. Supported by the National Natural Science Foundation of China under Project 10771026 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m × n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of long but straight continuous parts while the remaining curved part is relatively “short”. R. D. C. Monteiro was supported in part by NSF Grants CCR-0203113 and CCF-0430644 and ONR grant N00014-05-1-0183. T. Tsuchiya was supported in part by Japan-US Joint Research Projects of Japan Society for the Promotion of Science “Algorithms for linear programs over symmetric cones” and the Grants-in-Aid for Scientific Research (C) 15510144 of Japan Society for the Promotion of Science.     

Tensor Decomposition With Generalized Lasso Penalties

We present an approach for penalized tensor decomposition (PTD) that estimates smoothly varying latent factors in multiway data. This generalizes existing work on sparse tensor decomposition and penalized matrix decompositions, in a manner parallel to the generalized lasso for regression and smoothing problems. Our approach presents many nontrivial challenges at the intersection of modeling and computation, which are studied in detail. An efficient coordinate-wise optimization algorithm for PTD is presented, and its convergence properties are characterized. The method is applied both to simulated data and real data on flu hospitalizations in Texas and motion-capture data from video cameras. These results show that our penalized tensor decomposition can offer major improvements on existing methods for analyzing multiway data that exhibit smooth spatial or temporal features.     

乙烯醇锂的从头算研究

用限制的HF/3-21G和HF/6-31G^*优化乙烯醇锂的几种可能构型,比较了它们的稳定性.用限制的HF/3-1G,从乙醛开始,探讨了气相反应生成乙烯醇锂的机理,并在MP2水平上用6-31G^*基组计算了反应热.