## Complexity in Numerical OptimizationComputational 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 |

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 |

### Other editions - View all

### Common terms and phrases

6-near-planar graphs analytic center applied approximation algorithm assume combinatorial optimization complexity concave concave function consider constant constraints construct convex function corresponding cost decision problem decomposition defined definition denote dimensional algorithm edges ellipsoid evaluation exists feasible finite flow problem graph G Hence heuristic hyperplane implies inequality input integer interior point Jacobian Lawler Lemma Lenstra linear programming lower bound Management Science Mathematics matrix maximizer minimize minimum negative instances Newton's method node NP-complete NP-hard number of iterations number of tardy O(nlogn objective function obtain Operations Research optimal solution optimization problem parametric Pardalos path planar graphs polynomial-time positive instances Proof quadratic programming reverse mode Rinnooy satisfying scheduling problems sequence single machine solve spanning tree Steiner ratio strongly polynomial structure tree subset tardy tardy jobs Theorem TICM TICM's Traveling Salesman Problem variables vector vertex vertices weight witness ray zero

### 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