Author
Listed:
- Dillard Robertson
(Georgia Institute of Technology)
- Pengfei Cheng
(Georgia Institute of Technology)
- Joseph K. Scott
(Georgia Institute of Technology)
Abstract
This paper analyzes the convergence rate of decomposition algorithms for globally solving nonconvex stochastic programming problems. We focus on two recent algorithms, termed CZ (Cao and Zavala in J Glob Optim 75:393–416, 2019) and LG (Li and Grossmann in J Glob Optim 75:247–272, 2019), that guarantee global optimality while achieving a favorable decomposed scaling with respect to the number of scenarios. Both methods project the problem into the space of first-stage decisions and apply a spatial-B&B search in this reduced space. Consequently, we observe that they are subject to the results of prior studies on the efficiency of general spatial-B&B algorithms. Such studies have concluded that, to avoid very slow convergence due to the cluster problem, it is necessary (but not sufficient) for the B&B lower bounding problems to have a sufficiently high Hausdorff convergence order. We apply this concept to the CZ and LG decomposition algorithms by first arguing that their lower bounding procedures can be interpreted as defining relaxations in the reduced space of first-stage decisions, and then analyzing the Hausdorff convergence of these relaxations in detail. The results are found to depend strongly on the regularity of the recourse optimal value functions. The relaxations used by CZ are found to be first-order convergent or less, while second order is generally necessary to avoid clustering. In contrast, the relaxations used by LG achieve the highest order possible within the decomposition framework we consider, which is second order when the value functions are smooth, but first order or less otherwise. Unfortunately, these functions are only guaranteed to be lower semi-continuous under standard assumptions. This alludes to a larger limitation of the projection-based decomposition approach, which is discussed at length.
Suggested Citation
Dillard Robertson & Pengfei Cheng & Joseph K. Scott, 2025.
"On the convergence order of value function relaxations used in decomposition-based global optimization of nonconvex stochastic programs,"
Journal of Global Optimization, Springer, vol. 91(4), pages 701-742, April.
Handle:
RePEc:spr:jglopt:v:91:y:2025:i:4:d:10.1007_s10898-024-01458-1
DOI: 10.1007/s10898-024-01458-1
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:91:y:2025:i:4:d:10.1007_s10898-024-01458-1. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.