×

zbMATH — the first resource for mathematics

An interior-point method for nonlinear optimization problems with locatable and separable nonsmoothness. (English) Zbl 1329.90144
Summary: Many real-world optimization models comprise nonconvex and nonsmooth functions leading to very hard classes of optimization models. In this article, a new interior-point method for the special, but practically relevant class of optimization problems with locatable and separable nonsmooth aspects is presented. After motivating and formalizing the problems under consideration, modifications and extensions to a standard interior-point method for nonlinear programming are investigated to solve the introduced problem class. First theoretical results are given and a numerical study is presented that shows the applicability of the new method for real-world instances from gas network optimization.

MSC:
90C30 Nonlinear programming
90C51 Interior-point methods
90C90 Applications of mathematical programming
90C35 Programming involving graphs or networks
90C56 Derivative-free methods and methods using generalized derivatives
90B10 Deterministic network models in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Byrd, RH; Gilbert, JC; Nocedal, J, A trust region method based on interior point techniques for nonlinear programming, Math Program Ser B, 89, 149-185, (2000) · Zbl 1033.90152
[2] Clarke FH (1990) Optimization and nonsmooth analysis. Soc Ind Appl Math. doi:10.1137/1.9781611971309 · Zbl 1134.90542
[3] Clarke FH, Ledyaev YS, Stern RJ, Wolenski PR (1998) Nonsmooth analysis and control theory. Graduate texts in mathematics. Springer, Berlin
[4] Conn AR, Gould NIM, Toint P (2000) Trust-region methods. MPS-SIAM series on optimization. SIAM · Zbl 1364.90066
[5] CPLEX (2013) User’s manual for CPLEX. IBM Corporation, Armonk, USA, 12.6 edn · Zbl 1176.49036
[6] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Program, 91, 201-213, (2002) · Zbl 1049.90004
[7] Fügenschuh A, Geißler B, Gollmer R, Hayn C, Henrion R, Hiller B, Humpola J, Koch T, Lehmann T, Martin A, Mirkov R, Morsi A, Rövekamp J, Schewe L, Schmidt M, Schultz R, Schwarz R, Schweiger J, Stangl C, Steinbach MC, Willert BM (2013) Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets. Energy Syst 1-25. doi:10.1007/s12667-013-0099-8 · Zbl 1211.90182
[8] Fletcher, R; Leyffer, S, Nonlinear programming without a penalty function, Math Program, 91, 239-269, (2000) · Zbl 1049.90088
[9] Forsgren, A; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev, 44, 525-597, (2002) · Zbl 1028.90060
[10] Fuduli, A; Gaudioso, M; Giallombardo, G, A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optim Methods Softw, 19, 89-102, (2004) · Zbl 1211.90182
[11] Geißler B, Martin A, Morsi A, Schewe L (2012) Using piecewise linear functions for solving MINLPs. In: Lee J, Leyffer S (eds) Mixed integer nonlinear programming. The IMA volumes in mathematics and its applications, vol. 154. Springer, New York. pp 287-314. doi:10.1007/978-1-4614-1927-3_10 · Zbl 1242.90132
[12] Geißler B, Morsi A, Schewe L (2013) A new algorithm for MINLP applied to gas transport energy cost minimization. In: Jünger M, Reinelt G (eds) Facets of combinatorial optimization. Springer, Berlin, Heidelberg. pp 321-353. doi:10.1007/978-3-642-38189-8_14 · Zbl 1317.90209
[13] Golub GH, van Loan CF (1989) Matrix computations, 2nd edn. Johns Hopkins University Press, Baltimore
[14] Grothey A (2002) A second order trust region bundle method for nonconvex nonsmooth optimization. Tech. Rep. Report MS02-001, University of Edinburgh · Zbl 1075.90078
[15] Gu Z, Rothberg E, Bixby R (2003) Gurobi optimizer reference manual, version 5.6. Gurobi Optimization Inc., Houston
[16] Hiller B, Humpola J, Lehmann T, Lenz R, Morsi A, Pfetsch ME, Schewe L, Schmidt M, Schwarz R, Schweiger J, Stangl C, Willert BM Computational results for validation of nominations. In: Koch et al. [23], chap 12, pp 233-270. doi:10.1137/1.9781611973693 · Zbl 1343.90011
[17] Hiriart-Urruty JB, Lemaréchal C (1993a) Convex analysis and minimization algorithms I: Fundamentals. Grundlehren der mathematischen Wissenschaften, vol. 305. Springer, Berlin · Zbl 1049.90088
[18] Hiriart-Urruty JB, Lemaréchal C (1993b) Convex analysis and minimization algorithms II: advanced theory and bundle methods. Grundlehren der mathematischen Wissenschaften, vol. 306. Springer, Berlin · Zbl 1049.90004
[19] Karmarkar, N, A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[20] Karmitsa N NonSmooth Optimization (NSO) software. http://napsu.karmitsa.fi/nsosoftware/
[21] Khachiyan, LG, A polynomial algorithm in linear programming, Sov Math Doklady, 20, 191-194, (1979) · Zbl 0409.90079
[22] Kiwiel KC (1985) Methods of descent for nondifferentiable optimization. Lecture Notes in Math, vol 1133. Springer-Verlag, Berlin, New York · Zbl 0561.90059
[23] Koch T, Hiller B, Pfetsch ME, Schewe L (eds) (2015) Evaluating gas network capacities. SIAM-MOS series on optimization. SIAM. doi:10.1137/1.9781611973693 · Zbl 0963.65063
[24] Mehrotra, S, On the implementation of a primal-dual interior point method, SIAM J Optim, 2, 575-601, (1992) · Zbl 0773.90047
[25] Nocedal, J; Wächter, A; Waltz, RA, Adaptive barrier update strategies for nonlinear interior methods, SIAM J Optim, 19, 1674-1693, (2009) · Zbl 1176.49036
[26] Pfetsch, ME; Fügenschuh, A; Geißler, B; Geißler, N; Gollmer, R; Hiller, B; Humpola, J; Koch, T; Lehmann, T; Martin, A; Morsi, A; Rövekamp, J; Schewe, L; Schmidt, M; Schultz, R; Schwarz, R; Schweiger, J; Stangl, C; Steinbach, MC; Vigerske, S; Willert, BM, Validation of nominations in gas network optimization: models, methods, and solutions, Optim Methods Softw, 30, 15-53, (2015) · Zbl 1325.90019
[27] Ruszczyński A (2006) Nonlinear optimization. Princeton University Press, Princeton · Zbl 1108.90001
[28] Schmidt M (2013) A generic interior-point framework for nonsmooth and complementarity constrained nonlinear optimization. Ph.D. thesis, Gottfried Wilhelm Leibniz Universität Hannover · Zbl 0773.90047
[29] Schmidt M, Steinbach MC, Willert BM (2013) A primal heuristic for nonsmooth mixed integer nonlinear optimization. In: Jünger M, Reinelt G (eds) Facets of combinatorial optimization. Springer, Berlin, Heidelberg, pp 295-320. doi:10.1007/978-3-642-38189-8_13 · Zbl 1049.90088
[30] Schmidt, M; Steinbach, MC; Willert, BM, High detail stationary optimization models for gas networks, Optim Eng, 16, 131-164, (2015) · Zbl 1364.90066
[31] Tits, AL; Wächter, A; Bakhtiari, S; Urban, TJ; Lawrence, CT, A primal-dual interior-point method for nonlinear programmng with strong global and local convergence properties, SIAM J Optim, 14, 173-199, (2003) · Zbl 1075.90078
[32] Ulbrich, M; Ulbrich, S; Vicente, LN, A globally convergent primal-dual interior-point filter method for nonlinear programming, Math Program, 100, 379-410, (2004) · Zbl 1070.90110
[33] Vanderbei RJ (2006) LOQO user’s manual-version 4.05. Princeton University, School of Engineering and Applied Science, Department of Operations Research and Financial Engineering, Princeton, New Jersey
[34] Vanderbei, RJ; Shanno, DF, An interior-point algorithm for nonconvex nonlinear programming, Comput Optim Appl, 13, 231-252, (1997) · Zbl 1040.90564
[35] Wächter, A; Biegler, LT, Failure of global convergence for a class of interior point methods for nonlinear programming, Math Program, 88, 565-574, (2000) · Zbl 0963.65063
[36] Wächter, A; Biegler, LT, Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J Optim, 16, 1-31, (2005) · Zbl 1114.90128
[37] 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
[38] Waltz, RA; Morales, JL; Nocedal, J; Orban, D, An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math Program, 107, 391-408, (2006) · Zbl 1134.90053
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.