×

MM algorithms for geometric and signomial programming. (English) Zbl 1286.90110

Summary: This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for an optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate that the MM algorithm derived can converge to a boundary point or to one point of a continuum of minimum points. Conditions under which the minimum point is unique or occurs in the interior of parameter space are proved for geometric programming. Convergence to an interior point occurs at a linear rate. Finally, the MM framework easily accommodates equality and inequality constraints of signomial type. For the most important special case, the constrained quadratic programming, the MM algorithm involves very simple updates.

MSC:

90C25 Convex programming
26D07 Inequalities involving other types of functions
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific (1999) · Zbl 1015.90077
[2] Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, New York (2000) · Zbl 0953.90001 · doi:10.1007/978-1-4757-9859-3
[3] Boyd, S., Kim, S.J., Vandenberghe, L., Hassibi, A.: A tutorial on geometric programming. Optim. Eng. 8, 67-127 (2007) · Zbl 1178.90270 · doi:10.1007/s11081-007-9001-7
[4] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[5] del Mar Hershenson, M., Boyd, S.P., Lee, T.H.: Optimal design of a CMOS op-amp via geometric programming. IEEE Trans Comput. Aided Des. 20, 1-21 (2001) · doi:10.1109/43.905671
[6] Ecker, J.G.: Geometric programming: methods, computations and applications. SIAM Rev. 22, 338-362 (1980) · Zbl 0438.90088 · doi:10.1137/1022058
[7] Feigin, P.D., Passy, U.: The geometric programming dual to the extinction probability problem in simple branching processes. Ann. Prob. 9, 498-503 (1981) · Zbl 0474.60069 · doi:10.1214/aop/1176994422
[8] Hoffman, K.: Analysis in Euclidean Space. Prentice-Hall, Englewood Cliffs (1975) · Zbl 0314.26001
[9] Hunter, D.R., Lange, K.: A tutorial on MM algorithms. Am. Stat. 58, 30-37 (2004) · doi:10.1198/0003130042836
[10] Lange, K.: Optimization. Springer, New York (2004) · Zbl 1140.90004 · doi:10.1007/978-1-4757-4182-7
[11] Lange, K., Hunter, D.R., Yang, I.: Optimization transfer using surrogate objective functions (with discussion). J Comput Graph. Stat. 9, 1-59 (2000)
[12] Mazumdar, M., Jefferson, T.R.: Maximum likelihood estimates for multinomial probabilities via geometric programming. Biometrika 70, 257-261 (1983) · Zbl 0502.62035 · doi:10.1093/biomet/70.1.257
[13] Nocedal, J., Wright, S.J.: Numer. Optim. Springer, Berlin (1999) · Zbl 0930.65067 · doi:10.1007/b98874
[14] Passy, U., Wilde, D.J.: A geometric programming algorithm for solving chemical equilibrium problems. SIAM J Appl Math. 16, 363-373 (1968) · doi:10.1137/0116030
[15] Peressini, A.L., Sullivan, F.E., Uhl, J.J. Jr.: The Mathematics of Nonlinear Programming. Springer, New York (1988) · Zbl 0663.90054
[16] Peterson, E.L.: Geometric programming. SIAM Rev. 18, 338-362 (1976) · Zbl 0331.90057 · doi:10.1137/1018001
[17] Ruszczynski, A.: Optimization. Princeton University Press, Princeton (2006) · Zbl 1108.90001
[18] Sha, F., Saul, L.K., Lee, D.D.: Multiplicative updates for nonnegative quadratic programming in support vector machines. In: Becker, S., Thrun, S., Obermayer, K. (eds.) Advances in Neural Information Processing Systems, vol. 15, pp. 1065-1073. MIT Press, Cambridge
[19] Steele, J.M.: The Cauchy-Schwarz Master Class: An Introduction to the Art of Inequalities. Cambridge University Press and the Mathematical Association of America, Cambridge (2004) · Zbl 1060.26023 · doi:10.1017/CBO9780511817106
[20] Wang, Y., Zhang, K., Shen, P.: A new type of condensation curvilinear path algorithm for unconstrained generalized geometric programming. Math. Comput. Model. 35, 1209-1219 (2002) · Zbl 1176.90474 · doi:10.1016/S0895-7177(02)00080-8
[21] Zhou, H., Alexander, D., Lange, K.L.: A quasi-Newton acceleration method for high-dimensional optimization algorithms. Stat. Comput. 21, 173-261 (2011) · Zbl 1284.90095 · doi:10.1007/s11222-009-9166-3
[22] Zhou, H., Lange, K.L.: MM algorithms for some discrete multivariate distributions. J. Comput. Graph. Stat 19(3), 645-665 (2010) · doi:10.1198/jcgs.2010.09014
[23] Zhou, H., Lange, K.L.: A fast procedure for calculating importance weights in bootstrap sampling. Comput. Stat. Data Anal. 55, 26-33 (2011) · Zbl 1247.62125 · doi:10.1016/j.csda.2010.04.019
[24] Zhou, H., Lange, K.L.: Path following in the exact penalty method of convex programming. arXiv:1201.3593 (2011) · Zbl 1343.90063
[25] Zhou, H., Lange, K.L., Suchard, M.A.: Graphical processing units and high-dimensional optimization. Stat. Sci. 25(3), 311-324 (2010) · Zbl 1329.62028 · doi:10.1214/10-STS336
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.