Shortest Path Auction Algorithm Without Contractions Using Virtual Source Concept

In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a virtual source.We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n ²), where n is the number of nodes.Numerical experimentsare reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches.     

Geometric Convergence Rates for Time-Sampled Markov Chains

We consider time-sampled Markov chain kernels, of the form P = _n n P ⁿ . We prove bounds on the total variation distance to stationarity of such chains. We are motivated by the analysis of near-periodic MCMC algorithms.     

Rational Functions with Prescribed Global and Local Minimizers

A family of multivariate rational functions is constructed. It has strong local minimizers with prescribed function values at prescribed positions. While there might be additional local minima, such minima cannot be global. A second family of multivariate rational functions is given, having prescribed global minimizers and prescribed interpolating data.     

Chaos in PDEs and Lax Pairs of Euler Equations

Recently, the author and collaborators have developed a systematic program for proving the existence of homoclinic orbits in partial differential equations. Two typical forms of homoclinic orbits thus obtained are: (1) transversal homoclinic orbits, (2) Silnikov homoclinic orbits. Around the transversal homoclinic orbits in infinite-dimensional autonomous systems, the author was able to prove the existence of chaos through a shadowing lemma. Around the Silnikov homoclinic orbits, the author was able to prove the existence of chaos through a horseshoe construction.Very recently, there has been a breakthrough by the author in finding Lax pairs for Euler equations of incompressible inviscid fluids. Further results have been obtained by the author and collaborators.     

A Quasi-Newton Penalty Barrier Method for Convex Minimization Problems

We describe an infeasible interior point algorithm for convex minimization problems. The method uses quasi-Newton techniques for approximating the second derivatives and providing superlinear convergence. We propose a new feasibility control of the iterates by introducing shift variables and by penalizing them in the barrier problem. We prove global convergence under standard conditions on the problem data, without any assumption on the behavior of the algorithm.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

IRK Methods for Index 2 and 3 DAEs: Starting Algorithms

When semi-explicit differential-algebraic equations are solved with implicit Runge-Kutta methods, the computational effort is dominated by the cost of solving the non-linear systems. That is why it is important to have good starting values to begin the iterations. In this paper we study a type of starting algorithms, without additional computational cost, in the case of index-2 and index-3 DAEs. The order of the starting values is defined, and by using DA-series and rooted trees we obtain their general order conditions. If the RK method satisfies some simplifying assumptions, then the maximum order can be obtained.     

On the Application of the Auxiliary Problem Principle

The auxiliary problem principle (APP) derives from a general theory on decomposition-coordination methods establishing a comprehensive framework for both one-level and two-level methods. In this paper, the results of the two-level methods of APP are specialized for an efficient application to some engineering problems.     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.