Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming

We present a variant of Karmarkar's algorithm for block-angular structured linear programs, such as stochastic linear programs. By computing the projection efficiently, we give a worst-case bound on the order of the running time that can be an order of magnitude better than that of Karmarkar's standard algorithm. Further implications for approximations and very large-scale problems are given.

• 저널Management Science · 34(12) · 1472–1479
• 토픽Risk and Portfolio Optimization · Management Science and Operations Research
• DOI10.1287/mnsc.34.12.1472
• 저자John R. Birge, Liqun Qi