Papers, Reports, Slides, and Other Material by Dimitri Bertsekas

Course Lecture Slides, Survey Papers, Most Recent Research papers, Selected Research papers, Complete List of Publications, Links to All Books

COURSE LECTURE SLIDES

Dynamic Programming and Optimal Control, Lecture Slides for MIT course 6.231.

Nonlinear Programming, Lecture Slides for MIT course 6.252.

Convex Analysis and Optimization, 2003, Lecture Slides for MIT course 6.253, Fall 2003. Slides of an overview lecture.

Convex Optimization Theory, 2007 Lecture Slides for MIT course 6.253, Fall 2007.

Ten Simple Rules for Mathematical Writing, Tutorial lecture on writing engineering/mathematics papers and books.

SURVEY AND EXPOSITORY ARTICLES

D. P. Bertsekas, "Auction Algorithms," Encyclopedia of Optimization, Kluwer, 2001.

Abstract: An 8-page expository article providing orientation, references, and a summary overview of the subject, as given in the author's book "Network Optimization: Continuous and Discrete Models," Athena Scientific, 1998.

D. P. Bertsekas, "Auction Algorithms for Network Flow Problems: A Tutorial Introduction," Computational Optimization and Applications, Vol. 1, pp. 7-66, 1992.

Abstract: An extensive tutorial paper that surveys auction algorithms, a comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a real auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.

D. P. Bertsekas, "Neuro-Dynamic Programming," Encyclopedia of Optimization, Kluwer, 2001.

Abstract: A 9-page expository article providing orientation, references, and a summary overview of the subject, as given in the book "Neuro-Dynamic Programming," by D. P. Bertsekas and J. N. Tsitsiklis, Athena Scientific, 1996. You may also find helpful the following introductory slide presentation: "Neuro-Dynamic Programming: An Overview"

D. P. Bertsekas, and S. E. Shreve, "Mathematical Issues in Dynamic Programming," an overview paper, 1997.

Abstract: An expository paper that provides orientation on the central mathematical issues for a comprehensive and rigorous theory of dynamic programming and stochastic control, as given in the authors' book "Stochastic Optimal Control: The Discrete-Time Case," Academic Press, 1978 (republished by Athena Scientific, 1996).

D. P. Bertsekas, "Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC," in Fundamental Issues in Control, European J. of Control, Vol. 11, Nos. 4-5, 2005; From 2005 CDC, Seville, Spain.

Abstract: We survey selectively the field of approximate dynamic programming (ADP), with a particular emphasis on two recent directions of research: rollout algorithms and model predictive control (MPC). We argue that while motivated by different concerns, these two methodologies are closely connected, and the mathematical essence of their desirable properties (cost improvement and stability, respectively) is couched on the central dynamic programming idea of policy iteration. In particular, among other things, we show that the most common MPC schemes can be viewed as rollout algorithms or one-step policy iteration methods. Furthermore, we embed rollout and MPC within a new unifying suboptimal control framework, based on a concept of restricted or constrained structure policies, which contains these schemes as special cases. (Lecture Slides)

RESEARCH PAPERS

Most Recent Papers

Selected papers on Dynamic and Neuro-Dynamic Programming

Selected papers on Nonlinear Programming and Optimization Applications

Selected papers on Network Optimization

Selected papers on Parallel and Distributed Algorithms

Selected papers on Set-Membership Estimation and Control

Top Menu

Most Recent Papers

D. P. Bertsekas and H. Yu, "Projected Equation Methods for Approximate Solution of Large Linear Systems," to appear in Journal of Computational and Applied Mathematics.

Abstract: We consider linear systems of equations and solution approximations derived by projection on a low-dimensional subspace. We propose stochastic iterative algorithms, based on simulation, which converge to the approximate solution and are suitable for very large-dimensional problems. The algorithms are extensions of recent approximate dynamic programming methods, known as temporal difference methods, which solve a projected form of Bellman's equation by using simulation-based approximations to this equation, or by using a projected value iteration method. (Related Lecture Slides)

A. Nedich and D. P. Bertsekas, "The Effect of Deterministic Noise in Subgradient Methods," Lab. for Information and Decision Systems Report, MIT, September 2007.

Abstract: In this paper, we study the influence of noise on subgradient methods for convex constrained optimization. The noise may be due to various sources, and is manifested in inexact computation of the subgradients. Assuming that the noise is deterministic and bounded, we discuss the convergence properties for two cases: the case where the constraint set is compact, and the case where this set need not be compact but the objective function has a sharp set of minima (for example the function is polyhedral). In both cases, using several different stepsize rules, we prove convergence to the optimal value within some tolerance that is given explicitly in terms of the subgradient errors. In the first case, the tolerance is nonzero, but in the second case, somewhat surprisingly, the optimal value can be obtained exactly, provided the size of the error in the subgradient computation is below some threshold. We then extend these results to objective functions that are the sum of a large number of convex functions, in which case an incremental subgradient method can be used.

H. Yu and D. P. Bertsekas, "Q-Learning Algorithms for Optimal Stopping Based on Least Squares," Proc. European Control Conference 2007, Kos, Greece, July 2007.

Abstract: We consider the solution of discounted optimal stopping problems using linear function approximation methods. A $Q$-learning algorithm for such problems, proposed by Tsitsiklis and Van Roy, is based on the method of temporal differences and stochastic approximation. We propose alternative algorithms, which are based on projected value iteration ideas and least squares. We prove the convergence of some of these algorithms and discuss their properties. (Related Lecture Slides)

D. P. Bertsekas and H. Yu, "Solution of Large Systems of Equations Using Approximate Dynamic Programming Methods," Lab. for Information and Decision Systems Report 2754, MIT, June 2007.

Abstract: We consider fixed point equations, and approximation of the solution by projection on a low-dimensional subspace. We propose stochastic iterative algorithms, based on simulation, which converge to the approximate solution and are suitable for large-dimensional problems. We focus primarily on general linear systems and propose extensions of recent approximate dynamic programming methods, based on the use of temporal differences, which solve a projected form of Bellman's equation by using simulation-based approximations to this equation, or by using a projected value iteration method. (Related Lecture Slides)

H. Yu and D. P. Bertsekas, "A Least Squares Q-Learning Algorithm for Optimal Stopping Problems," Lab. for Information and Decision Systems Report 2731, MIT, February 2007 (revised June 2007).

Abstract: We consider the solution of discounted optimal stopping problems using linear function approximation methods. A Q-learning algorithm for such problems, proposed by Tsitsiklis and Van Roy, is based on the method of temporal differences and stochastic approximation. We propose alternative algorithms, which are based on projected value iteration ideas and least squares. We prove the convergence of some of these algorithms and discuss their properties. (Related Lecture Slides)

D. P. Bertsekas and J. N. Tsitsiklis, "Comment on Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules," Lab. for Information and Decision Systems Report, MIT, June 2006; IEEE Trans. on Aut. Control, Vol. 52, pp. 968-969, 2007.

Abstract: We clarify the relation of the model and the convergence results of Jadbabaie et al. [3] to those studied by Bertsekas et al. [6, 5, 1]. We show that the update equations in [3] are a very special case of those in [5]. Furthermore, the main convergence results in [3] are special cases of those in [5], except for a small difference in the connectivity assumptions which, however, does not affect the proof.

H. Yu and D. P. Bertsekas, "On Near-Optimality of the Set of Finite-State Controllers for Average Cost POMDP," Lab. for Information and Decision Systems Report 2689, MIT, April 2006; to appear in Math. of Operations Research.

Abstract: We consider the average cost problem for partially observable Markov decision processes (POMDP) with finite state, observation, and control spaces. We prove that there exists an $\epsilon$-optimal finite-state controller functionally independent of initial distributions for any $\epsilon > 0$, under the assumption that the optimal liminf average cost function of the POMDP is constant. As part of our proof, we establish that if the optimal liminf average cost function is constant, then the optimal limsup average cost function is also constant, and the two are equal. We also discuss the connection between the existence of nearly optimal finite-history controllers and two other important issues for average cost POMDP: the existence of an average cost that is independent of the initial state distribution, and the existence of a bounded solution to the constant average cost optimality equation. (Related slide presentation)

H. Yu and D. P. Bertsekas, "Convergence Results for Some Temporal Difference Methods Based on Least Squares," Lab. for Information and Decision Systems Report 2697, MIT, June 2006; revised 2007.

Abstract: We consider finite-state Markovian Decision Problems and prove convergence and rate of convergence results for certain least squares policy evaluation algorithms. These are temporal difference methods for constructing a linear function approximation of the cost function of a stationary policy, within the context of infinite-horizon discounted and average cost dynamic programming. We introduce an average cost method, patterned after the discounted cost method, which uses a constant stepsize, and we prove its convergence. We also show that the convergence rate of both the discounted and the average cost methods is optimal within the class of temporal difference methods. Analysis and experiment indicate that our methods are substantially and often dramatically faster than TD(Lambda), as well as more reliable. (Related slide presentation)

D. P. Bertsekas, "Extended Monotropic Programming and Duality," Lab. for Information and Decision Systems Report 2692, MIT, March 2006 (revised March 2007), to appear in JOTA.

Abstract: We consider the separable problem of minimizing $\sum_{i=1}^mf_{i}(x_{i})$ subject to $x\in S$, where $x_i$ are multidimensional subvectors of $x$, $f_i$ are convex functions, and $S$ is a subspace. Monotropic programming, extensively studied by Rockafellar, is the special case where the subvectors $x_i$ are the scalar components of $x$. We show a strong duality result that parallels Rockafellar's result for monotropic programming, and contains other known and new results as special cases. The proof is based on the use of $\e$-subdifferentials and the $\e$-descent method, which is used here as an analytical vehicle.

