Primal-Dual Interior-Point Methods

By Stephen J. Wright. 1997

Preface Notation 1. Introduction. Linear Programming Primal-Dual Methods The Central Path A Primal-Dual Framework Path-Following Methods Potential-Reduction Methods Infeasible Starting Points Superlinear Convergence Extensions Mehrotra's Predictor-Corrector Algorithm Linear Algebra Issues Karmarkar's Algorithm 2. Background. Linear Programming and Interior-Point Methods Standard Form Optimality Conditions, Duality, and Solution Sets The B {SYMBOL 200 \f "Symbol"} N Partition and Strict Complementarity A Strictly Interior Point Rank of the Matrix A Bases and Vertices Farkas's Lemma and a Proof of the Goldman-Tucker Result The Central Path Background. Primal Method Primal-Dual Methods. Development of the Fundamental Ideas Notes and References 3. Complexity Theory. Polynomial Versus Exponential, Worst Case vs Average Case Storing the Problem Data. Dimension and Size The Turing Machine and Rational Arithmetic Primal-Dual Methods and Rational Arithmetic Linear Programming and Rational Numbers Moving to a Solution from an Interior Point Complexity of Simplex, Ellipsoid, and Interior-Point Methods Polynomial and Strongly Polynomial Algorithms Beyond the Turing Machine Model More on the Real-Number Model and Algebraic Complexity A General Complexity Theorem for Path-Following Methods Notes and References 4. Potential-Reduction Methods. A Primal-Dual Potential-Reduction Algorithm Reducing Forces Convergence A Quadratic Estimate of \Phi _{\rho } along a Feasible Direction Bounding the Coefficients in The Quadratic Approximation An Estimate of the Reduction in \Phi _{\rho } and Polynomial Complexity What About Centrality? Choosing {SYMBOL 114 \f "Symbol"} and {SYMBOL 97 \f "Symbol"} Notes and References 5. Path-Following Algorithms. The Short-Step Path-Following Algorithm Technical Results The Predictor-Corrector Method A Long-Step Path-Following Algorithm Limit Points of the Iteration Sequence Proof of Lemma 5.3 Notes and References 6. Infeasible-Interior-Point Algorithms. The Algorithm Convergence of Algorithm IPF Technical Results I. Bounds on \nu _k \delimiter "026B30D (x^k,s^k) \delimiter "026B30D Technical Results II. Bounds on (D^k)^{-1} \Delta x^k and D^k \Delta s^k Technical Results III. A Uniform Lower Bound on {SYMBOL 97 \f "Symbol"}k Proofs of Theorems 6.1 and 6.2 Limit Points of the Iteration Sequence 7. Superlinear Convergence and Finite Termination. Affine-Scaling Steps An Estimate of ({SYMBOL 68 \f "Symbol"}x, {SYMBOL 68 \f "Symbol"} s). The Feasible Case An Estimate of ({SYMBOL 68 \f "Symbol"} x, {SYMBOL 68 \f "Symbol"} s). The Infeasible Case Algorithm PC Is Superlinear Nearly Quadratic Methods Convergence of Algorithm LPF+ Convergence of the Iteration Sequence {SYMBOL 206 \f "Symbol"}(A,b,c) and Finite Termination A Finite Termination Strategy Recovering an Optimal Basis More on {SYMBOL 206 \f "Symbol"} (A,b,c) Notes and References 8. Extensions. The Monotone LCP Mixed and Horizontal LCP Strict Complementarity and LCP Convex QP Convex Programming Monotone Nonlinear Complementarity and Variational Inequalities Semidefinite Programming Proof of Theorem 8.4. Notes and References 9. Detecting Infeasibility. Self-Duality The Simplified HSD Form The HSDl Form Identifying a Solution-Free Region Implementations of the HSD Formulations Notes and References 10. Practical Aspects of Primal-Dual Algorithms. Motivation for Mehrotra's Algorithm The Algorithm Superquadratic Convergence Second-Order Trajectory-Following Methods Higher-Order Methods Further Enhancements Notes and References 11. Implementations. Three Forms of the Step Equation The Cholesky Factorization Sparse Cholesky Factorization. Minimum-Degree Orderings Other Orderings Small Pivots in the Cholesky Factorization Dense Columns in A The Augmented System Formulat

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

OptNet: Differentiable Optimization as a Layer in Neural Networks (2017, methodology): “…paper, we do not unroll a optimization procedure but instead solve (constrained) optimization problems exactly (to numerical precision) using an interior point methods (Wright, 1997), and then analytically derive expressions for the gradients using the matrix differential of the KKT conditions.”
Input Convex Neural Networks (2016, methodology): “…to solve such problems require that we form and in-vert structured matrices with blocks such as W Ti W i — the case for most interior-point methods (Wright, 1997) or even approximate algorithms such as the alternating direction method of multipliers (Boyd et al., 2011) — which are large dense…”
An online active set strategy to overcome the limitations of explicit MPC (2008, methodology): “[7], have emerged as a strong competitor to active set methods, and have also been proposed for the use in MPC [8].”
Formulation and solution of some plasticity problems as conic programs (2007, methodology): “Thus, the standard interior-point paradigm, e.g., (Nash and Sofer, 1996; Wright, 1997; Vanderbei, 2001), makes extensive use of Lagrange multiplier techniques and Koiter’s methodology then follows naturally.”
Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems (2007, background): “In [11], the problems (5) and (1) are solved by first reformulating them as " perturbed linear programs " (which are linear programs with additional terms in the objective which are squared norms of the unknowns), then applying a standard primal-dual IP approach [60].”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “which can often be efficiently solved by simplex or interior-point methods [30,103, 105,151,155].”
Optimal power flow: a bibliographic survey I (2012, background): “We refer the interested reader to Nocedal and Wright (2006) for additional discussion and references regarding the convergence of these methods, including proofs of convergence for those algorithms marked “yes” for global convergence.”
Computational Complexity Certification for Real-Time MPC With Input Constraints Based on the Fast Gradient Method (2012, unknown): “Interior point methods most commonly come in barrier and primal-dual variants using a short-step, long-step or predictorcorrector path-following scheme (see [24], [25]).”
The interior-point revolution in optimization: History, recent developments, and lasting consequences (2004, methodology): “For a detailed discussion of many aspects of primal-dual methods, see [ 41 ].”
DAKOTA, A Multilevel Parallel Object-Oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis Version 3.0 Reference Manual (2001, unknown): “See[91] for the definition of central path.”
Interior-Point Gradient Method for Large-Scale Totally Nonnegative Least Squares Problems (2005, methodology): “Lemma 1. Let ˆ �k and ��k be defined as in the Step ( 2 ) of the IPG Algorithm.”
Robust Optimal Power Flow Solution Using Trust Region and Interior-Point Methods (2011, methodology): “In this paper, the latter approach is followed; thus, the Byrd-Omojokun trust region technique is first used to decompose each trust region subproblem into two smaller subproblems which are easier to solve, and second an efficient primal-dual interior-point algorithm such as the one described in [17”