Complexity in Numerical Optimization

Front Cover
World Scientific, 1993 - Mathematics - 511 pages
0 Reviews
Computational complexity, originated from the interactions between computer science and numerical optimization, is one of the major theories that have revolutionized the approach to solving optimization problems and to analyzing their intrinsic difficulty.The main focus of complexity is the study of whether existing algorithms are efficient for the solution of problems, and which problems are likely to be tractable.The quest for developing efficient algorithms leads also to elegant general approaches for solving optimization problems, and reveals surprising connections among problems and their solutions.This book is a collection of articles on recent complexity developments in numerical optimization. The topics covered include complexity of approximation algorithms, new polynomial time algorithms for convex quadratic minimization, interior point algorithms, complexity issues regarding test generation of NP-hard problems, complexity of scheduling problems, min-max, fractional combinatorial optimization, fixed point computations and network flow problems.The collection of articles provide a broad spectrum of the direction in which research is going and help to elucidate the nature of computational complexity in optimization. The book will be a valuable source of information to faculty, students and researchers in numerical optimization and related areas.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Average Performance of a SelfDual Interior Point Algorithm
1
Random model and probabilistic analysis
10
The Complexity of Approximating a Nonlinear Program
16
The complexity of polynomial programming
25
Algorithms for the Least Distance Problem
33
An algorithm based on construction of arrangements
41
A linear time recursive algorithm
48
Appendix
56
Path problems and systems of linear equations
330
Structure trees weighted depth generalized satisfiability
336
Summary and open problems
348
References
349
Parametric Flows Weighted Means of Cuts and Fractional Combinatorial Optimization
351
The maximum meanweight cut problem and related network flow problems
356
Linear fractional combinatorial optimization problems
362
Analysis of Newtons method for the PF problem
372

Work per iteration for the translationalcuts algorithm
63
References
72
Hyperplane queries
80
References
87
MST based heuristics
94
References
102
General convex optimization
108
Resource allocation
114
Conclusions
121
Some Bounds on the Complexity of Gradients Jacobians
128
Generalizations of partial separability
136
The evaluation program and its complexity
147
Results and discussion
154
Summary and conclusion
160
The capacitated case
172
Complexity of Smooth Convex Programming and its Applications
180
Applications to convex quadratic programs
191
A Classification of Static Scheduling Problems
203
References
231
An 0nL Iteration Algorithm for Computing Bounds in Quadratic
254
Complexity analysis
261
Conclusions
267
3 A G Ei Ci Ei wiOi Zmax mui nux
274
A Ei i Ei fiCj imaxi nuii Cmji
280
6 A e E E E ISEi f E
287
Complexity tables
294
DVUP
302
LinkDelayx 6
309
DVDP
318
Introduction
324
Analysis of Newtons method for the uniform PF problem
377
Concluding remarks
383
Analysis of a Random Cut Test Instance Generator for the TSP
387
Introduction
388
Versions of the general TSP and class Dp
389
Polyhedral relaxations and random cut generators
391
Exposed instances
395
Intermediate TSPs
398
Well formed instances and promises
400
References
403
Some Complexity Issues Involved in the Construction of Test Cases for NPhard Problems
406
Definitions
408
Generability
409
Generation of hard instances
417
References
426
Maximizing NonLinear Concave Functions in Fixed Dimension
429
Maximizing one dimensional concave functions
432
A two dimensional algorithm
435
The general algorithm
438
Applications
445
Complexity for the class FiL
452
Conclusion
459
A mathematical framework
467
Two old barrier functions
475
The hybrid barrier function
484
Polynomial Time Weak Approximation Algorithms for Quadratic
490
Conclusions
498
The minmax shortest path problem
504
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 488 - in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant

References to this book

All Book Search results »

Bibliographic information