D. P. Bertsekas, "Separable Dynamic Programming and Approximate Decomposition Methods," Lab. for Information and Decision Systems Report 2684, MIT, Feb. 2006; IEEE Trans. on Aut. Control, Vol. 52, 2007, pp. 911-916.

Abstract: We consider control, planning, and resource allocation problems involving several independent subsystems that are coupled through a control/decision constraint. We discuss one-step lookahead methods that use an approximate cost-to-go function derived from the solution of single subsystem problems. We propose a new method for constructing such approximations, and derive bounds on the performance of the associated suboptimal policies. We then specialize this method to problems of reachability of target tubes that have the form of a box (a Cartesian product of subsystem tubes). This yields inner approximating tubes, which have the form of a union of a finite number of boxes, each involving single subsystem calculations.

D. P. Bertsekas, "Rollout Algorithms for Constrained Dynamic Programming," Lab. for Information and Decision Systems Report 2646, MIT, April 2005.

Abstract: The rollout algorithm is a suboptimal control method for deterministic and stochastic problems that can be solved by dynamic programming. In this short note, we derive an extension of the rollout algorithm that applies to constrained deterministic dynamic programming problems, and relies on a suboptimal policy, called base heuristic. Under suitable assumptions, we show that if the base heuristic produces a feasible solution, the rollout algorithm also produces a feasible solution, whose cost is no worse than the cost corresponding to the base heuristic.

D. P. Bertsekas, and P. Tseng, "Set Intersection Theorems and Existence of Optimal Solutions," Lab. for Information and Decision Systems Report 2628, MIT, Nov. 2004; revised August 2005; Math. Programming J., Vol. 110, 2007 pp. 287-314.

Abstract: The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We introduce the new notion of an asymptotic direction of a sequence of closed sets, and the associated notions of retractive, horizon, and critical directions, and we provide several conditions that guarantee the nonemptiness of the corresponding intersection. We show how these conditions can be used to obtain simple proofs of some known results on existence of optimal solutions, and to derive some new results, including an extension of the Frank-Wolfe Theorem for (nonconvex) quadratic programming. (Related Slide Presentation)

D. P. Bertsekas, "Lagrange Multipliers with Optimal Sensitivity Properties in Constrained Optimization," Lab. for Information and Decision Systems Report 2632, MIT, October 2004; in Proc. of the 2004 Erice Workshop on Large Scale Nonlinear Optimization, Erice, Italy, Kluwer, 2005.

We consider optimization problems with inequality and abstract set constraints, and we derive sensitivity properties of Lagrange multipliers under very weak conditions. In particular, we do not assume uniqueness of a Lagrange multiplier or continuity of the perturbation function. We show that the Lagrange multiplier of minimum norm defines the optimal rate of improvement of the cost per unit constraint violation. (Related Slide Presentation)

D. P. Bertsekas, A. E. Ozdaglar, and P. Tseng, "Enhanced Fritz John Conditions for Convex Programming," Lab. for Information and Decision Systems Report 2631, MIT, July 2004; SIAM J. on Optimization, Vol. 16, 2006, p. 766.

Abstract: We consider convex constrained optimization problems, and we enhance the classical Fritz John optimality conditions to assert the existence of multipliers with special sensitivity properties. In particular, we prove the existence of Fritz John multipliers that are informative in the sense that they identify constraints whose relaxation, at rates proportional to the multipliers, strictly improves the primal optimal value. Moreover, we show that if the set of geometric multipliers is nonempty, then the minimum-norm vector of this set is informative, and defines the optimal rate of cost improvement per unit constraint violation. Our assumptions are very general, and do not include the absence of duality gap or the existence of optimal solutions. In particular, for the case where there is a duality gap, we establish enhanced Fritz John conditions involving the dual optimal value and dual optimal solutions.

H. Yu, and D. P. Bertsekas, "Discretized Approximations for POMDP with Average Cost," The 20th Conference on Uncertainty in Artificial Intelligence, 2004, Banff, Canada.

Abstract: In this paper, we propose a new lower approximation scheme for POMDP with discounted and average cost criterion. The approximating functions are determined by their values at a finite number of belief points, and can be computed efficiently using value iteration algorithms for finite-state MDP. While for discounted problems several lower approximation schemes have been proposed earlier, ours seems the first of its kind for average cost problems. We focus primarily on the average cost case, and we show that the corresponding approximation can be computed efficiently using multi-chain algorithms for finite-state MDP. We give a preliminary analysis showing that regardless of the existence of the optimal average cost in the POMDP, the approximation obtained is a lower bound of the liminf optimal average cost function, and can also be used to calculate an upper bound on the limsup optimal average cost function, as well as bounds on the cost of executing the stationary policy associated with the approximation. We show the convergence of the cost approximation, when the optimal average cost is constant and the optimal differential cost is continuous.

D. P. Bertsekas, V. Borkar, and A. Nedic, "Improved Temporal Difference Methods with Linear Function Approximation," in "Learning and Approximate Dynamic Programming", by A. Barto, W. Powell, J. Si, (Eds.), IEEE Press, 2004, pp. 231-255.

Abstract: We consider temporal difference algorithms within the context of infinite-horizon finite-state dynamic programming problems with discounted cost, and linear cost function approximation. We show, under standard assumptions, that a least squares-based temporal difference method, proposed by Nedic and Bertsekas [NeB03], converges with a stepsize equal to 1. To our knowledge, this is the first iterative temporal difference method that converges without requiring a diminishing stepsize. We discuss the connections of the method with Sutton's TD(Lambda) and with various versions of least-squares based value iteration, and we show via analysis and experiment that the method is substantially and often dramatically faster than TD(Lambda), as well as simpler and more reliable. We also discuss the relation of our method with the LSTD method of Boyan [Boy02], and Bradtke and Barto [BrB96]. You may also find helpful the following slide presentation.

A. E. Ozdaglar and D. P. Bertsekas, "The Relation Between Pseudonormality and Quasiregularity in Constrained Optimization," Optimization Methods and Software, Vol. 19, 2004, pp. 493--506.

Abstract: We consider optimization problems with equality, inequality, and abstract set constraints. We investigate the relations between various characteristics of the constraint set that imply the existence of Lagrange multipliers. For problems with no abstract set constraint, the classical condition of quasiregularity provides the connecting link between the most common constraint qualifications and existence of Lagrange multipliers. In earlier work, we introduced a new and general condition, pseudonormality, that is central within the theory of constraint qualifications, exact penalty functions, and existence of Lagrange multipliers. In this paper, we explore the relations between pseudonormality, quasiregularity, and existence of Lagrange multipliers in the presence of an abstract set constraint. In particular, under a regularity assumption on the abstract constraint set, we show that pseudonormality implies quasiregularity. However, contrary to pseudonormality, quasiregularity does not imply the existence of Lagrange multipliers, except under additional assumptions.

A. E. Ozdaglar and D. P. Bertsekas, "Optimal Solution of Integer Multicommodity Flow Problems with Application in Optical Networks," Proc. of Symposium on Global Optimization, Santorini, Greece, June 2003; Frontiers in global optimization, pp. 411--435, Nonconvex Optim. Appl., 74, Kluwer Acad. Publ., Boston, MA, 2004.

Abstract: In this paper, we propose methods for solving broadly applicable integer multicommodity flow problems. We focus in particular on the problem of routing and wavelength assignment (RWA), which is critically important for increasing the efficiency of wavelength-routed all-optical networks. Our methodology can be applied as a special case to the problem of routing in a circuit-switched network. We discuss an integer-linear programming formulation, which can be addressed with highly efficient linear (not integer) programming methods, to obtain optimal or nearly optimal solutions. Note: A comparative computational evaluation of the methodology of this paper is given in the thesis by Ali Meli.

Lecture Slides, Survey Papers, Research papers, Top Menu

Dynamic and Neuro-Dynamic Programming

D. P. Bertsekas and H. Yu, "Projected Equation Methods for Approximate Solution of Large Linear Systems," to appear in Journal of Computational and Applied Mathematics (posted Feb. 2008).

D. P. Bertsekas and H. Yu, "Solution of Large Systems of Equations Using Approximate Dynamic Programming Methods," Lab. for Information and Decision Systems Report 2754, MIT, June 2007.

H. Yu and D. P. Bertsekas, "Q-Learning Algorithms for Optimal Stopping Based on Least Squares," to appear in Proc. European Control Conference 2007, Kos, Greece, July 2007.

H. Yu and D. P. Bertsekas, "A Least Squares Q-Learning Algorithm for Optimal Stopping Problems," Lab. for Information and Decision Systems Report 2731, MIT, February 2007 (revised June 2007).

H. Yu and D. P. Bertsekas, "Convergence Results for Some Temporal Difference Methods Based on Least Squares," Lab. for Information and Decision Systems Report 2697, MIT, June 2006.

D. P. Bertsekas, "Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC," Report LIDS 2632, May 2005; to appear in Proc. of 2005 CDC, Seville, Spain.

D. P. Bertsekas, "Rollout Algorithms for Constrained Dynamic Programming," Lab. for Information and Decision Systems Report 2646, MIT, April 2005.

H. Yu, and D. P. Bertsekas, "Discretized Approximations for POMDP with Average Cost," The 20th Conference on Uncertainty in Artificial Intelligence, 2004, Banff, Canada.

A. Nedic and D. P. Bertsekas, "Least-Squares Policy Evaluation Algorithms with Linear Function Approximation," LIDS Report LIDS-P-2537, Dec. 2001; J. of Discrete Event Systems, Vol. 13, 2003, pp. 79-110.

