scientific article; zbMATH DE number 1131479
The book is concerned with interior point methods for solving optimization problems. This area has received much attention recently for various reasons. Many researchers have found some of these methods to be far more efficient than the simplex method on a wide range of large calculations, while its polynomial time properties are fundamental to research on complexity. The author highlights in this book the underlying interior point geometry, combinatorics, and the potential theory for convex inequalities. The worst-case complexity bound for interior point algorithms is studied. Some of the recent results on average case analysis and asymptotic analysis are also presented. The discussion on several effective implementation techniques frequently used in interior point linear programming software is an added feature of the book. The book contains ten chapters and each chapter is followed by `Notes' and `Exercises'. The first chapter is an introduction and discusses some of the mathematical preliminaries required in subsequent chapters. Several decision and optimization problems, models of computation and several basic numerical procedures used in the subsequent chapters are also presented here. The second chapter deals with the geometry of inequalities and interior point algorithms. Some of the important concepts, such as `Center', `Volume' and potential of a polytope are discussed here. The third chapter is devoted to the computation of analytic center. The fourth chapter considers five interior point linear programming algorithms, namely. Karmarkar's projective algorithm, the path-following algorithm, the potential reduction algorithm, the primal-dual algorithm including the predictor-corrector algorithm, and the affine scaling algorithm. The fifth chapter deals with the worst-case complexity bound for interior point algorithms. The main issues discussed in this chapter are arithmetic operation, termination and initialization techniques. The sixth chapter is devoted to the study of average case analysis where the idea is to obtain rigorous probabilistic bounds on the number of iterations required by an algorithm to reach some termination criteria. The average complexity results of interior point algorithms for solving the random linear programming model of Todd are presented here. Chapter 7 discusses asymptotic convergence analysis and contains complexity results obtained from applying a predictor-corrector algorithm to both linear programming as well as linear complementarity problems. The eighth chapter illustrates the working of potential functions and interior point algorithms for solving broader convex optimization problems including positive semi-definite programming and monotone complementarity problems. Chapter 9 deals with the working of interior point algorithms for solving non-convex optimization problems including fractional programming and general quadratic programming problems and suggests some directions for future research. The tenth chapter is devoted to the discussion of several effective implementation techniques such as the presolver process, the high-order predictor corrector method, the homogeneous and self-dual method, and the optimal basis identifier. The last section on `Notes' in each chapter is useful and keeps the reader informed about the developments in the areas covered. The author could have given hints to the selected exercises listed at the end of each chapter and included them in an appendix at the end for the benefit of a reader.
- scientific article; zbMATH DE number 123966
- Interior point algorithms in linear optimization
- scientific article; zbMATH DE number 1017028
- scientific article; zbMATH DE number 590363
- scientific article; zbMATH DE number 1064586
- scientific article; zbMATH DE number 800120
- scientific article; zbMATH DE number 1069182
- scientific article; zbMATH DE number 269555
- Interior point techniques in optimization. Complementarity, sensitivity and algorithms
- scientific article; zbMATH DE number 1889340
- Note on implementing the new sphere method for LP using matrix inversions sparingly
- Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions
- A polynomial-time algorithm for linear optimization based on a new class of kernel functions
- Exploring complexity of large update interior-point methods for \(P_*(\kappa )\) linear complementarity problem based on kernel function
- A redundant Klee-Minty construction with all the redundant constraints touching the feasible region
- Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming
- Partitioning multiple objective optimal solutions with applications in radiotherapy design
- Stabilized column generation
- Interior point techniques in optimization. Complementarity, sensitivity and algorithms
- Euclidean Jordan algebras and interior-point algorithms
- Specialized fast algorithms for IQC feasibility and optimization problems.
- A primal-dual interior point method for parametric semidefinite programming problems
- Interior-point methods
- An SQP method for general nonlinear complementarity problems
- A new algorithm for geometric programming based on the linear structure of its dual problem.
- Pivot versus interior point methods: Pros and cons
- Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier
- An optimal approach for the critical node problem using semidefinite programming
- A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimization
- A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming
- Complexity analysis of a full-{N}ewton step interior-point method for linear optimization
- Bin packing under linear constraints
- Knapsack with variable weights satisfying linear constraints
- Autonomous trajectory planning for space vehicles with a Newton-Kantorovich/convex programming approach
- The flattened aggregate constraint homotopy method for nonlinear programming problems with many nonlinear constraints
- Complexity of interior point methods for a class of linear complementarity problems using a kernel function with trigonometric growth term
- A mixed 0--1 LP for index tracking problem with CVaR risk constraints
- The asymptotic optimal partition and extensions of the nonsubstitution theorem
- On self-regular IPMs (with comments and rejoinder)
- Large-step interior-point algorithm for linear optimization based on a new wide neighbourhood
- A new class of polynomial primal-dual methods for linear and semidefinite optimization
- Analytic centers and repelling inequalities
- Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
- A level set approach for the solution of a state-constrained optimal control problem
- On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming
- Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
- Second-order cone interior-point method for quasistatic and moderate dynamic cohesive fracture
- A survey on the high convergence orders and computational convergence orders of sequences
- A full-Newton step infeasible interior-point algorithm based on darvay directions for linear optimization
- Linear operators and positive semidefiniteness of symmetric tensor spaces
- A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound
- A full-Newton step infeasible interior-point method for the special weighted linear complementarity problem
- A wide neighborhood interior-point algorithm based on the trigonometric kernel function
- An interior-point algorithm for linear programming with optimal selection of centering parameter and step size
- An infeasible interior-point arc-search algorithm for nonlinear constrained optimization
- A full-modified-Newton step O(n) infeasible interior-point method for the special weighted linear complementarity problem
- A primal-dual interior-point relaxation method with global and rapidly local convergence for nonlinear programs
- Novel kernel function with a hyperbolic barrier term to primal-dual interior point algorithm for SDP problems
- An interior-point algorithm for semidefinite least-squares problems.
- A logarithmic barrier interior-point method based on majorant functions for second-order cone programming
- The multiproximal linearization method for convex composite problems
- A full-Newton step infeasible interior-point method based on a trigonometric kernel function without centering steps
- A corrector-predictor interior-point method with new search direction for linear optimization
- A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization
- A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization
- A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function
- A full-Newton step feasible interior-point algorithm for \(P_\ast(\kappa)\)-linear complementarity problems
- Optimal assignment schemes for general access structures based on linear programming
- A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP
- Iterative solution methods for mesh approximation of control and state constrained optimal control problem with observation in a part of the domain
- A variational principle for computing nonequilibrium fluxes and potentials in genome-scale biochemical networks
- Tensor complementarity problems. II: Solution methods
- On the approximability of the two-phase knapsack problem
- An oracle for the discrete-time integral quadratic constraint problem
- Simplified infeasible interior-point algorithm for linear optimization based on a simple function
- A new portfolio rebalancing model with transaction costs
- Generalized affine scaling algorithms for linear programming problems
- On saddle points in semidefinite optimization via separation scheme
- An interior-point method for P_*()-linear complementarity problem based on a trigonometric kernel function
- An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs
- On the convergence of a predictor-corrector variant algorithm
- Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly
- A still simpler way of introducing interior-point method for linear programming
- Random matrix theory for the analysis of the performance of an analog computer: a scaling theory
- An empirical evaluation of walk-and-round heuristics for mixed integer linear programs
- Two wide neighborhood interior-point methods for symmetric cone optimization
- Kernel-function-based primal-dual interior-point methods for convex quadratic optimization over symmetric cone
- On a box-constrained linear symmetric cone optimization problem
- Optimal experimental design and some related control problems
- A cutting plane method for solving KYP-SDPs
- On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems
- New complexity analysis of IIPMs for linear optimization based on a specific self-regular function
- An infeasible interior-point algorithm with full-Newton step for linear optimization
- Dual versus primal-dual interior-point methods for linear and conic programming
- A constraint generation algorithm for large scale linear programs using multiple-points separation
- Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function
- Fast linear iterations for distributed averaging
- Approximate augmented Lagrangian functions and nonlinear semidefinite programs
- The complexity of self-regular proximity based infeasible IPMs
- Computational methods for solving fully fuzzy linear systems
- A predictor-corrector algorithm for linear optimization based on a modified Newton direction
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- LFTB: an efficient algorithm to bound linear fractional transformations
- An infeasible primal-dual interior point algorithm for linear programs based on logarithmic equivalent transformation
- Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming
- A primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils
- Interior-point algorithms: creation history, research results, applications, and prospects
- A mathematical view of interior-point methods in convex optimization
- A fixed point iterative approach to integer programming and its distributed computation
- A new feasible interior-point algorithm with full step for linear optimization based on a simple function
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382667)