We study the two-stage stochastic infinity norm optimization problem with recourse. First, we study and analyze the algebraic structure of the infinity norm cone, and use its algebra to compute the derivatives of the barrier recourse functions. Then, we show that the barrier recourse functions and the composite barrier functions for this optimization problem are self-concordant families with respect to barrier parameters. These results are used to develop primal decomposition-based interior-point algorithms for this class of stochastic programming problems. Our complexity results for the short- and long-step algorithms show that the dominant complexity terms are linear in the rank of the underlying cone. Despite the nonsymmetry of the infinity norm cone, we also show that the obtained complexity results match (in terms of rank) the best known results in the literature for other well-studied stochastic symmetric cone programs. Finally, we show the efficiency of the proposed algorithm by presenting some numerical experiments on both stochastic uniform facility location problems and randomly-generated problems.
Article
View Algebraic-based primal interior-point algorithms for stochastic infinity norm optimization