Abstract: We consider two policy evaluation methods for discounted dynamic programming, which use simulation, temporal differences, and linear cost function approximation. The first method is a new gradient-like algorithm involving least-squares subproblems and a diminishing stepsize, which is based on the lambda-policy iteration method of Bertsekas and Ioffe. The second method is the LSTD(lambda) algorithm recently proposed by Boyan, which for lambda=0 coincides with the linear least-squares temporal-difference algorithm of Bradtke and Barto. At present, there is only a convergence result by Bradtke and Barto for the LSTD(0) algorithm. Here, we strengthen this result by showing the convergence of LSTD(lambda), with probability 1, for every lambda in [0,1].

C. C. Wu and D. P. Bertsekas, "Admission Control for Wireless Networks,"IEEE Trans. on Vehicular Technology, to appear.

Abstract: With the population of wireless subscribers increasing at a rapid rate, overloaded situations are likely to become an increasing problem. Admission control can be used to balance the goals of maximizing bandwidth utilization and ensuring sufficient resources for high priority events. In this paper, we formulate the admission control problem as a Markov decision problem. While dynamic programming can be used to solve such problems, the large size of the state space makes this impractical. We propose an approximate dynamic programming technique, which involves creating an approximation of the original model with a state space sufficiently small so that dynamic programming can be applied. Our results show that the method improves significantly on policies that are generally in use, in particular, the greedy policy and the reservation policy. Much of the computation required for our method can be done off-line, and the real-time computation required is easily distributed between the cells.

D. P. Bertsekas and D. A. Castanon, "Rollout Algorithms for Stochastic Scheduling Problems," J. of Heuristics, Vol. 5, 1999, pp. 89-108.

Abstract: Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, and we delineate circumstances under which they are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.

D. P. Bertsekas, M. L. Homer, D. A. Logan, S. D. Patek, and N. R. Sandell, "Missile Defense and Interceptor Allocation by Neuro-Dynamic Programming," IEEE Trans. on Systems, Man, and Cybernetics, 1999.

Abstract: The purpose of this paper is to propose a solution methodology for a missile defense problem involving the sequential allocation of defensive resources over a series of engagements. The problem is cast as a dynamic programming/Markovian decision problem, which is computationally intractable by exact methods because of its large number of states and its complex modeling issues. We have employed a Neuro-Dynamic Programming (NDP) framework, whereby the cost-to-go function is approximated using neural network architectures that are trained on simulated data. We report on the performance obtained using several different training methods, and we compare this performance with the optimal.

J. Abounadi, D. Bertsekas, and V. Borkar, "Learning Algorithms for Markov Decision Processes," Report LIDS-P-2434, Lab. for Info. and Decision Systems, 1998; SIAM J. on Control and Optimization, Vol. 40, 2001, pp. 681-698.

Abstract: This paper gives the first rigorous convergence analysis of analogs of Watkins' Q-learning algorithm, applied to average cost control of finite-state Markov chains. We discuss two algorithms which may be viewed as stochastic approximation counterparts of two existing algorithms for recursively computing the value function of average cost problem - the traditional relative value iteration algorithm and a recent algorithm of Bertsekas based on the stochastic shortest path (SSP) formulation of the problem. Both synchronous and asynchronous implementations are considered and are analyzed using the ``ODE" method. This involves establishing asymptotic stability of associated ODE limits. The SSP algorithm also uses ideas from two time scale stochastic approximation.

J. Abounadi, D. Bertsekas, and V. Borkar, "Stochastic Approximation for Non-Expansive Maps: Q-Learning Algorithms," Report LIDS-P-2433, Lab. for Info. and Decision Systems, 1998; SIAM J. on Control and Optimization, Vol. 41, 2002, pp. 1-22.

Abstract: We discuss synchronous and asynchronous variants of fixed point iterations of the form x^{k+1} = x^k + \gamma(k) \bl(F(x^k,w^k)-x^k\br), where F is a non-expansive mapping under a suitable norm, and {w^k} is a stochastic sequence. These are stochastic approximation iterations that can be analyzed using the ODE approach based either on Kushner and Clark's Lemma for the synchronous case or Borkar's Theorem for the asynchronous case. However, the analysis requires that the iterates {x^k} are bounded, a fact which is usually hard to prove. We develop a novel framework for proving boundedness, which is based on scaling ideas and properties of Lyapunov functions. We then combine the boundedness property with Borkar's stability analysis of ODE's involving non-expansive mappings to prove convergence with probability 1. We also apply our convergence analysis to Q-learning algorithms for stochastic shortest path problems and we are able to relax some of the assumptions of the currently available results.

S. D. Patek and D. P. Bertsekas, "Stochastic Shortest Path Games," SIAM J. on Control and Optimization, Vol. 36, 1999, pp. 804-824.

Abstract: We consider dynamic, two-player, zero-sum games where the "minimizing" player seeks to drive an underlying finite-state dynamic system to a special terminal state along a least expected cost path. The "maximizer" seeks to interfere with the minimizer's progress so as to maximize the expected total cost. We consider, for the frst time, undiscounted finite-state problems, with compact action spaces, and transition costs that are not strictly positive. We admit that there are policies for the minimizer which permit the maximizer to prolong the game indefinitely. Under assumptions which generalize deterministic shortest path problems, we establish (i) the existence of a real-valued equilibrium cost vector achievable with stationary policies for the opposing players and (ii) the convergence of value iteration and policy iteration to the unique solution of Bellman's equation.

D. P. Bertsekas, "A New Value Iteration Method for the Average Cost Dynamic Programming Problem," SIAM J. on Control and Optimization, Vol. 36, 1998, pp. 742-759.

Abstract: We propose a new value iteration method for the classical average cost Markovian Decision problem, under the assumption that all stationary policies are unichain and furthermore there exists a state that is recurrent under all stationary policies. This method is motivated by a relation between the average cost problem and an associated stochastic shortest path problem. Contrary to the standard relative value iteration, our method involves a weighted sup norm contraction and for this reason it admits a Gauss-Seidel implementation. Computational tests indicate that the Gauss-Seidel version of the new method substantially outperforms the standard method for difficult problems.

D. P. Bertsekas, "Differential Training of Rollout Policies," Proc. of the 35th Allerton Conference on Communication, Control, and Computing, Allerton Park, Ill., October 1997.

Abstract: We consider the approximate solution of stochastic optimal control problems using a neuro-dynamic programming/reinforcement learning methodology. We focus on the computation of a rollout policy, which is obtained by a single policy iteration starting from some known base policy and using some form of exact or approximate policy improvement. We indicate that, in a stochastic environment, the popular methods of computing rollout policies are particularly sensitive to simulation and approximation error, and we present more robust alternatives, which aim to estimate relative rather than absolute Q-factor and cost-to-go values. In particular, we propose a method, called differential training, that can be used to obtain an approximation to cost-to-go differences rather than cost-to-go values by using standard methods such as TD(lambda) and lambda-policy iteration. This method is suitable for recursively generating rollout policies in the context of simulation-based policy iteration methods.

D. P. Bertsekas, J. N. Tsitsiklis, and C. Wu, "Rollout Algorithms for Combinatorial Optimization," J. of Heuristics, Vol. 3, 1997, pp. 245-262.

Abstract: We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential application. In particular, we embed the problem within a dynamic programming framework, and we introduce several types of rollout algorithms, which are related to notions of policy iteration. We provide conditions guaranteeing that the rollout algorithm improves the performance of the original heuristic algorithm. The method is illustrated in the context of a machine maintenance and repair problem.

D. P. Bertsekas and S. Ioffe, "Temporal Differences-Based Policy Iteration and Applications in Neuro-Dynamic Programming," Report LIDS-P-2349, Lab. for Information and Decision Systems, MIT, 1996.

Abstract: We consider a new policy iteration method for dynamic programming problems with discounted and undiscounted cost. The method is based on the notion of temporal differences, and is primarily geared to the case of large and complex problems where the use of approximations is essential. We develop the theory of these methods without approximation, we describe how to embed them within a neuro-dynamic programming/reinforcement learning context where feature-based approximation architectures are used, we relate them to TD(Lambda) methods, and we illustrate their use in the training of a tetris playing program.

D. P. Bertsekas, L. C. Polymenakos, and J. N. Tsitsiklis, "Efficient Algorithms for Continuous-Space Shortest Path Problems," IEEE Transactions on Automatic Control, Vol. 43, 1998, pp. 278-283.

Abstract: We consider a continuous-space shortest path problem in a two-dimensional plane. This is the problem of finding a trajectory that starts at a given point, ends at the boundary of a compact set, and minimizes a cost function of the form $\int_0^Tr(x(t))dt+q(x(T)).$ For a discretized version of this problem, a Dijkstra-like method that requires one iteration per discretization point has been developed by Tsitsiklis. Here we develop some new label correcting-like methods based on the Small Label First methods of Bertsekas. We prove the finite termination of these methods, and we present computational results showing that they are competitive and often superior to the Dijkstra-like method, and are also much faster than the traditional Jacobi and Gauss-Seidel methods.

S. D. Patek and D. P. Bertsekas,"Play Selection in American Football: a Case Study in Neuro-Dynamic Programming", Chapter 7 in Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search: Interfaces in Computer Science and Operations Research, David L. Woodruff, editor. Kluwer Academic Publishers, Boston, 1997.

