A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints. (English) Zbl 1330.90088

Summary: 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.


90C26 Nonconvex programming, global optimization
Full Text: DOI


[1] Antipin, AS, Gradient approach of computing fixed points of equilibrium problems, J. Glob. Optim., 24, 285-309, (2002) · Zbl 1056.91001
[2] Antipin, AS, Extra-proximal methods for solving two-person nonzero-sum games, Math. Program., 120, 147-177, (2009) · Zbl 1163.91303
[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) · Zbl 1133.65041
[4] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[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-122, (2010) · Zbl 1229.90122
[6] Bertesekas, DP; Tseng, P, Partial proximal minimization algorithms for convex programming, SIAM J. Optim., 4, 551-572, (1994) · Zbl 0819.90069
[7] Bertesekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press. Inc., New York (1996)
[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) · Zbl 0916.90224
[9] Chen, CH; He, BS; Yuan, XM, Matrix completion via alternating direction methods, IMA J. Numer. Anal., 32, 227-245, (2012) · Zbl 1236.65043
[10] Chen, TC; Jiang, ZW; Hsu, TC; Chen, HC; Chang, YW, 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, 1228-1240, (2008)
[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, YW; Jiang, ZW; Chen, TC, Essential issues in analytical placement algorithms, Inf. Media Technol., 4, 815-836, (2009)
[13] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073
[14] Eckstein, J, Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4, 75-83, (1994)
[15] Eckstein, J; Fukushima, M; Hager, WW (ed.); Hearn, DW (ed.); Pardalos, Panos M (ed.), Some reformulations and applications of the alternating direction method of multipliers, 115-134, (1994), Dordrecht · Zbl 0816.90109
[16] Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, New York (1984) · Zbl 0536.65054
[17] He, BS; Liao, LZ; Han, DR; Yang, H, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92, 103-118, (2002) · Zbl 1009.90108
[18] He, BS; Liao, LZ; Qian, MJ, Alternating projection based prediction-correction methods for structured variational inequalities, J. Comput. Math., 24, 693-710, (2006) · Zbl 1133.65041
[19] Karamardian, S; Schaible, S, Seven kinds of monotone maps, J. Optim. Theory Appl., 66, 37-46, (1990) · Zbl 0679.90055
[20] Kaplan, A; Tichatschke, R, Proximal point methods and nonconvex optimization, J. Glob. Optim., 13, 389-406, (1998) · Zbl 0916.90224
[21] Martinet, B, Regularisation d’indquations variationelles par approximations successives, Revue Francaise d’Automatique et Informatique Recherche Opérationelle, 4, 154-159, (1970) · Zbl 0215.21103
[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) · Zbl 0226.47032
[23] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Science & Business Media, LLC (2006) · Zbl 1104.65059
[24] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[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) · Zbl 1163.91303
[27] Xu, MH, Proximal alternating directions method for structured variational inequalities, J. Optim. Theory Appl., 134, 107-117, (2009) · Zbl 1129.49040
[28] Yang, JF; Sun, DF; Toh, KC, A proximal point algorithm for log-determinant optimization with group lasso regularization, SIAM J. Optim., 23, 857-893, (2013) · Zbl 1285.65037
[29] Yuan, XM, An improved proximal alternating direction method for monotone variational inequalities with separable structure, Comput. Optim. Appl., 49, 17-29, (2011) · Zbl 1219.90174
[30] IBM standard cell benchmarks, available online at: http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.public.iastate.edu/nataraj/ISPD04-Bench.html · Zbl 1285.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.