×

zbMATH — the first resource for mathematics

Solving nearly-separable quadratic optimization problems as nonsmooth equations. (English) Zbl 1370.90169
Summary: An algorithm for solving nearly-separable quadratic optimization problems (QPs) is presented. The approach is based on applying a semismooth Newton method to solve the implicit complementarity problem arising as the first-order stationarity conditions of such a QP. An important feature of the approach is that, as in dual decomposition methods, separability of the dual function of the QP can be exploited in the search direction computation. Global convergence of the method is promoted by enforcing decrease in component(s) of a Fischer-Burmeister formulation of the complementarity conditions, either via a merit function or through a filter mechanism. The results of numerical experiments when solving convex and nonconvex instances are provided to illustrate the efficacy of the method.

MSC:
90C20 Quadratic programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49M05 Numerical methods based on necessary conditions
49M15 Newton-type methods
49M27 Decomposition methods
49M29 Numerical methods involving duality
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, L., Raghunathan, A. U.: Semismooth equation approach to network utility maximization (NUM). In American Control Conference (ACC), pp. 4795-4801, (2013)
[2] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[3] Bertsekas, D.P.: Convex Optimization Theory. Athena Scientific, Belmont (2009) · Zbl 1242.90001
[4] Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, New York (1997) · Zbl 0892.90142
[5] Bragalli, C; Ambrosio, CD; Lee, J; Lodi, A; Toth, P, On the optimal design of water distribution networks: a practical MINLP approach, Opt. Eng., 13, 219-246, (2012) · Zbl 1293.76045
[6] Ralph, D; Dempe, S, Directional derivatives of the solution of a parametric nonlinear program, Math. Prog., 70, 159-172, (1995) · Zbl 0844.90089
[7] Deng, W., Lai, M.-J., Peng, Z., Yin, W.: Parallel Multi-Block ADMM with \(o(1/k)\) Convergence. Technical report, arXiv:1312.3040 (2014) · Zbl 1398.65121
[8] Dinh, QT; Necoara, I; Diehl, M, Path-following gradient-based decomposition algorithms for separable convex optimization, J. Global Optim., 59, 59-80, (2014) · Zbl 1317.90239
[9] Dinh, QT; Necoara, I; Savorgnan, C; Diehl, M, An inexact perturbed path-following method for Lagrangian decomposition in large-scale separable convex optimization, SIAM J. Optim., 23, 95-125, (2013) · Zbl 1284.90049
[10] Dinh, QT; Savorgnan, C; Diehl, M, Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems, Comput. Optim. Appl., 55, 75-111, (2013) · Zbl 1295.90048
[11] Facchinei, F; Fischer, A; Kanzow, C, Regularity properties of a semismooth reformulation of variational inequalities, SIAM J. Optim., 8, 850-869, (1998) · Zbl 0913.90249
[12] Facchinei, F; Soares, J, A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., 7, 225-247, (1997) · Zbl 0873.90096
[13] Fiacco, AV, Sensitivity analysis for nonlinear programming using penalty methods, Math. Program., 10, 287-311, (1976) · Zbl 0357.90064
[14] Fiacco, A.V., McCormick, G.P.: Nonlinear programming: sequential unconstrained minimization techniques. Class. Appl. Math. Soc. Ind. Appl. Math. (1987) · Zbl 0193.18805
[15] Fischer, A, A special Newton-type optimization method, Optimization, 24, 269-284, (1992) · Zbl 0814.65063
[16] Fletcher, R; Gould, NIM; Leyffer, S; Toint, PhL; Wächter, A, Global convergence of trust-region SQP-filter algorithms for nonlinear programming, SIAM J. Opt., 13, 635-659, (2002) · Zbl 1038.90076
[17] Fletcher, R; Leyffer, S, Nonlinear programming without a penalty function, Math. Program., 91, 239-269, (2002) · Zbl 1049.90088
[18] Fletcher, R., Leyffer, S.: Filter-type algorithms for solving systems of algebraic equations and inequalities. In: High-Performance Algorithms and Software in Nonlinear Optimization, pp. 259-278. Kluwer, Dordrecht, The Netherlands (2003)
[19] Fletcher, R; Leyffer, S; Toint, PhL, On the global convergence of a filter-SQP algorithm, SIAM J. Opt., 13, 44-59, (2002) · Zbl 1029.65063
[20] Frasch, JV; Sager, S; Diehl, M, A parallel quadratic programming method for dynamic optimization problems, Math. Prog. Comput., 7, 289-329, (2015) · Zbl 1321.90094
[21] Gondzio, J; Grothey, A, Parallel interior-point solver for structured quadratic programs: application to financial planning problems, Ann. Oper. Res., 152, 319-339, (2007) · Zbl 1144.90510
[22] Gould, NIM; Leyffer, S; Toint, PhL, A multidimensional filter algorithm for nonlinear equations and nonlinear least squares, SIAM J. Opt., 15, 17-38, (2004) · Zbl 1075.65075
[23] Jiang, H; Qi, L, A new nonsmooth equations approach to nonlinear complementarity problems, SIAM J Control Opt., 35, 178-193, (1997) · Zbl 0872.90097
[24] Kanzow, C; Petra, S, Projected filter trust region methods for a semismooth least squares formulation of mixed complementarity problems, Opt. Methods Softw., 22, 713-735, (2007) · Zbl 1188.90258
[25] Qi, L; Sun, J, A nonsmooth version of newton’s method, Math. Progr., 58, 353-368, (1993) · Zbl 0780.90090
[26] Laird, CD; Biegler, LT; Bock, HG (ed.); Kostina, E (ed.); Phu, HX (ed.); Ranacher, R (ed.), Large-scale nonlinear programming for multi-scenario optimization, 323-336, (2008), Berlin
[27] Luca, T; Facchinei, F; Kanzow, C, A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Progr., 75, 407-439, (1996) · Zbl 0874.90185
[28] Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, Oxford (1991) · Zbl 1256.91002
[29] Munson, TS; Facchinei, F; Ferris, M; Fischer, A; Kanzow, C, The semismooth algorithm for large scale complementarity problems, J. Comput., 13, 294-311, (2001) · Zbl 1238.90123
[30] Necoara, I; Patrascu, A, Iteration complexity analysis of dual first-order methods for conic convex programming, Opt. Methods Softw., 31, 645-678, (2016) · Zbl 1342.90135
[31] Necoara, I; Suykens, JAK, Application of a smoothing technique to decomposition in convex optimization, IEEE Trans. Autom. Control, 53, 2674-2679, (2008) · Zbl 1367.90085
[32] Necoara, I; Suykens, JAK, Application of a smoothing technique to decomposition in convex optimization, IEEE Trans. Autom. Control, 53, 2674-2679, (2008) · Zbl 1367.90085
[33] Necoara, I; Suykens, JAK, Interior-point Lagrangian decomposition method for separable convex optimization, J. Optim. Theory Appl., 143, 567-588, (2009) · Zbl 1184.90126
[34] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Boston (2004) · Zbl 1086.90045
[35] Nesterov, Y, Excessive gap technique in nonsmooth convex minimization, SIAM J Opt., 16, 235-249, (2005) · Zbl 1096.90026
[36] Nesterov, Y, Smooth minimization of non-smooth functions, Math. Progr. (A), 103, 127-152, (2005) · Zbl 1079.90102
[37] Nesterov, Y., Nemirovskii, A.: Interior Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics (SIAM Studies in Applied Mathematics), Philadelphia (1994) · Zbl 0824.90112
[38] Neumaier, A.: MINQ—General Definite and Bound Constrained Indefinite Quadratic Programming (1998) · Zbl 1317.90239
[39] Nie, Pu-yan; Lai, Ming yong; Zhu, Shu jin; Zhang, Pei ai, A line search filter approach for the system of nonlinear equations, Comput. Math. Appl., 55, 2134-2141, (2008) · Zbl 1144.90491
[40] Qi, L, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 51, 101-131, (1991)
[41] Mifflin, R, Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Opt., 15, 959-972, (1977) · Zbl 0376.90081
[42] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Classics in Applied Mathematics. SIAM, Philadelphia (2009) · Zbl 1192.90001
[43] Raghunathan, AU, Global optimization of nonlinear network design, SIAM J. Optim., 23, 268-295, (2013) · Zbl 1270.90036
[44] Raghunathan, A. U., Curtis, F. E., Takaguchi, Y., Hashimoto, H.: Accelerating convergence to competitive equilibrium in electricity markets. In: IEEE Power & Energy Society General Meeting, PESGM2016-000221 (2016)
[45] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898, (1976) · Zbl 0358.90053
[46] Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer, New York (1985) · Zbl 0561.90058
[47] Luca, T; Facchinei, F; Kanzow, C, A theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Comput. Opt. Appl., 16, 173-205, (2000) · Zbl 0964.90046
[48] Ulbrich, M; Ulbrich, S; Vicente, LN, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math. Progr., 100, 379-410, (2004) · Zbl 1070.90110
[49] Wächter, A; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[50] Wang, G; Negrete-Pincetic, M; Kowli, A; Shafieepoorfard, E; Meyn, S; Shanbhag, UV; Chakrabortty, Aranya (ed.); Ili, Marija D (ed.), Dynamic competitive equilibria in electricity markets, 35-62, (2012), New York
[51] Wood, A.J., Wollenberg, B.F.: Power Generation Operation and Control, 2nd edn. Wiley, Hoboken (1996)
[52] Zavala, VM; Laird, CD; Biegler, LT, Interior-point decomposition approaches for parallel solution of large-scale nonlinear parameter estimation problems, Chem. Eng. Sci., 63, 4834-4845, (2008)
[53] Zimmerman, RD; Murillo-Sanchez, CE; Thomas, RJ, MATPOWER: steady-state operations, planning and analysis tools for power systems research and education, IEEE Trans. Power Syst., 26, 12-19, (2011)
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.