Abstract: We present a computational case study of neuro-dynamic program- ming, a recent class of reinforcement learning methods. We cast the problem of play selection in American football as a stochastic shortest path Markov Decision Problem (MDP). In particular, we consider the problem faced by a quarterback in attempting to maximize the net score of an offensive drive. The resulting optimization problem serves as a medium-scale testbed for numerical algorithms based on policy iteration. The algorithms we consider evolve as a sequence of approximate policy eval- uations and policy updates. An (exact) evaluation amounts to the computation of the reward-to-go function associated with the policy in question. Approxi- mations of reward-to-go are obtained either as the solution or as a step toward the solution of a training problem involving simulated state/reward data pairs. Within this methodological framework there is a great deal of flexibility. In specifying a particular algorithm, one must select a parametric form for esti- mating the reward-to-go function as well as a training algorithm for tuning the approximation. One example we consider, among many others, is the use of a multilayer perceptron (i.e. neural network) which is trained by backpropaga- tion. The objective of this paper is to illustrate the application of neuro-dynamic programming methods in solving a well-defined optimization problem. We will contrast and compare various algorithms mainly in terms of performance, al- though we will also consider complexity of implementation. Because our version of football leads to a medium-scale Markov decision problem, it is possible to compute the optimal solution numerically, providing a yardstick for meaningful comparison of the approximate methods.

B. Van Roy, D. P. Bertsekas, Y. Lee, and J. N. Tsitsiklis, "A Neuro-Dynamic Programming Approach to Retailer Inventory Management," Lab. for Information and Decision Systems Report, Nov. 1996.

Abstract: We present a model of two echelon retailer inventory systems, and we cast the problem of generating optimal control strategies into the framework of dynamic programming. We formulate two specific case studies for which the underlying dynamic programming problems involve thirty three and forty six state variables, respectively. Because of the enormity of these state spaces, classical algorithms of dynamic programming are inapplicable. To address these complex problems we develop approximate dynamic programming algorithms. The algorithms are motivated by recent research in artificial intelligence involving simulation-based methods and neural network approximations, and they are representative of algorithms studied in the emerging field of neuro dynamic programming. We assess performance of resulting solutions relative to optimized s-type ("order-up-to" policies), which are generally accepted as reasonable heuristics for the types of problems we consider. In both case studies, we are able to generate control strategies substantially superior to the heuristics, reducing inventory costs by approximately ten percent.

D. P. Bertsekas, F. Guerriero, and R. Musmanno, "Parallel Asynchronous Label Correcting Methods for Shortest Paths," J. of Optimization Theory and Applications, Vol. 88, 1996, pp. 297-320.

Abstract: In this paper we develop parallel asynchronous implementations of some known and some new label correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.

D. P. Bertsekas, "Generic Rank One Corrections for Value Iteration in Markovian Decision Problems," Operations Research Letters, Vol. 17, 1995, pp. 111-119.

Abstract: Given a linear iteration of the form $x:=F(x)$, we consider modified versions of the form $x:=F(x+\g d)$, where $d$ is a fixed direction, and $\g$ is chosen to minimize the norm of the residual $\|x+\g d-F(x+\g d)\|$. We propose ways to choose $d$ so that the convergence rate of the modified iteration is governed by the subdominant eigenvalue of the original. In the special case where $F$ relates to a Markovian decision problem, we obtain a new extrapolation method for value iteration. In particular, our method accelerates the Gauss-Seidel version of the value iteration method for discounted problems in the same way that MacQueen's error bounds accelerate the standard version. Furthermore, our method applies equally well to Markov Renewal and undiscounted problems.

D. P. Bertsekas, "A Counterexample to Temporal Difference Learning," Neural Computation, Vol. 7, 1995, pp. 270-279.

Abstract: Sutton's TD($\l$) method aims to provide a representation of the cost function in an absorbing Markov chain with transition costs. A simple example is given where the representation obtained depends on $\l$. For $\l=1$ the representation is optimal with respect to a least squares error criterion, but as $\l$ decreases towards 0 the representation becomes progressively worse and, in some cases, very poor. The example suggests a need to understand better the circumstances under which TD(0) and Q-learning obtain satisfactory neural network-based compact representations of the cost function. A variation of TD(0) is also proposed, which performs better on the example.

D. P. Bertsekas and J. N. Tsitsiklis, "An Analysis of Stochastic Shortest Path Problems," Mathematics of Operations Research, Vol. 16, 1991, pp. 580-595.

Abstract: We consider a stochastic version of the classical shortest path problem whereby for each node of a graph, we must choose a probability distribution over the set of successor nodes so as to reach a certain destination node with minimum expected cost. The costs of transition between successive nodes can be positive as well as negative. We prove natural generalizations of the standard results for the deterministic shortest path problem, and we extend the corresponding theory for undiscounted finite state Markovian decision problems by removing the usual restriction that costs are either all nonnegative or all nonpositive.

D. P. Bertsekas, "Distributed Dynamic Programming," IEEE Transactions on Aut. Control, Vol. AC-27, 1982, pp. 610-616.

Abstract: We consider distributed algorithms for solving dynamic programming problems whereby several processors participate simultaneously in th computation while maintaining coordination by information exchange via communication links. A model of asynchronous distributed computation is developed which requires very weak assumptions on the ordering of computations,the timing of information exchange,the amount of local information needed at each computation node, and the initial condition for the algorithm. the class of problems considered is very broad and includes shortest path problems, and finite and infinite horizon stochastic optimal control problems. When specialized to the shortest path problem, the algorithm reduces to the algorithm originally implemented for routing messages in the internet.

D. P. Bertsekas, and S. E. Shreve "Existence of Optimal Stationary Policies in Deterministic Optimal Control," J. of Math Analysis and Applications, Vol. 69, 1979, pp. 607-620.

Abstract: This paper considers deterministic discrete-time optimal control problems over an infinite horizon involving a stationary system and a nonpositive cost per stage. Various results are provided relating to existence of an epsilon-optimal stationary policy, and existence of an optimal stationary policy assuming an optimal policy exists.

S. E. Shreve, and D. P. Bertsekas, "Alternative Theoretical Frameworks for Finite Horizon Discrete-Time Stochastic Optimal Control," SIAM J. on Control and Optimization, Vol. 16, 1978, pp. 953-978.

Abstract: Stochastic optimal control problems are usually analyzed under one of three types of assumptions: a) Countability assumptions on the underlying probability space - this eliminates all difficulties of measure theoretic nature; b) Semicontinuity assumptions under which the existence of optimal Borel measurable policies can be guaranteed; and c) Borel measurability assumptions under which the existence of p-optimal or p-epsilon-optimal Borel measurable policies can be guaranteed (Blackwell, Strauch). In this paper, we introduce a general theoretical framework based on outer integration which contains these three models as special cases. Within this framework all known results for finite horizon problems together with some new ones are proved and subsequently specialized. An important new feature of our specialization to the Borel measurable model is the introduction of universally measurable policies. We show that everywhere optimal or nearly optimal policies exist within this class and this enables us to dispense with the notion of p-optimality.

D. P. Bertsekas, "Monotone Mappings with Application in Dynamic Programming," SIAM J. on Control and Optimization, Vol. 15, 1977, pp. 438-464.

Abstract: The structure of many sequential optimization problems over a finite or infinite horizon can be summarized in the mapping that defines the related dynamic programming algorithm. In this paper, we take as a starting point this mapping and obtain results that are applicable to a broad class of problems. This approach has also been taken earlier by Denardo under contraction assumptions. The analysis here is carried out without contraction assumptions and thus the results obtained can be applied, for example, to the positive and negative dynamic programming models of Blackwell and Strauch. Most of the existing results for these models are generalized and several new results are obtained relating mostly to the convergence of the dynamic programming algorithm and the existence of optimal stationary policies.

Lecture Slides, Survey Papers, Research papers, Top Menu

Nonlinear Programming and Optimization Applications

A. Nedich and D. P. Bertsekas, "The Effect of Deterministic Noise in Subgradient Methods," Lab. for Information and Decision Systems Report, MIT, September 2007.

D. P. Bertsekas, "Extended Monotropic Programming and Duality," Lab. for Information and Decision Systems Report 2692, MIT, March 2006 (revised March 2007), to appear in JOTA.

A. E. Ozdaglar and D. P. Bertsekas, "The Relation Between Pseudonormality and Quasiregularity in Constrained Optimization," Optimization Methods and Software, Vol. 19 (2004), pp. 493--506.

A. E. Ozdaglar and D. P. Bertsekas, "Routing and Wavelength Assignment in Optical Networks," Report LIDS-P-2535, Dec. 2001; IEEE Trans. on Networking, no. 2, Apr. 2003, pp. 259-272.

Abstract: The problem of routing and wavelength assignment (RWA) is critically important for increasing the efficiency of wavelength-routed all-optical networks. Given the physical network structure and the required connections, the RWA problem is to select a suitable path and wavelength among the many possible choices for each connection so that no two paths sharing a link are assigned the same wavelength. In work to date, this problem has been formulated as a difficult integer programming problem that does not lend itself to efficient solution or insightful analysis. In this work, we propose several novel optimization problem formulations that offer the promise of radical improvements over the existing methods. We adopt a (quasi-)static view of the problem and propose new integer-linear programming formulations, which can be addressed with highly efficient linear (not integer) programming methods and yield optimal or near-optimal RWA policies. The fact that this is possible is surprising, and is the starting point for new and greatly improved methods for RWA. Aside from its intrinsic value, the quasi-static solution method can form the basis for suboptimal solution methods for the stochastic/dynamic settings. Note: A comparative computational evaluation of the methodology of this paper is given in the thesis by Ali Meli.

D. P. Bertsekas and A. E. Ozdaglar, "Pseudonormality and a Lagrange Multiplier Theory for Constrained Optimization," Report LIDS-P-2489, Nov. 2000; JOTA, Vol. 114, (2002), pp. 287--343.

