Tuesday, 15:15 - 15:40 h, Room: H 2036


Miguel Anjos
Convergence and polynomiality of a primal-dual interior-point algorithm for linear programming with selective addition of inequalities

Coauthor: Alexander Engau


We present the convergence proof and complexity analysis for an interior-point framework that solves linear programming problems by dynamically selecting and adding inequalities. First, we formulate a new primal-dual interior-point algorithm for solving linear programs in nonstandard form with equality and inequality constraints. The algorithm uses a primal-dual path-following predictor-corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of the algorithm is polynomial in the problem dimension.


Talk 1 of the invited session Tue.3.H 2036
"First-derivative and interior methods in convex optimization" [...]
Cluster 4
"Conic programming" [...]


  To apply for USA Payday Loans you don't have to seek the help of relatives or go to a bank. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.