Optimization Online


Stochastic infinity norm optimization and self-concordant primal interior-point algorithms

Baha Alzalg (alzalg.1***at***osu.edu)
Karima Tamsaouete (kry9180336***at***ju.edu.jo)

Abstract: 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.

Keywords: Convex programming, Infinity norm optimization, Stochastic programming, Interior-point methods, Polynomial-time complexity

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Nonlinear Optimization

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 11/22/2021
Entry Accepted: 11/22/2021
Entry Last Modified: 12/04/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society