Abstract: We consider optimization problems with equality, inequality, and abstract set constraints, and we explore various characteristics of the constraint set that imply the existence of Lagrange multipliers. We prove a generalized version of the Fritz-John theorem, and we introduce new and general conditions that extend and unify the major constraint qualifications. Among these conditions, two new properties, pseudonormality and quasinormality, emerge as central within the taxonomy of interesting constraint characteristics. In the case where there is no abstract set constraint, these properties provide the connecting link between the classical constraint qualifications and two distinct pathways to the existence of Lagrange multipliers: one involving the notion of quasiregularity and Farkas' Lemma, and the other involving the use of exact penalty functions. The second pathway also applies in the general case where there is an abstract set constraint.

D. P. Bertsekas and A. E. Koksal-Ozdaglar, "Enhanced Optimality Conditions and Exact Penalty Functions," Proc. of the 38th Allerton Conference on Communication, Control, and Computing, Allerton Park, Ill., September 2000.

A. Nedic and D. P. Bertsekas, "Incremental Subgradient Methods for Nondifferentiable Optimization," Report LIDS-P-2460, Dec. 2000, SIAM J. on Optimization, Vol. 12, 2001, pp. 109-138.

A. Nedic, D. P. Bertsekas, and V. Borkar, Distributed Asynchronous Incremental Subgradient Methods, Proceedings of the March 2000 Haifa Workshop ``Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications", D. Butnariu, Y. Censor, and S. Reich, Eds., Elsevier, Amsterdam, 2001.

Abstract: We propose and analyze a distributed asynchronous subgradient method for minimizing a convex function that consists of the sum of a large number of component functions. The idea is to distribute the computation of the component subgradients among a set of processors, which communicate only with a coordinator. The coordinator performs the subgradient iteration incrementally and asynchronously, by taking steps along the subgradients of the component functions that are available at the update time. The incremental approach has performed very well in centralized computation, and the parallel implementation should improve its performance substantially, particularly for typical problems where computation of the component subgradients is relatively costly.

A. Nedic and D. P. Bertsekas, "Convergence Rate of Incremental Subgradient Algorithms," Stochastic Optimization: Algorithms and Applications (S. Uryasev and P. M. Pardalos, Editors), pp. 263-304, Kluwer Academic Publishers, 2000.

Abstract: We consider a class of subgradient methods for minimizing a convex function that consists of the sum of a large number of component functions. This type of minimization arises in a dual context from Lagrangian relaxation of the coupling constraints of large scale separable problems. The idea is to perform the subgradient iteration incrementally, by sequentially taking steps along the subgradients of the component functions, with intermediate adjustment of the variables after processing each component function. This incremental approach has been very successful in solving large differentiable least squares problems, such as those arising in the training of neural networks, and it has resulted in a much better practical rate of convergence than the steepest descent method. In this paper, we present convergence results and estimates of the convergence rate of a number of variants of incremental subgradient methods, including some that use randomization. The convergence rate estimates are consistent with our computational results, and suggests that the randomized variants perform substantially better than their deterministic counterparts.

D. P. Bertsekas, and J. N. Tsitsiklis, "Gradient Convergence in Gradient Methods," Report LIDS-P-2404, Lab. for Info. and Decision Systems, November 1997, SIAM J. on Optimization, Vol. 10, 2000, pp. 627-642.

Abstract: For the classical gradient method and several deterministic and stochastic variants for unconstrained minimization, we discuss the issue of convergence of the gradient sequence and the attendant issue of stationarity of limit points of the iterate sequence. We assume that the cost function gradient is Lipschitz continuous, and that the stepsize diminishes to 0 and satisfies standard stochastic approximation conditions. We show that either the cost sequence diverges to - infinity or else the cost sequence converges to a finite value and the gradient sequence converges to 0 (with probability 1 in the stochastic case). Existing results assume various boundedness conditions, such as boundedness of the cost sequence or the gradient sequence or the iterate sequence, which we do not assume.

D. P. Bertsekas, "A Note on Error Bounds for Convex and Nonconvex Programs, " COAP (Comp. Optimization and Applications), Vol. 12, 1999, pp. 41-51.

Abstract: Given a single feasible solution $x_F$ and a single infeasible solution $x_I$ of a mathematical program, we provide an upper bound to the optimal dual value. We assume that $x_F$ satisfies a weakened form of the Slater condition. We apply the bound to convex programs and we discuss its relation to Hoffman-like bounds. As a special case, we recover a bound due to Mangasarian [Man97] on the distance of a point to a convex set specified by inequalities.

C. C. Wu and D. P. Bertsekas, "Distributed Power Control Algorithms for Wireless Networks," IEEE Trans. on Vehicular Technology, Vol. 50, pp. 504-514, 2001.

Abstract: Power control has been shown to be an effective way to increase capacity in wireless systems. In previous work on power control, it has been assumed that power levels can be assigned from a continuous range. In practice, however, power levels are assigned from a discrete set. In this work, we consider the minimization of the total power transmitted over given discrete sets of available power levels subject to maintaining an acceptable signal quality for each mobile. We have developed distributed iterative algorithms for solving a more general version of this integer programming problem, which is of independent interest, and have shown that they find the optimal solution in a finite number of iterations which is polynomial in the number of power levels and the number of mobiles.

D. P. Bertsekas, "A Hybrid Incremental Gradient Method for Least Squares," SIAM J. on Optimization, Vol. 7, 1997, pp. 913-926.

Abstract: The LMS method for linear least squares problems differs from the steepest descent method in that it processes data blocks one-by-one, with intermediate adjustment of the parameter vector under optimization. This mode of operation often leads to faster convergence when far from the eventual limit, and to slower (sublinear) convergence when close to the optimal solution. We embed both LMS and steepest descent, as well as other intermediate methods, within a one-parameter class of algorithms, and we propose a hybrid class of methods that combine the faster early convergence rate of LMS with the faster ultimate linear convergence rate of steepest descent. These methods are well-suited for neural network training problems with large data sets.

D. P. Bertsekas, "Incremental Least Squares Methods and the Extended Kalman Filter," SIAM J. on Optimization, Vol. 6, 1996, pp. 807-822.

Abstract: In this paper we propose and analyze nonlinear least squares methods, which process the data incrementally, one data block at a time. Such methods are well suited for large data sets and real time operation, and have received much attention in the context of neural network training problems. We focus on the Extended Kalman Filter, which may be viewed as an incremental version of the Gauss-Newton method. We provide a nonstochastic analysis of its convergence properties, and we discuss variants aimed at accelerating its convergence.

D. P. Bertsekas, "Thevenin Decomposition and Network Optimization," J. of Optimization Theory and Applications, Vol. 89, 1996, pp. 1-15.

Abstract: Thevenin's theorem, one of the most celebrated results of electric circuit theory, provides a two-parameter characterization of the behavior of an arbitrarily large circuit, as seen from two of its terminals. We interpret the theorem as a sensitivity result in an associated minimum energy/network flow problem, and we abstract its main idea to develop a decomposition method for convex quadratic programming problems with linear equality constraints, such as those arising in a variety of contexts such as Newton's method, interior point methods, and least squares estimation. Like Thevenin's theorem, our method is particularly useful in problems involving a system consisting of several subsystems, connected to each other with a small number of coupling variables.

D. P. Bertsekas and P. Tseng, "Partial Proximal Minimization Algorithms for Convex Programming," SIAM J. on Optimization, Vol. 4, 1994, pp. 551-572.

Abstract: We consider an extension of the proximal minimization algorithm where only some of the minimization variables appear in the quadratic proximal term. We interpret the resulting iterates in terms of the iterates of the standard algorithm and we show a uniform descent property, which holds independently of the proximal terms used. This property is used to give simple convergence proofs of parallel algorithms where multiple processors simultaneously execute proximal iterations using different partial proximal terms. We also show that partial proximal minimization algorithms are dual to multiplier methods with partial elimination of constraints, and we establish a relation between parallel proximal minimization algorithms and parallel constraint distribution algorithms.

D. P. Bertsekas and P. Tseng, "On the Convergence of the Exponential Multiplier Method for Convex Programming," Math Programming, Vol. 60, pp. 1-19, 1993.

Abstract: In this paper, we analyze the exponential method of multipliers for convex constrained minimization problems, which operates like the usual Augmented Lagrangian method, except that it uses an exponential penalty function in place of the usual quadratic. We also analyze a dual counterpart, the entropy minimization algorithm, which operates like the proximal minimization algorithm, except that it uses a logarithmic/entropy ``proximal'' term in place of a quadratic. We strengthen substantially the available convergence results for these methods, and we derive their convergence rate when applied to linear programs.

J. Eckstein and D. P. Bertsekas, "On the Douglas-Ratchford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators," Mathematical Programming, Vol. 55, 1992, pp. 293-318.

Abstract: This paper shows, by means of an operator called a splitting operator, that the Douglas-Ratchford splitting method for finding a zero of the sum of two monotone operators is a special case of the proximal point algorithm. Therefor, applications of Douglas-Ratchford splitting, such as the alternating direction method of multipliers for convex programming decomposition, are also special cases of the proximal point algorithm. This observation allows the unification and generalization of a variety of convex programming algorithms. By introducing a modified version of the proximal point algorithm, we derive a new, generalized alternating direction method of multipliers for convex programming. Advances of this sort illustrate the power and generality gained by adopting monotone operator theory as a conceptual framework.

P. Tseng and D. P. Bertsekas, "Relaxation Methods for Strictly Convex Costs and Linear Constraints," Mathematics of Operations Research, Vol. 16, 1991 pp. 462-481.

