Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support

Sanjay Mehrotra; M. Gokhan Özevin

doi:10.1137/080741380

Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support

Sanjay Mehrotra^*, M. Gokhan Özevin

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

Mehrotra and Özevin [SIAM J. Optim., 19 (2009), pp. 1846-1880] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the equally weighted barrier decomposition proposed and analyzed in [G. Zhao, Math. Program., 90 (2001), pp. 507-536; S. Mehrotra and M. G. Özevin, Oper. Res., 57 (2009), pp. 964-974; S. Mehrotra and M. G. Özevin, SIAM J. Optim., 18 (2007), pp. 206-222]. Here we consider a weighted barrier that allows us to analyze iteration complexity of algorithms in all of the aforementioned publications in a unified framework. In particular, we prove self-concordance parameter values for the weighted barrier and using these values give a worst-case iteration complexity bound for the weighted decomposition algorithm.

Original language	English (US)
Pages (from-to)	2474-2486
Number of pages	13
Journal	SIAM Journal on Optimization
Volume	20
Issue number	5
DOIs	https://doi.org/10.1137/080741380
State	Published - 2010

Keywords

Benders decomposition
Large scale optimization
Linear-quadratic programming
Nondifferentiable convex optimization
Two stage stochastic programming

ASJC Scopus subject areas

Software
Theoretical Computer Science
Applied Mathematics

Access to Document

10.1137/080741380

Cite this

@article{001a2fb5d78f416a82066304d1ef51f2,

title = "Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support",

abstract = "Mehrotra and {\"O}zevin [SIAM J. Optim., 19 (2009), pp. 1846-1880] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the equally weighted barrier decomposition proposed and analyzed in [G. Zhao, Math. Program., 90 (2001), pp. 507-536; S. Mehrotra and M. G. {\"O}zevin, Oper. Res., 57 (2009), pp. 964-974; S. Mehrotra and M. G. {\"O}zevin, SIAM J. Optim., 18 (2007), pp. 206-222]. Here we consider a weighted barrier that allows us to analyze iteration complexity of algorithms in all of the aforementioned publications in a unified framework. In particular, we prove self-concordance parameter values for the weighted barrier and using these values give a worst-case iteration complexity bound for the weighted decomposition algorithm.",

keywords = "Benders decomposition, Large scale optimization, Linear-quadratic programming, Nondifferentiable convex optimization, Two stage stochastic programming",

author = "Sanjay Mehrotra and {\"O}zevin, {M. Gokhan}",

year = "2010",

doi = "10.1137/080741380",

language = "English (US)",

volume = "20",

pages = "2474--2486",

journal = "SIAM Journal on Optimization",

issn = "1052-6234",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support

AU - Mehrotra, Sanjay

AU - Özevin, M. Gokhan

PY - 2010

Y1 - 2010

N2 - Mehrotra and Özevin [SIAM J. Optim., 19 (2009), pp. 1846-1880] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the equally weighted barrier decomposition proposed and analyzed in [G. Zhao, Math. Program., 90 (2001), pp. 507-536; S. Mehrotra and M. G. Özevin, Oper. Res., 57 (2009), pp. 964-974; S. Mehrotra and M. G. Özevin, SIAM J. Optim., 18 (2007), pp. 206-222]. Here we consider a weighted barrier that allows us to analyze iteration complexity of algorithms in all of the aforementioned publications in a unified framework. In particular, we prove self-concordance parameter values for the weighted barrier and using these values give a worst-case iteration complexity bound for the weighted decomposition algorithm.

AB - Mehrotra and Özevin [SIAM J. Optim., 19 (2009), pp. 1846-1880] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the equally weighted barrier decomposition proposed and analyzed in [G. Zhao, Math. Program., 90 (2001), pp. 507-536; S. Mehrotra and M. G. Özevin, Oper. Res., 57 (2009), pp. 964-974; S. Mehrotra and M. G. Özevin, SIAM J. Optim., 18 (2007), pp. 206-222]. Here we consider a weighted barrier that allows us to analyze iteration complexity of algorithms in all of the aforementioned publications in a unified framework. In particular, we prove self-concordance parameter values for the weighted barrier and using these values give a worst-case iteration complexity bound for the weighted decomposition algorithm.

KW - Benders decomposition

KW - Large scale optimization

KW - Linear-quadratic programming

KW - Nondifferentiable convex optimization

KW - Two stage stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=77956077098&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956077098&partnerID=8YFLogxK

U2 - 10.1137/080741380

DO - 10.1137/080741380

M3 - Article

AN - SCOPUS:77956077098

SN - 1052-6234

VL - 20

SP - 2474

EP - 2486

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 5

ER -

Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this