Solving linear systems involved in constrained optimization
The interior point methods for large scale linear, quadratic and convex programming need \((n+ m)\times (n+ m)\) systems of linear equations to be solved in each iteration. The author proposes an inexpensive iterative method for solving those systems which guarantees exact solutions to the last \(m\) equations. Current implementations solve the systems by considering an equivalent system in each iteration and reducing the task to solving an \((m\times m)\) system which has to be solved exactly and therefore the iterative methods are avoided. The typical approach uses the Cholesky factorization in every iteration step which makes the computation costly and sometimes impractical. The new algorithm, proposed in this paper, uses only one Cholesky factorization at the initial step of the interior point algorithm. The description of the method and its convergence analysis are presented. Some implementation issues and the possibility to combine the proposed method with another iterative method such as the conjugate gradient method in order to have the advantages of both are discussed. Some preliminary numerical experiments, where the objective functions are widely used functions in economics, physics and engineering are shortly reported in the last section.
- Parallel Processing and Applied Mathematics
- An interior point method for solving systems of linear equations and inequalities
- Block preconditioners for linear systems in interior point methods for convex constrained optimization
- Preconditioning indefinite systems in interior point methods for optimization
- A Faster Method For Computing Karmarkar's Projections For Large Number of Constraints
- A Centered Projective Algorithm for Linear Programming
- A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
- Containing and shrinking ellipsoids in the path-following algorithm
- Efficent line search algorithm for unconstrained optimization
- scientific article; zbMATH DE number 45971 (Why is no real title available?)
- scientific article; zbMATH DE number 617926 (Why is no real title available?)
- On some efficient interior point methods for nonlinear convex programming
- On the finite convergence of interior-point algorithms for linear programming
- Solution of P₀ -Matrix Linear Complementarity Problems Using a potential Reduction Algorithm
- The Mehrotra Predictor-Corrector Interior-Point Method As a Perturbed Composite Newton Method
- An interior point method for solving systems of linear equations and inequalities
- Solving linear optimization over arithmetic constraint formula
- Approximate solution of system of equations arising in interior-point methods for bound-constrained optimization
- Signum-function array activated ZNN with easier circuit implementation and finite-time convergence for linear systems solving
- scientific article; zbMATH DE number 3903854 (Why is no real title available?)
- scientific article; zbMATH DE number 3936945 (Why is no real title available?)
- scientific article; zbMATH DE number 554736 (Why is no real title available?)
- A Faster Method For Computing Karmarkar's Projections For Large Number of Constraints
- An Infinitely Summable Series Implementation of Interior Point Methods
- Linear programming with a feasible direction interior point technique for smooth optimization
- Parallel Processing and Applied Mathematics
- A New Stopping Criterion for Krylov Solvers Applied in Interior Point Methods
- A Sherman-Morrison approach to the solution of linear systems
- Finding the orthogonal projection of a point onto an affine subspace
This page was built for publication: Solving linear systems involved in constrained optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1902118)