Abstract: Consider the problem of minimizing a stritcly convex (possibly nondifferentiable) cost subject to linear constraints. We propose a dual coordinate ascent method for this problem that uses inexact line search and either essentially cyclic or Gauss-Southwell order of coordinate relaxation. We show, under very weak conditions, that this method generates a sequence of primal vectors converging to the optimal primal solution. Under an additional regularity assumption, and assuming that the effective domain of the cost function is polyhedral, we show that a related sequence of dual vectors converges in cost to the optimal cost. If the constraint set has an interior point in the effective domain of the cost function, then this sequence of dual vectors is bounded and each of its limit points is an optimal dual solution. When the cost function is strongly convex, we show that the order of coordinate relaxation can become progressively more chaotic. These results significantly improve upon those obtained previously.

E. M. Gafni, and D. P. Bertsekas, "Two-Metric Projection Methods for Constrained Optimization," SIAM J. on Control and Optimization, Vol. 22, 1984, pp. 936-964.

Abstract: This paper is concerned with the problem min{f(x)|x\in X}, where X is a convex subset of a linear space H, and f is a smooth real-valued function on H. We propose the class of methods x_{k+1}=P(x_k-\alpha_k g_k), where P denotes projection on X with respect to the Hilbert space norm ||.||, g_k denotes the Frechet derivative of f at x_k with respect to another Hilbert space norm ||.||_k on H, and \alpha_k is a positive scalar stepsize. We thus remove an important restriction in the original proposal of Goldstein, and Levitin and Poljak, where the norms ||.|| and ||.||_k must be the same. It is therefore possible to match the norm ||.|| with the structure of X so that the projection operation is simplified while at the same time reserving the option to choose ||.||_k on the basis of approximations to the Hessian of f so as to attain a typically superlinear rate of convergence. The resulting methods are particularly attractive for large-scale problems with specially structured constraint sets such as optimal control and nonlinear multi-commodity network flow problems. The latter class of problems is discussed in some detail.

D. P. Bertsekas, "Projected Newton Methods for Optimization Problems with Simple Cosntraints," SIAM J. Control and Optimization, Vol. 20, 1982, pp. 221-246.

Abstract: We consider the problem min{f(x)|x>=0} and propose algorithms of the form x_{k+1}=P(x_k-a_kD_k grad f(x_k)) where P denotes projection on the positive orthant, a_k is a stepsize chosen by an Armijo-like rule, and D_k is a positive definite symmetric matrix, which is partly diagonal. We show that D_k can be calculated simply on the basis of second derivatives of f so that the resulting Newton-like algorithm has a typically superlinear rate of convergence. With other choices of D_k convergence at a typically linear rate is obtained. The algorithms are almost as simple as their unconstrained counterparts. They are well suited for problems of large dimension such as those arising in optimal control while being competitive with existing methods for low-dimensional problems. The effectiveness of the Newton-like algorithm is demonstrated via computational examples involving as many as 10,000 variables. Extensions to general linearly constrained problems are also provided. These extensions utilize a notion of an active generalized rectangle patterned after the notion of an active manifold used in maniforld suboptimization methods, By contrast with these methods, many constraints can be added or subtracted from the binding set at each iteration without the need to solve a quadratic programming problem.

D. P. Bertsekas, "Approximation Procedures Based on the Method of Multipliers," J. of Optimization Theory and Applications, Vol. 23, 1977.

Abstract: In this paper, we consider a method for solving certain optimization problems with constraints, nondifferentiabilities, and other ill-conditioning terms in the cost functional by approximating them by well-behaved optimization problems. The approach is based on the method of multipliers. The convergence properties of the methods proposed can be inferred from corresponding properties of multiplier methods with partial elimination of constraints. A related analysis is provided in this paper.

D. P. Bertsekas, "Multiplier Methods: A Survey," Automatica, Vol. 12, 1976, pp. 133-145.

Abstract: The purpose of this paper is to provide a survey of convergence and rate of convergence aspects of a class of recently proposed methods for constrained minimization - the, so called, multiplier methods. The results discussed highlight the operational aspects of multiplier methods and demonstrate their significant advantages over ordinary penalty methods.

D. P. Bertsekas, "On the Goldstein-Levitin-Polyak Gradient Projection Method," IEEE Trans. on Aut. Control, Vol. AC-21, 1976.

Abstract: This paper considers some aspects of the gradient projection method proposed by Goldstein, Levitin and Polyak, and more recently, in a less general context by McCormick. We propose and analyze some convergent step-size rules to be used in conjunction with the method. These rules are similar in spirit to the efficient Armijo rule for the method of steepest descent and under mild assumptions, they have the desirable property that they identify the set of active inequality constraints in a finite number of iterations.

D. P. Bertsekas, "A New Algorithm for Solution of Resistive Networks Involving Diodes," IEEE Trans. on Circuits and Systems, Vol. CAS-23, 1976, pp. 599-608.

Abstract: The solution of electric network problems by various algorithms such as for example Newton's method is often hampered by the presence of physical diodes with steeply rising exponential characteristics which cause overflow and slow convergence during numerical computation. In this paper we propose and analyze an algorithm which bypasses these difficulties by successively approximating the steep diode characteristics by smoother exponential functions. The algorithm may be modified to be used in the presence of ideal diodes and is related to penalty and multiplier methods for constrained minimization and Davidenko's method for solving certain ill-conditioned systems of nonlinear equations.

D. P. Bertsekas, "Necessary and Sufficient Conditions for a Penalty Method to be Exact," Mathematical Programming, Vol. 9, pp. 87-99, 1975.

Abstract: This paper identifies necessary and sufficient conditions for a penalty method to yield an optimal solution or a Lagrange multiplier of a convex programming problem by means of a single unconstrained minimization. The conditions are given in terms of properties of the objective and constraint functions of the problem as well as the penalty function adopted. It is shown among other things that all linear programs with finite optimal value satisfy such conditions when the penalty function is quadratic.

D. P. Bertsekas, "Nondifferentiable Optimization via Approximation," in Mathematical Programming Study 3, Nondifferentiable Optimization, M. L. Balinski, P. Wolfe, (eds.), North-Holland Publ. Co., pp. 1-15, 1975.

Abstract: This paper presents a systematic approach for minimization of a wide class of nondifferentiable functions. The technique is based on approximation of the nondifferentiable function by a smooth function and is related to penalty and multiplier methods for constrained minimization. Some convergence results are given and the method is ilustrated by means of examples from nonlinear programming.

D. P. Bertsekas, "Necessary and Sufficient Conditions for Existence of an Optimal Portfolio," Journal of Economic Theory, Vol. 8, No. 2, pp. 235-247, 1974.

Abstract: This paper identifies necessary and sufficient conditions for existence of a solution to a class of optimization problems under uncertainty. This class includes certain problems of optimal portfolio selection when rates of return of risky assets are uncertain, as well as problems of optimal choice of inputs and outputs by a perfectly competitive firm facing uncertain prices.

D. P. Bertsekas, "Partial Conjugate Gradient Methods for a Class of Optimal Control Problems," IEEE Trans. on Aut. Control, Vol. AC-19, 1974, pp. 209-217.

Abstract: In this paper we examine the computational aspects of a certain class of discrete-time optimal control problems. We propose and analyze two partial conjugate gradient algorithms which operate in cycles of s+1 conjugate gradient steps (s\le n = space dimension). The algorithms are motivated by the special form of the Hessian matrix of the cost functional. The first algorithm exhibits a linear convergence rate and offers some advantages over steepest descent in certain cases such as when the system is unstable. The second algorithm requires second-order information with respect to the control variables at the beginning of each cycle and exhibits (s+1)-step superlinear convergence rate. Furthermore, it solves a linear-quadratic problem in s+1 steps as compared with the mN steps (m = control space dimension, N = number of stages) required by the ordinary conjugate gradient method.

D. P. Bertsekas, "Stochastic Optimization Problems with Nondifferentiable Cost Functionals," Journal of Optimization Theory and Applications, Vol. 12, 1973. pp. 218-231.

Abstract: In this paper, we examine a class of stochastic optimization problems characterized by nondifferentiability of the objective function. It is shown that, in many cases, the expected value of the objective function is differentiable and, thus, the resulting optimization problem can be solved by using classical analytical or numerical methods. Te results are subsequently applied to the solution of a problem of economic resource allocation.

D. P. Bertsekas, and S. K. Mitter, "A Descent Numerical Method for Optimization Problems with Nondifferentiable Cost Functionals," SIAM Journal on Control, Vol. 11, 1973, pp. 637-652.

Abstract: In this paper we consider the numerical solution of convex optimization problems with nondifferentiable cost functionals. We propose a new algorithm, the epsilon-subgradient method, a large step, double iterative algorithm which converges rapidly under very general assumptions. We discuss the application of the algorithm in some problems of nonlinear programming and optimal control and we show that the epsilon-subgradient method contains as a special case a minimax algorithm due to Pschenichnyi.

D. P. Bertsekas, and S. K. Mitter, "Steepest Descent for Optimization Problems with Nondifferentiable Cost Functionals," Proc. of Princeton Conference on Information Sciences and Systems, 1971, pp. 347-351.

Lecture Slides, Survey Papers, Research papers, Top Menu

Network Optimization

A. E. Ozdaglar and D. P. Bertsekas, "Routing and Wavelength Assignment in Optical Networks," Report LIDS-P-2535, Dec. 2001; IEEE Trans. on Networking, no. 2, Apr. 2003, pp. 259-272.

P. Tseng, and D. P. Bertsekas, "An Epsilon-Relaxation Method for Separable Convex Cost Generalized Network Flow Problems," Math. Programming, Vol. 88, 2000, pp. 85-104.

