Search

In this paper we discuss a general framework for single component replacement models. This framework is based on the regenerative structure of these models and by using results from renewal theory a unified presentation of the discounted and average finite and infinite horizon cost models is given. Finally, some well-known replacement models are discussed, and making use of the previous results an easy derivation of their cost functions is presented.

In this paper we present two algorithms for a machine allocation problem occurring in manufacturing systems. For the two algorithms presented we prove worst-case performance ratios of 2 and 3/2, respectively. The machine allocation problem we consider is a general convex resource allocation problem, which makes the algorithms applicable to a variety of resource allocation problems. Numerical results are presented for two real-life manufacturing systems.

In this note we derive the expected total discounted profit of an insurer due to a single policy holder within a third-party liability insurance. We consider both a policy holder claiming optimally and non-optimally.

In this chapter, we discuss a modification of the standard path-following scheme that tends to speed up the global convergence. This modification, the central region method, generates iterates that do not really trace the central path, or at least not closely. In this way, it has a relatively large freedom of movement, and consequently the ability to take long steps. This makes it interesting to consider more sophisticated search directions. We propose a search direction that is built up in three phases, viz. 1. Initial centering, 2. Predictor, 3. Second order centrality corrector.

In this chapter, we take a careful look at the behavior of the central path, when it approaches the optimal solution set of a semidefinite program. We will demonstrate that the primal-dual central path converges to the analytic center of the optimal solution set. Moreover, the distance to this analytic center from any point on the central path is shown to converge at the same R-rate as the duality gap. This result can be interpreted as an error-bound for solutions on the central path, with respect to the optimal solution set. Underlying the analysis is an assumption that a strictly complementary solution pair for the semidefinite program exists.

In Chapter 3, we have analyzed the iteration complexity of finding an ϵ-optimal solution, if an interior, sufficiently centered pair of primal and dual solutions is known beforehand. We will see in this chapter how we can adapt the algorithms of Chapter 3 to solve semidefinite programming problems without any pre-knowledge. To this end, we use the self-dual embedding technique. This technique will also be used to tackle semidefinite programming problems that may be unbounded, unsolvable, or infeasible.

Modern solvers for linear and quadratic programming often incorporate some variant of the primal-dual path-following method, which is a class of interior point methods. This method turns out to be suited for solving semidefinite programming problems as well. In this chapter, we propose a framework for analyzing primal-dual path-following algorithms for semidefinite programming. Our framework is a direct extension of the v-space approach, which was developed by Kojima et al. [63] in the context of complementarity problems.

List of Figures. List of Tables. Preface. Contributing Authors. Part I: Theory and Algorithms of Semidefinite Programming J.F. Sturm. 1. Introduction. 2. Duality. 3. Polynomiality of Path-following Methods. 4. Self-Dual Embedding Technique. 5. Properties of the Central Path. 6. Superlinear Convergence. 7. Central Region Methods. Part II: Linear, Quadratic, Semidefinite Programming and Beyond. 8. An Implementation of the Homogeneous Algorithm E.D. Andersen, K.D. Andersen. 9. A Simplified Correctness Proof for Interior Point Algorithm S.A. Vavasis, Y. Ye. 10. New Analysis of Newton Methods for LCP J. Peng, et al. 11. Numerical Evaluation of SDPA K. Fujisawa, et al. 12. Robust Modeling of Multi-Stage Portfolio Problems A. Ben-Tal, et al. 13. An Interior Point SQP Parallel B&B Method. 14. Solving Linear Ordering Problems J.E. Mitchell, B. Borchers. 15. Finite Element Methods for Solving Parabolic Inverse Problems Y.L. Keung, J. Zou. 16. Error Bounds For Quadratic Systems Z.-Q. Luo, J.F. Sturm. 17. Squared Functional Systems and Optimization Problems Y. Nesterov. 18. Interior Point Methods: Current Status and Future Directions R.M. Freund, S. Mizuno. Index.

This article is a continuation of the paper "Inventory Control and Regenerative processes: Theory" (Bazsa et al.; 1998) and presents closed form expressions for Laplace transforms associated with the cost functions of the classical single item inventory models with indivisible items, a fixed lead time and backlogging. For given instances of these inventory control models these Laplace transforms will be used as input functions in a newly developed Laplace transform inversion algorithm (Iseger; A new method for inverting Laplace transforms; 1998) which yields highly accurate computational results of the associated cost functions.