Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this paper, a proximal alternating direction method of multipliers is proposed for solving a minimization problem with Lipschitz nonconvex constraints. Such problems are raised in many engineering fields, such as the analytical global placement of very large scale integrated circuit design. The proposed method is essentially a new application of the classical proximal alternating direction method of multipliers. We prove that, under some suitable conditions, any subsequence of the sequence generated by the proposed method globally converges to a Karush–Kuhn–Tucker point of the problem. We also present a practical implementation of the method using a certain self-adaptive rule of the proximal parameters. The proposed method is used as a global placement method in a placer of very large scale integrated circuit design. Preliminary numerical results indicate that, compared with some state-of-the-art global placement methods, the proposed method is applicable and efficient.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Antipin, A.S.: Gradient approach of computing fixed points of equilibrium problems. J. Glob. Optim. 24(3), 285–309 (2002)

    Article  MathSciNet  Google Scholar 

  2. Antipin, A.S.: Extra-proximal methods for solving two-person nonzero-sum games. Math. Program. 120, 147–177 (2009)

    Article  MathSciNet  Google Scholar 

  3. Agnihotri, A.R., Ono, S., Li, C., Yildiz, M.C., Khatkhate, A., Koh, C.K., Madden, P.H.: Recursive bisection placement: feng shui 5.0 implementation detail. In: Proceeding of the International Symposium on Physical Design, pp. 230–232 (2005)

  4. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    Book  Google Scholar 

  5. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2010)

    Article  Google Scholar 

  6. Bertesekas, D.P., Tseng, P.: Partial proximal minimization algorithms for convex programming. SIAM J. Optim. 4(3), 551–572 (1994)

    Article  MathSciNet  Google Scholar 

  7. Bertesekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press. Inc., New York (1996)

    Google Scholar 

  8. Chan, T., Cong, J., Shinnerl, J., Sze, K., Xie, M.: mPL6: Enhanced multilevel mixed-sized placement. In: Proceeding of the International Symposium on Physical Design, pp. 212–214 (2006)

  9. Chen, C.H., He, B.S., Yuan, X.M.: Matrix completion via alternating direction methods. IMA J. Numer. Anal. 32, 227–245 (2012)

    Article  MathSciNet  Google Scholar 

  10. Chen, T.C., Jiang, Z.W., Hsu, T.C., Chen, H.C., Chang, Y.W.: NTUplace3: an analytical placer for large-scale mixed-size design with preplaced blocks and density constraints. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(7), 1228–1240 (2008)

    Article  Google Scholar 

  11. Chu, C.: Placement. In: Wang L.T., Chang Y.W., Cheng K.T. (eds.) Electronic Design Automation: Synthesis, Verification, and Testing, chap. 11, pp. 635–684. Elsevier, Morgan Kaufmann (2008)

  12. Chang, Y.W., Jiang, Z.W., Chen, T.C.: Essential issues in analytical placement algorithms. Inf. Media Technol. 4(4), 815–836 (2009)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. Eckstein, J.: Some saddle-function splitting methods for convex programming. Optim. Methods Softw. 4, 75–83 (1994)

    Article  MathSciNet  Google Scholar 

  15. Eckstein, J., Fukushima, M.: Some reformulations and applications of the alternating direction method of multipliers. In: Hager, W.W., Hearn, D.W., Pardalos, Panos M. (eds.) Large Scale Optimization: State of the Art, pp. 115–134. Kluwer Academic Publishers, Dordrecht (1994)

    Chapter  Google Scholar 

  16. Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, New York (1984)

    Book  Google Scholar 

  17. He, B.S., Liao, L.Z., Han, D.R., Yang, H.: A new inexact alternating directions method for monotone variational inequalities. Math. Program. 92(1), 103–118 (2002)

    Article  MathSciNet  Google Scholar 

  18. He, B.S., Liao, L.Z., Qian, M.J.: Alternating projection based prediction-correction methods for structured variational inequalities. J. Comput. Math. 24, 693–710 (2006)

    MathSciNet  Google Scholar 

  19. Karamardian, S., Schaible, S.: Seven kinds of monotone maps. J. Optim. Theory Appl. 66(1), 37–46 (1990)

    Article  MathSciNet  Google Scholar 

  20. Kaplan, A., Tichatschke, R.: Proximal point methods and nonconvex optimization. J. Glob. Optim. 13, 389–406 (1998)

    Article  MathSciNet  Google Scholar 

  21. Martinet, B.: Regularisation d’indquations variationelles par approximations successives. Revue Francaise d’Automatique et Informatique Recherche Opérationelle 4, 154–159 (1970)

    MathSciNet  Google Scholar 

  22. Martinet, B.: Determination approch\(\acute{e}\)e d’un point fixe d’une application pseudo-contractante. Compte Rendu Academie des Sciences de Paris 274, 163–165 (1972)

    MathSciNet  Google Scholar 

  23. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Science & Business Media, LLC (2006)

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  25. Roy, J.A., Papa, D.A., Adya, S.N., Chan, H.H., Ng, A.N., Lu, J.F., Markov, I.L.: Capo: robust and scalable open-source min-cut floorplacer. In: Proceeding of International Symposium on Physical Design, pp. 224–227 (2005)

  26. Viswanathan, N., Pan, M., Chu, C.: Fastplace3.0: a fast multilevel quadratic placement algorithm with placement congestion control. In: Proceeding of Asia and South Pacific Design Automation Conference, pp. 135–140 (2007)

  27. Xu, M.H.: Proximal alternating directions method for structured variational inequalities. J. Optim. Theory Appl. 134(1), 107–117 (2009)

    Article  Google Scholar 

  28. Yang, J.F., Sun, D.F., Toh, K.C.: A proximal point algorithm for log-determinant optimization with group Lasso regularization. SIAM J. Optim. 23(2), 857–893 (2013)

    Article  MathSciNet  Google Scholar 

  29. Yuan, X.M.: An improved proximal alternating direction method for monotone variational inequalities with separable structure. Comput. Optim. Appl. 49(1), 17–29 (2011)

    Article  MathSciNet  Google Scholar 

  30. IBM standard cell benchmarks, available online at: http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.public.iastate.edu/nataraj/ISPD04-Bench.html

Download references

Acknowledgments

The authors are very grateful to the editor and the anonymous reviewers for their constructive comments which play a crucial role on the final version of this paper.

Author information

Authors and Affiliations

  1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou, 350108, People’s Republic of China

    Zheng Peng, Jianli Chen & Wenxing Zhu

Authors
  1. Zheng Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jianli Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenxing Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zheng Peng.

Additional information

This work was supported by the Natural Science Foundation of China (61170308), Major Science Foundation of FuJian Province Department of Education (JA14037), and Talent Foundation of Fuzhou University (XRC-1043).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Peng, Z., Chen, J. & Zhu, W. A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints. J Glob Optim 62, 711–728 (2015). https://doi.org/10.1007/s10898-015-0287-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-015-0287-2

Keywords

Search

Navigation