Abstract: We generalize the epsilon-relaxation method of for the single commodity, separable convex cost network flow problem to network flow problems with positive gains. We show that the method terminates with a near optimal solution, and we provide an associated complexity analysis.

D. P. Bertsekas, L. C. Polymenakos, and P. Tseng, "Epsilon-Relaxation and Auction Methods for Separable Convex Cost Network Flow Problems," in Network Optimization, by P. M. Pardalos, D. W. Hearn, and W. W. Hager (eds.), Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, N.Y., 1998, pp. 103-126; also given in the book by Bertsekas "Network Optimization: Continuous and Discrete Models," Athena Scientific, 1998.

Abstract: We consider a generic auction method for the solution of the single commodity, separable convex cost network flow problem. This method provides a unifying framework for the $\e$-relaxation method and the auction/sequential shortest path algorithm and, as a consequence, we develop a unified complexity analysis for the two methods. We also present computational results showing that these methods are much faster than earlier relaxation methods, particularly for ill-conditioned problems.

D. P. Bertsekas, L. C. Polymenakos, and P. Tseng, "An Epsilon-Relaxation Method for Convex Network Optimization Problems," SIAM J. on Optimization, Vol. 7, 1997, pp. 853-870.

Abstract: We propose a new method for the solution of the single commodity, separable convex cost network flow problem. The method generalizes the $\e$-relaxation method developed for linear cost problems, and reduces to that method when applied to linear cost problems. We show that the method terminates with a near optimal solution, and we provide an associated complexity analysis. We also present computational results showing that the method is much faster than earlier relaxation methods, particularly for ill-conditioned problems.

D. P. Bertsekas, F. Guerriero, and R. Musmanno, "Parallel Asynchronous Label Correcting Methods for Shortest Paths," J. of Optimization Theory and Applications, Vol. 88, 1996, pp. 297-320.

D. P. Bertsekas, "An Auction Algorithm for the Max-Flow Problem," J. of Optimization Theory and Applications, Vol. 87, 1995, pp. 69-101.

Abstract: We propose a new algorithm for the max-flow problem. It consists of a sequence of augmentations along paths constructed by an auction-like algorithm. These paths are not necessarily shortest, that is, they need not contain a minimum number of arcs. However, they typically can be found with much less computation than the shortest augmenting paths used by competing methods. Our algorithm outperforms these latter methods as well as state-of-the-art preflow-push algorithms by a very large margin in tests with standard randomly generated problems.

D. P. Bertsekas, S. Pallottino, and M. G. Scutella, "Polynomial Auction Algorithms for Shortest Paths," Computational Optimization and Applications , Vol. 4, 1995, pp. 99-125.

Abstract: In this paper we consider strongly polynomial variations of the auction algorithm for the single origin/many destinations shortest path problem. These variations are based on the idea of graph reduction, that is, deleting unnecessary arcs of the graph by using certain bounds naturally obtained in the course of the algorithm. We study the structure of the reduced graph and we exploit this structure to obtain algorithms with $O\bl(n\min\{m,n\log n\}\br)$ and $O(n^2)$ running time. Our computational experiments show that these algorithms outperform their closest competitors on randomly generated dense all destinations problems, and on a broad variety of few destination problems.

D. P. Bertsekas, "An Auction/Sequential Shortest Path Algorithm for the Minimum Cost Flow Problem," Report LIDS-P-2146, Lab. for Info. and Decision Systems, Revision of Feb. 1995.

Abstract: We propose a new algorithm for the solution of the linear minimum cost network flow problem, based on a sequential shortest path augmentation approach. Each shortest path is constructed by means of the recently proposed auction/shortest path algorithm. This approach allows useful information to be passed from one shortest path construction to the next. However, the naive implementation of this approach where the length of each arc is equal to its reduced cost fails because of the presence of zero cost cycles. We overcome this difficulty by using as arc lengths $\e$-perturbations of reduced costs and by using $\e$-complementary slackness conditions in place of the usual complementary slackness conditions. We present several variants of the main algorithm, including one that has proved very efficient for the max-flow problem. We also discuss the possibility of combining the algorithm with the relaxation method and we provide encouraging computational results.

D. P. Bertsekas, D. A. Castanon, and H. Tsaknakis, "Reverse Auction and the Solution of Asymmetric Assignment Problems," SIAM J. on Optimization, Vol. 3, 1993, pp. 268-299.

Abstract: In this paper we propose auction algorithms for solving several types of assignment problems with inequality constraints. Included are asymmetric problems with different numbers of persons and objects, and multiassignment problems, where persons may be assigned to several objects and reversely. A central new idea in all these algorithms is to combine regular auction, where persons bid for objects by raising their prices, with reverse auction, where objects compete for persons by essentially offering discounts. Reverse auction can also be used to accelerate substantially (and sometimes dramatically) the convergence of regular auction for symmetric assignment problems.

D. P. Bertsekas, "A Simple and Fast Label Correcting Algorithm for Shortest Paths," Networks, Vol. 23, pp. 703-709, 1993.

Abstract: We propose a new method for ordering the candidate nodes in label correcting methods for shortest path problems. The method is equally simple but much faster than the D' Esopo-Pape algorithm. It is similar to the threshold algorithm in that it tries to scan nodes with small labels as early as possible, and performs comparably with that algorithm. Our algorithm can also be combined with the threshold algorithm thereby considerably improving the practical performance of both algorithms.

D. P. Bertsekas and D. A. Castanon, "Parallel Primal-Dual Methods for the Minimum Cost Flow Problem," Computational Optimization and Applications, Vol. 2, pp. 317-336, 1993.

Abstract: In this paper we discuss the parallel asynchronous implementation of the classical primal-dual method for solving the linear minimum cost network flow problem. Multiple augmentations and price rises are simultaneously attempted starting from several nodes with possibly outdated price and flow information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show that this algorithm is valid, terminating finitely to an optimal solution. We also present computational results using an Encore Multimax that illustrate the speedup that can be obtained by parallel implementation.

D. P. Bertsekas and D. A. Castanon, "A Forward Reverse Auction Algorithm for Asymmetric Assignment Problems," Report LIDS-P-2159, Lab. for Information and Decision Systems, also Computational Optimization and Applications, Vol. 1, pp. 277-297, 1992.

Abstract: In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently deals better with price wars than the currently existing auction algorithms. As a result it frequently does not require $\e$-scaling for good practical performance, and tends to terminate substantially (and often dramatically) faster than its competitors.

D. P. Bertsekas and D. A. Castanon, "Parallel Synchronous and Asynchronous Implementations of the Auction Algorithm," Parallel Computing, Vol. 17, pp. 707-732, 1991.

Abstract: In this paper we discuss the parallel implementation of the auction algorithm for the classical assignment problem. We show that the algorithm admits a totally asynchronous implementation and we consider several implementations on a shared memory machine, with varying degrees of synchronization. We also discuss and explore computationally the tradeoffs involved in using asynchronism to reduce the synchronization penalty.

D. P. Bertsekas, "An Auction Algorithm for Shortest Paths," SIAM J. on Optimization, Vol. 1, 1991, pp. 425-447.

Abstract: We propose a new and simple algorithm for finding shortest paths in a directed graph. In the single origin/single destination case, the algorithm maintains a single path starting at the origin, which is extended or contracted by a single node at each iteration. Simultaneously, at most one dual variable is adjusted at each iteration so as to either improve or maintain the value of a dual function. For the case of multiple origins, the algorithm is well suited for parallel computation. It maintains multiple paths that can be extended or contracted in parallel by several processors that share the results of their computations. Based on experiments with randomly generated problems on a serial machine, the algorithm outperforms substantially its closest competitors for problems with few origins and a single destination. It also seems better suited for parallel computation than other shortest path algorithms.

D. P. Bertsekas and D. A. Castanon, "The Auction Algorithm for the Transportation Problem," Annals of Operations Research, Vol. 20, pp. 67-96, 1989.

Abstract: This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.

D. P. Bertsekas and J. Eckstein, "Dual Coordinate Step Methods for Linear Network Flow Problems," Mathematical Programming, Series B, Vol. 42, 1988, pp. 203-243.

Abstract: 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 epsilon-complementary slackness, and most do not explicitly manipulate any "global" objects such as paths, trees, or cuts. Interestingly, these methods have stimulated a large class of serial computational methods complexity results. We develop the basic theory of these methods and present two specific methods, the epsilon-relaxation algorithm for the minimum-cost flow problem, and the auction algorithm for the assignment problem. We show how to implement these methods with serial complexities of O(N^3 log NC) and O(NA log NC), respectively. We also discuss practical implementation issues and computational experience to date. Finally, we show how to implement epsilon-relaxation in a completely asynchronous, "chaotic" environment in which some processors compute faster than others, and there can be arbitrarily large communication delays.

D. P. Bertsekas, "The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem," Annals of Operations Research, Vol. 14, 1988, pp. 105-123.

