Dual gradient method for linearly constrained,strongly convex,separable mathematical programming problems

A new dual gradient method is given to solve linearly constrained, strongly convex, separable mathematical programming problems. The dual problem can be decomposed into one-dimensional problems whose solutions can be computed extremely easily. The dual objective function is shown to have a Lipschitz continuous gradient, and therefore a gradient-type algorithm can be used for solving the dual problem. The primal optimal solution can be obtained from the dual optimal solution in a straightforward way. Convergence proofs and computational results are given.     

Asynchronous multisplitting methods for nonlinear fixed point problems

Our aim is to present for nonlinear problems asynchronous multisplitting algorithms including both the basic situation of O'Leary and White and the discrete analogue of Schwarz's alternating method and its multisubdomain extensions and moreover their two-stage counterparts. The analysis of these methods is based on El Tarazi’s convergence theorem for asynchronous iterations and leads to a good level of asynchronism in each of the considered situations. This revised version was published online in August 2006 with corrections to the Cover Date.     

A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series—parallel networks

We present strongly polynomial algorithms to find rational and integer flow vectors that minimize a convex separable quadratic cost function on two-terminal series—parallel graphs.     

Parallel Asynchronous Schwarz and Multisplitting Methods for a Nonlinear Diffusion Problem

Parallel asynchronous subdomain algorithms with flexible communication for the numerical solution of nonlinear diffusion problems are presented. The discrete maximum principle is considered and the Schwarz alternating method and multisplitting methods are studied. A connection is made with M-functions for a classical nonlinear diffusion problem. Finally, computational experiments carried out on a shared memory multiprocessor are presented and analyzed.     

Dual coordinate step methods for linear network flow problems

