On the convergence of the method of analytic centers when applied to convex quadratic programs
The problem under study is to find \[ \lambda^*=\min \{c^ Tx| x\in P\},\quad P=\{x\in R^ n| f_ i(x)\leq 0,\quad 1\leq i\leq m\}, \] where \(f_ i\), \(1\leq i\leq m\) are convex quadratic functions, int \(P\neq \emptyset\). The method mentioned in the title generates sequences of optimal value estimations \(\lambda_ k>\lambda_{k+1}\downarrow \lambda^*\) and iterative points \[ y_ k\in int(P\cap \{x:c^ Tx\leq \lambda_ k\}). \] Here \(y_{k+1}\) is obtained from \(y_ k\) by one Newton step for solving the system \(D_ x\phi (x,\lambda_{k+1})=0\), \[ \phi (x,\lambda)=-\sum^{m}_{i=1}\ell n(-f_ i(x))-m \ell n(\lambda - c^ Tx). \] The aim of the paper is to prove the following estimation of the speed of convergence \[ 0<c^ Ty_ k-\lambda^*<\epsilon (c^ Ty_ 0-\lambda^*) \] for all \(k\geq const \sqrt{m}\ell n(1/\epsilon)\).
- A method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
- A new continuation method for complementarity problems with uniform P- functions
- A new polynomial-time algorithm for linear programming
- A polynomial method of approximate centers for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- An Algorithm for Convex Quadratic Programming That Requires O(n3.5L) Arithmetic Operations
- Containing and shrinking ellipsoids in the path-following algorithm
- Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
- scientific article; zbMATH DE number 4045481 (Why is no real title available?)
- scientific article; zbMATH DE number 4049377 (Why is no real title available?)
- scientific article; zbMATH DE number 4076974 (Why is no real title available?)
- scientific article; zbMATH DE number 4102820 (Why is no real title available?)
- scientific article; zbMATH DE number 4121759 (Why is no real title available?)
- scientific article; zbMATH DE number 4193461 (Why is no real title available?)
- scientific article; zbMATH DE number 4197759 (Why is no real title available?)
- La méthode des centres dans un espace topologique
- On the convergence of the method of analytic centers when applied to convex quadratic programs
- The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
- On the convergence of Han's method for convex programming with quadratic objective
- Interior-point methods for convex programming
- Quadratically constrained convex quadratic programmes: Faculty feasible regions
- An O(n^ 3 L) primal-dual potential reduction algorithm for solving convex quadratic programs
- On the classical logarithmic barrier function method for a class of smooth convex programming problems
- Interior-point algorithm for quadratically constrained entropy minimization problems
- Utility function programs and optimization over the efficient set in multiple-objective decision making
- Infinite-dimensional quadratic optimization: Interior-point methods and control applications
- A combined homotopy interior point method for convex nonlinear programming
- An analytic center quadratic cut method for the convex quadratic feasibility problem
- Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
- A polynomial time dual algorithm for the Euclidean multifacility location problem
- A cutting plane algorithm for convex programming that uses analytic centers
- Complexity analysis for certain convex programming problems
- On computing the center of a convex quadratically constrained set
- On the convergence of the method of analytic centers when applied to convex quadratic programs
- An exterior point polynomial-time algorithm for convex quadratic programming
- scientific article; zbMATH DE number 4162679 (Why is no real title available?)
- A method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
- scientific article; zbMATH DE number 45207 (Why is no real title available?)
- A second order affine scaling algorithm for the geometric programming dual with logarithmic barrier
- Impproving the rate of convergence of the logarithmic barrier function method
- A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming
- scientific article; zbMATH DE number 4114380 (Why is no real title available?)
- scientific article; zbMATH DE number 4121759 (Why is no real title available?)
- scientific article; zbMATH DE number 4197758 (Why is no real title available?)
- Properties Of Primal Interior Point Methods For QP∗
- Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
- An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming
- A long-step barrier method for convex quadratic programming
This page was built for publication: On the convergence of the method of analytic centers when applied to convex quadratic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277366)
