MONOTONICITY OF PRIMAL AND DUAL OBJECTIVE VALUES IN PRIMAL-DUAL INTERIOR-POINT ALGORITHMS

Monotonicity of primal and dual objective values in the framework of p rimal-dual interior-point methods is studied. The primal-dual affine-s caling algorithm is monotone in both objectives. A condition is derive d under which a primal-dual interior-point algorithm with a centering component is monotone. Primal-dual algorithms that are monotone in bot h primal and dual objective values are then proposed, and polynomial t ime bounds are achieved. Some arguments are also provided that show th at several existing primal-dual algorithms use parameters close to one that almost always improves both objectives.