We review a class of recently-proposed linear-cost network flow methods which are amenable to distributed implementation. All the methods in the class use the notion of-complementary slackness, and most do not explicitly manipulate any global objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large number of newserial computational complexity results. We develop the basic theory of these methods and present two specific methods, the-relaxation algorithm for the minimum-cost flow problem, and theauction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N ³ logNC) and O(NA logNC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement-relaxation in a completely asynchronous, chaotic environment in which some processors compute faster than others, some processors communicate faster than others, and there can be arbitrarily large communication delays.Supported by Grant NSF-ECS-8217668 and by the Army Research Office under grant DAAL03-86-K-0171. Thanks are due to David Castañon, Paul Tseng, and Jim Orlin for their helpful comments.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Global search algorithms for minimum concave-cost network flow problems

We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure.     

A new class of asynchronous iterative algorithms with order intervals

This paper deals with a new class of parallel asynchronous iterative algorithms for the solution of nonlinear systems of equations. The main feature of the new class of methods presented here is the possibility of flexible communication between processors. In particular partial updates can be exchanged. Approximation of the associated fixed point mapping is also considered. A detailed convergence study is presented. A connection with the Schwarz alternating method is made for the solution of nonlinear boundary value problems. Computational results on a shared memory multiprocessor IBM 3090 are briefly presented.

     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

Minimum concave-cost network flow problems: Applications,complexity, and algorithms

We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach.     

Prim-based support-graph preconditioners for min-cost flow problems

Support-graph preconditioners have been shown to be a valuable tool for the iterative solution, via a Preconditioned Conjugate Gradient method, of the KKT systems that must be solved at each iteration of an Interior Point algorithm for the solution of Min Cost Flow problems. These preconditioners extract a proper triangulated subgraph, with “large” weight, of the original graph: in practice, trees and Brother-Connected Trees (BCTs) of depth two have been shown to be the most computationally efficient families of subgraphs. In the literature, approximate versions of the Kruskal algorithm for maximum-weight spanning trees have most often been used for choosing the subgraphs; Prim-based approaches have been used for trees, but no comparison have ever been reported. We propose Prim-based heuristics for BCTs, which require nontrivial modifications w.r.t. the previously proposed Kruskal-based approaches, and present a computational comparison of the different approaches, which shows that Prim-based heuristics are most often preferable to Kruskal-based ones. This paper has been partially supported by the UE Marie Curie Research Training Network no. 504438 ADONET.     

Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems

We develop an iterative algorithm based on right-hand side decomposition for the solution of multicommodity network flow problems. At each step of the proposed iterative procedure the coupling constraints are eliminated by subdividing the shared capacity resource among the different commodities and a master problem is constructed which attempts to improve sharing of the resources at each iteration.As the objective function of the master problem is nonsmooth, we apply to it a new optimization technique which does not require the exact solutions of the single commodity flow subproblems. This technique is based on the notion of - subgradients instead of subgradients and is suitable for parallel implementation. Extensions to the nonlinear, convex separable case are also discussed.The work of this author has been supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410.     

Function-space quasi-Newton algorithms for optimal control problems with bounded controls and singular arcs

Two existing function-space quasi-Newton algorithms, the Davidon algorithm and the projected gradient algorithm, are modified so that they may handle directly control-variable inequality constraints. A third quasi-Newton-type algorithm, developed by Broyden, is extended to optimal control problems. The Broyden algorithm is further modified so that it may handle directly control-variable inequality constraints. From a computational viewpoint, dyadic operator implementation of quasi-Newton methods is shown to be superior to the integral kernel representation. The quasi-Newton methods, along with the steepest descent method and two conjugate gradient algorithms, are simulated on three relatively simple (yet representative) bounded control problems, two of which possess singular subarcs. Overall, the Broyden algorithm was found to be superior. The most notable result of the simulations was the clear superiority of the Broyden and Davidon algorithms in producing a sharp singular control subarc.This research was supported by the National Science Foundation under Grant Nos. GK-30115 and ENG 74-21618 and by the National Aeronautics and Space Administration under Contract No. NAS 9-12872.     

Local optimality conditions for multicommodity flow problems with separable piecewise convex costs

We consider here a multicommodity flow network optimization problem with non-convex but piecewise convex arc cost functions. We derive complete optimality conditions for local minima based on negative-cost cycles associated with each commodity. These conditions do not extend to the convex non-smooth case.     

Parallel Asynchronous Algorithms for the K Shortest Paths Problem

We deal with the problem of computing in parallel the first K shortest paths from a single origin node to all other nodes of a directed graph. Our approach is based on a very easy way to introduce parallelism in the typical sequential label-correcting method. We describe formally an asynchronous method defined on a shared-memory parallel computational model, and we prove its theoretical correctness under very weak assumptions. According to different strategies used to implement the generic method, we propose several parallel label-correcting algorithms, and we analyze the numerical performance of the resulting codes on a nonuniform memory access multiprocessor via computational results collected on random generated networks. The advantage of parallelism is significant for very large-scale problems of practical interest.     

Parallel initial-value algorithms for singularly perturbed boundary-value problems

Initial-value methods for linear and semilinear singularly perturbed boundary-value problems are examined with a view to designing and implementing algorithms on parallel architectures. Practical experiments on a CRAY Y-MP 8/432 multiprocessor have been performed, showing the reliability and performance of several proposed parallel schemes.This work was supported by CNR, Rome, Italy (Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo, Sottoprogetto 1).The authors wish to thank Dr. A. Papini, who carried out most of the computations reported in this work.     

Randomized and quantum algorithms yield a speed-up for initial-value problems

Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration and approximation problems, for which a speed-up is shown in many important cases by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper, we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem.     

Conjugate gradient predictor corrector method for solving large scale problems

In this paper, we give a new method for solving large scale problems. The basic idea of this method depends on implementing the conjugate gradient as a corrector into a continuation method. We use the Euler method as a predictor. Adaptive steplength control is used during the tracing of the solution curve. We present some of our experimental examples to demonstrate the efficiency of the method.

     

Application of the alternating direction method of multipliers to separable convex programming problems

This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established.