SpringerLink
Log in

The Elicited Progressive Decoupling Algorithm: A Note on the Rate of Convergence and a Preliminary Numerical Experiment on the Choice of Parameters

  • SI: Optimization, Convex and Variational Analysis
  • Published:
Set-Valued and Variational Analysis Aims and scope Submit manuscript

Abstract

The paper studies the progressive decoupling algorithm (PDA) of Rockafellar and focuses on the elicited version of the algorithm. Based on a generalized Yosida-regularization of S**arn’s partial inverse of an elicitable operator, it is shown that the elicited progressive decoupling algorithm (EPDA), in a particular nonmonotone setting, linearly converges at a rate that could be viewed as the rate of a rescaled PDA, which may provide certain guidance to the selection of the parameters in computational practice. A preliminary numerical experiment shows that the choice of the elicitation constant has an impact on the efficiency of the EPDA. It is also observed that the influence of the elicitation constant is generally weaker than the proximal constant in the algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(3), 293–318 (1992)

    Article  MathSciNet  Google Scholar 

  2. Lu, Y., Sun, J., Zhang, M., Zhang, Y.: A stochastic variational inequality approach to the Nash equilibrium model of a manufacturer-supplier game under uncertainty. preprint. Department of Analytics and Operations National University of Singapore (2020)

  3. Minty, G.J.: Monotone (nonlinear) operators in Hilbert space. Duke Math. J. 29(3), 341–346 (1962)

    Article  MathSciNet  Google Scholar 

  4. Pennanen, T.: Local convergence of the proximal point algorithm and multiplier methods without monotonicity. Math. Oper. Res. 27(1), 170–191 (2002)

    Article  MathSciNet  Google Scholar 

  5. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)

    Article  MathSciNet  Google Scholar 

  6. S**arn, J. E.: Partial inverse of a monotone operator. Appl. Math. Optim. 10(3), 247–265 (1983)

    Article  MathSciNet  Google Scholar 

  7. Rockafellar, R. T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)

    Article  MathSciNet  Google Scholar 

  8. Rockafellar, R.T.: Progressive decoupling of linkages in monotone variational inequalities and convex optimization. In: Proceedings of the 10th International Conference on Nonlinear Analysis and Convex Analysis (Chitose, Japan), pp 1–21 (2017)

  9. Rockafellar, R.T.: Progressive decoupling of linkages in optimization and variational inequalities with elicitable convexity or monotonicity. Set-Valued Var. Anal. 27, 863–893 (2019)

    Article  MathSciNet  Google Scholar 

  10. Rockafellar, R.T., Sun, J.: Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging. Math. Program. 174, 453–471 (2019)

    Article  MathSciNet  Google Scholar 

  11. Rockafellar, R.T., Sun, J.: Solving Lagrangian variational inequalities with applications to stochastic programming. Math. Program. 181, 435–451 (2020)

    Article  MathSciNet  Google Scholar 

  12. Rockafellar, R.T., Wets, R.-J.B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119–147 (1991)

    Article  MathSciNet  Google Scholar 

  13. Rockafellar, R.T., Wets, R.-J.B.: Stochastic variational inequalities: single-stage to multistage. Math. Program. 165(1), 331–360 (2017)

    Article  MathSciNet  Google Scholar 

  14. Zhang, M., Hou, L.S., Sun, J., Yan, A.L.: A model of multistage risk-averse stochastic optimization and its solution by scenario-based decomposition algorithms. Asia-Pacific J. Oper. Res. 37(4), 2040004 (2020). https://doi.org/10.1142/S0217595920400047

    Article  MathSciNet  Google Scholar 

  15. Zhang, M., Sun, J., Xu, H.: Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms. SIAM J. Optim. 29 (3), 1799–1818 (2019)

    Article  MathSciNet  Google Scholar 

Download references

Funding

This work is partially supported by Chinese Academy of Sciences (Grant 292021000088) and National Science Foundation of China (Grant 12101598).

Author information

Authors and Affiliations

  1. Department of Analytics and Operations, School of Business, National University of Singapore, Singapore, 119245, Singapore

    Jie Sun

  2. School of EECMS, Curtin University, Perth, 6845, Australia

    Jie Sun

  3. **njiang Institute of Ecology and Geography, Chinese Academy of Sciences, Urumqi, 830011, China

    Min Zhang

  4. University of Chinese Academy of Sciences, Bei**g, 100049, China

    Min Zhang

Authors
  1. Jie Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Min Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Min Zhang.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sun, J., Zhang, M. The Elicited Progressive Decoupling Algorithm: A Note on the Rate of Convergence and a Preliminary Numerical Experiment on the Choice of Parameters. Set-Valued Var. Anal 29, 997–1018 (2021). https://doi.org/10.1007/s11228-021-00613-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11228-021-00613-0

Keywords

Mathematics Subject Classification (2010)

Search

Navigation