Abstract: We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi - like relaxation method for solving a dual problem. Its (sequential) worst - case complexity, for a particular implementation that uses scaling, is O(NAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.

D. P. Bertsekas and P. Tseng, "Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems," Operations Research Journal, Vol. 36, 1988, pp. 93-114.

Abstract: We propose a new class of algorithms for linear network flow problems with and without gains. These algorithms are based on iterative improvement of a dual cost and operate in a manner that is reminiscent of coordinate ascent and gauss-Deidel relaxation methods. we compare our coded implementations of these methods with mature state-of-the-art primal simplex and primal-dual codes,and find them to be several times faster on standard benchmark problems, and faster by an order of magnitude on large, randomly generated problems. Our experiments indicate that the speedup factor increases with problem dimension.

D. P. Bertsekas, P. A. Hosein, and P. Tseng, "Relaxation Methods for Network Flow Problems with Convex Arc Costs," SIAM J. on Optimization, Vol. 25, 1987.

Abstract: We consider the standard single commodity network flow problem with both linear and strictly convex possibly nondifferentiable arc costs. For the case where all arc costs are strictly convex we study the convergence of a dual Gauss-Seidel type relaxation method that is well suited for parallel computation. We then extend this method to the case where some of the arc costs are linear. As a special case we recover a relaxation method for the linear minimum cost network flow problem proposed in Bertsekas [1] and Bertsekas and Tseng [2].

J. N. Tsitsiklis, and D. P. Bertsekas, "Distributed Asynchronous Optimal Routing in Data Networks," IEEE Trans. on Aut. Control, Vol. AC-31, 1986, pp. 325-332.

Abstract: In this paper we study the performance of a class of distributed optimal routing algorithms of the gradient projection type under weaker and more realistic assumptions than those considered thus far. In particular, we show convergence to an optimal routing without assuming synchronization of computation at all nodes and measurement of link lengths at all links, while taking into account the probability of link flow transients caused by routing updates. This demonstrates the robustness of these algorithms in a realistic distributed operating environment.

D. P. Bertsekas, "A Unified Framework for Primal-Dual Methods in Minimum Cost Network Flow Problems," Math. Programming, Vol. 32, pp. 125-145, 1985.

Abstract: We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. the algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.

E. Gafni, and D. P. Bertsekas, "Dynamic Control of Session Input Rates in Communication Networks," IEEE Trans. on Aut. Control, Vol. AC-29, 1984, pp. 1009-1016.

Abstract: We consider a distributed iterative algorithm for dynamically adjusting the input rate of each session of a voice or data network using virtual circuits so as to exercise flow control. Each session origin periodically receives information regarding the level of congestion along the session path and iteratively corrects its input rate. In this paper, we place emphasis on voice networks, but the ideas involved are also relevant for dynamic flow control in data networks. The algorithm provides for the addition of new and termination of old sessions and maintains at all times feasibility of link flows with respect to capacity constraints. Fairness with respect to all sessions is built into the algorithm and a mechanism is provided to control link utilization and average delay per packet at any desired level.

D. P. Bertsekas, E. Gafni, and R. G. Gallager, "Second Derivative Algorithms for Minimum Delay Distributed Routing in Networks," IEEE Trans. on Communications, Vol. COM-32, 1984 p. 911.

Abstract: We propose a class of algorithms for finding an optimal quasi-static routing in a communication network. The algorithms are based on Gallager's method [1] and provide methods for iteratively updating the routing table entries of each node in a manner that guarantees convergence to a minimum delay routing. Their main feature is that they utilize second derivatives of the objective function and may be viewed as approximations to a constrained version of Newton's method. The use of second derivatives results in improved speed of convergence and automatic stepsize scaling with respect to level of traffic input. These advantages are of crucial importance for the practical implementation of the algorithm using distributed computation in an environment where input traffic statistics gradually change.

D. P. Bertsekas and E. Gafni, "Projected Newton Methods and Optimization of Multicommodity Flows," IEEE Trans. on Automatic Control, Vol. AC-28, 1983, pp. 1090-1096.

Abstract: A superlinearly convergent Newton like method for linearly constrained optimization problems is adapted for solution of multicommodity network flow problems of the type arising in communication and transportation networks. We show that the method can be implemented approximately by making use of conjugate gradient iterations without the need to compute explicitly the Hessian matrix. Preliminary computational results suggest that this type of method is capable of yielding highly accurate solutions of nonlinear multicommodity flow problems far more efficiently than any of the methods available at present.

Lecture Slides, Survey Papers, Research papers, Top Menu

Parallel and Distributed Algorithms

A. Nedic, D. P. Bertsekas, and V. Borkar, Distributed Asynchronous Incremental Subgradient Methods, Proceedings of the March 2000 Haifa Workshop "Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications", D. Butnariu, Y. Censor, and S. Reich, Eds., Elsevier, Amsterdam, 2001.

S. A. Savari and D. P. Bertsekas, "Finite Termination of Asynchronous Iterative Algorithms," Parallel Computing, Vol. 22, 1996, pp. 39-56.

Abstract: We consider $n$-processor distributed systems where the $i$th processor executes asynchronously the iteration $x_i=f_i(x)$. It is natural to terminate the iteration of the $i$th processor when some local condition, such as $x_i-f_i(x)$: ``small", holds. However, local termination conditions of this type may not lead to global termination because of the asynchronous character of the algorithm. In this paper, we propose several approaches to modify the original algorithm and/or supplement it with an interprocessor communication protocol so that this difficulty does not arise.

E. A. Varvarigos and D. P. Bertsekas, "A Conflict Sense Routing Protocol and Its Performance for Hypercubes", IEEE Trans. Computers, Vol. 45, 1996, pp. 693-703 (copy of this paper available from the first author).

Abstract: We propose a new switching format for multiprocessor networks, which we call Conflict Sense Routing Protocol. This switching format is a hybrid of packet and circuit switching, and combines advantages of both. We initially present the protocol in a way applicable to a general topology. We then present an implementation of this protocol for a hypercube computer and a particular routing algorithm. We also analyze the steady-state throughput of the hypercube implementation for random node-to-node communications.

D. P. Bertsekas, D. A. Castanon, J. Eckstein, and S. Zenios, "Parallel Computing in Network Optimization", Handbooks in OR & MS, (M. O. Ball, et. al, Eds.), Vol. 7, 1995, pp. 331-399.

D. P. Bertsekas, F. Guerriero and R. Musmanno, "Parallel Shortest Path Methods for Globally Optimal Trajectories," High Performance Computing: Technology, Methods, and Applications, (J. Dongarra et.al., Eds.), Elsevier, 1995.

Abstract: In this paper we consider a special type of trajectory optimization problem that can be viewed as a continuous-space analog of the classical shortest path problem. This problem is approached by space discretization and solution of a discretized version of the associated Hamilton-Jacobi equation. It was recently shown by Tsitsiklis that some of the ideas of classical shortest path methods, such as those underlying Dijkstra's algorithm, can be applied to solve the discretized Hamilton-Jacobi equation. In more recent work, Polymenakos, Bertsekas, and Tsitsiklis have carried this analogy further to show that some efficient label correcting methods for shortest path problems, the SLF and SLF/LLL methods of Bertsekas, can be fruitfully adapted to solve the discretized Hamilton-Jacobi equation. In this paper we discuss parallel asynchronous implementations of these methods on a shared memory multiprocessor, the Alliant FX/80. Our results show that these methods are well suited for parallelization and achieve excellent speedup.

E. A. Varvarigos and D. P. Bertsekas, "Multinode Broadcast in Hypercubes and Rings with Randomly Distributed Length of Packets," IEEE Transactions on Parallel and Distributed Systems, Vol. 4, pp. 144-154, 1993.

Abstract: We consider a multinode broadcast (MNB) in a hypercube and in a ring network of processors. This is the communication task where we want each node of the network to broadcast a packet to all the other nodes. The communication model that we use is different than those considered in the literature so far. In particular, we assume that the lengths of the packets that are broadcast are not fixed, but are distributed according to some probabilistic rule, and we compare the optimal times required to execute the MNB for variable and for fixed packet lengths.

D. P. Bertsekas and D. A. Castanon, "Parallel Asynchronous Hungarian Methods for the Assignment Problem," ORSA J. on Computing, Vol. 5, pp. 261-274, 1993.

Abstract: In this paper we discuss the parallel asynchronous implementation of the Hungarian method for solving the classical assignment problem. Multiple augmentations and price rises are simultaneously attempted starting from several unassigned sources and using possibly outdated price and assignment information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show the validity of this algorithm and we demonstrate computationally that an asynchronous implementation is often faster than its synchronous counterpart.

D. P. Bertsekas and D. A. Castanon, "Parallel Primal-Dual Methods for the Minimum Cost Flow Problem," Computational Optimization and Applications, Vol. 2, pp. 317-336, 1993.

D. P. Bertsekas and D. A. Castanon, "Parallel Synchronous and Asynchronous Implementations of the Auction Algorithm," Parallel Computing, Vol. 17, 1991, pp. 707-732.

D. P. Bertsekas, and J. N. Tsitsiklis, "Some Aspects of Parallel and Distributed Iterative Algorithms - A Survey," Automatica, Vol. 27, 1991, pp. 3-21.

Abstract: We consider iterative algorithms of the form x:=f(x), executed by a parallel or distributed computing system. We first consider synchronous executions of such iterations and study their communication requirements, as well as issues related to processor synchronization. We also discuss the parallelization of iterations of the Gauss-Seidel type. We then consider asynchronous implementations whereby each processor iterates on a different component of x, at its own pace, using the most recently received (but possibly outdated) information on the remaining components of x. While certain algorithms may fail to converge when implemented asynchronously, a large number of positive convergence results is available. We classify asynchronous algorithms into three main categories, depending on the amount of asynchronism they can tolerate, and survey the corresponding convergence results. We also discuss issues related to their termination.

D. P. Bertsekas, C. Ozveren, G. D. Stamoulis, P. Tseng, and J. N. Tsitsiklis, "Optimal Communication Algorithms for Hypercubes," J. of Parallel and Distributed Computing, Vol. 11, 1991, pp. 263-275.

Abstract: We consider the following basic communication problems in a hypercube network of processors: the problem of a single processor sending a different packet to each of the other processors, the problem of simultaneous broadcast of the same packet from every processor to all other processors, and the problem of simultaneous exchange of different packets between every pair of processors. The algorithms proposed for these problems are optimal in terms of execution time and communication