×

zbMATH — the first resource for mathematics

An augmented Lagrangian filter method. (English) Zbl 1454.90088
Summary: We introduce a filter mechanism to enforce convergence for augmented Lagrangian methods for nonlinear programming. In contrast to traditional augmented Lagrangian methods, our approach does not require the use of forcing sequences that drive the first-order error to zero. Instead, we employ a filter to drive the optimality measures to zero. Our algorithm is flexible in the sense that it allows for equality-constrained quadratic programming steps to accelerate local convergence. We also include a feasibility restoration phase that allows fast detection of infeasible problems. We provide a convergence proof that shows that our algorithm converges to first-order stationary points. We provide preliminary numerical results that demonstrate the effectiveness of our proposed method.
MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abhishek, K.; Leyffer, S.; Linderoth, JT, FilMINT: an outer-approximation-based solver for nonlinear mixed integer programs, INFORMS J Comput, 22, 555-567 (2010) · Zbl 1243.90142
[2] Altay-Salih, A.; Pinar, MC; Leyffer, S., Constrained nonlinear programming for volatility estimation with GARCH models, SIAM Rev, 45, 3, 485-503 (2003) · Zbl 1064.90043
[3] Arrieta-Camacho, JJ; Biegler, LT; Subramanian, D.; Allgower, RF; Biegler, LT, NMPC-based real-time coordination of multiple aircraft, Assessment and future directions of nonlinear model predictive control, 629-639 (2007), Heidelberg: Springer, Heidelberg · Zbl 1220.49024
[4] Bautista, G.; Anjos, MF; Vannelli, A., Formulation of oligopolistic competition in AC power networks: an NLP approach, IEEE Trans Power Syst, 22, 1, 105-115 (2007)
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer, 22, 5, 1-131 (2013) · Zbl 1291.65172
[6] Benson, H.; Shanno, D., An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput Optim Appl, 38, 371-399 (2007) · Zbl 1171.90546
[7] Benson, HY; Shanno, DF, Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts, Comput Optim Appl, 40, 2, 143-189 (2008) · Zbl 1181.90243
[8] Benson, HY; Shanno, DF; Vanderbei, RJ, Interior-point methods for nonconvex nonlinear programming: filter-methods and merit functions, Comput Optim Appl, 23, 2, 257-272 (2002) · Zbl 1022.90017
[9] Bertsekas, DP, Constrained optimization and lagrange multiplier methods (1982), New York: Athena Scientific, New York · Zbl 0572.90067
[10] Betts, JT, Practical methods for optimal control using nonlinear programming. Advances in design and control (2001), Philadelphia: SIAM, Philadelphia · Zbl 0995.49017
[11] Biegler, LT; Grossmann, IE; Floudas, CA; Agrawal, R., Challenges and research issues for product and process design optimization, Proceedings of foundations of computer aided process design (2004), Austin: CACHE Corporation, Austin
[12] Biegler, LT; Grossmann, IE, Part I: retrospective on optimization, Comput Chem Eng, 28, 8, 1169-1192 (2004)
[13] Birgin, EG; Martinez, JM, Improving ultimate convergence of an augmented Lagrangian method, Optim Methods Softw, 23, 2, 177-195 (2008) · Zbl 1211.90222
[14] Birgin, EG; Martínez, JM, Augmented lagrangian method with nonmonotone penalty parameters for constrained optimization, Comput Optim Appl, 51, 3, 941-965 (2012) · Zbl 1244.90216
[15] Birgin, EG; Martínez, JM, Practical augmented Lagrangian methods for constrained optimization (2014), Philadelphia: SIAM, Philadelphia · Zbl 1339.90312
[16] Bonami P, Biegler LT, Conn AR, Cornuejols G, Grossmann IE, Laird CD, Lee J, Lodi A, Margot F, Sawaya N, Wähter A (2005) An algorithmic framework for convex mixed integer nonlinear programs. Research report RC 23771, IBM T. J. Watson Research Center, Yorktown, NY · Zbl 1151.90028
[17] Bonami P, Lee J, Leyffer S, Waechter A (2011) More branch-and-bound experiments in convex nonlinear integer programming. Technical report ANL/MCS-P1949-0911, Argonne National Laboratory, Mathematics and Computer Science Division, Lemont, IL
[18] Bonnans JF, André J (2009) Optimal structure of gas transmission trunklines. Technical report 6791, INRIA Saclay, 91893 ORSAY Cedex, France · Zbl 1272.90005
[19] Bonnard, B.; Faubourg, L.; Launay, G.; Trélat, E., Optimal control with state constraints and the space shuttle re-entry problem, J Dyn Control Syst, 9, 2, 155-199 (2003) · Zbl 1034.49014
[20] Borghetti, A.; Frangioni, A.; Lacalandra, F.; Nucci, CA, Lagrangian heuristics based on disaggregated bundle methods for hydrothermal unit commitment, IEEE Trans Power Syst, 18, 1-10 (2003)
[21] Byrd, RH; Hribar, ME; Nocedal, J., An interior point algorithm for large scale nonlinear programming, SIAM J Optim, 9, 4, 877-900 (1999) · Zbl 0957.65057
[22] Byrd, RH; Gould, NIM; Nocedal, J.; Waltz, RA, An algorithm for nonlinear optimization using linear programming and equality constrained subproblems, Math Progr Ser B, 100, 1, 27-48 (2004) · Zbl 1146.90513
[23] Byrd, RH; Nocedal, J.; Waltz, RA; di Pillo, G.; Roma, M., KNITRO: an integrated package for nonlinear optimization, Large-scale nonlinear optimization, 35-59 (2006), New York: Springer, New York · Zbl 1108.90004
[24] Calamai, PH; Moré, JJ, Projected gradient methods for linearly constrained problems, Math Progr, 39, 93-116 (1987) · Zbl 0634.90064
[25] Castro, J.; Gonzalez, JA, A nonlinear optimization package for long-term hydrothermal coordination, Eur J Oper Res, 154, 1, 641-658 (2004) · Zbl 1053.90091
[26] Chin, CM; Fletcher, R., On the global convergence of an SLP-filter algorithm that takes EQP steps, Math Progr, 96, 1, 161-177 (2003) · Zbl 1023.90060
[27] Coleman, TF; Li, Y.; Verman, A., Reconstructing the unknown volatility function, J Comput Finance, 2, 3, 77-102 (1999)
[28] Conn, AR; Gould, NIM; Toint, PL, LANCELOT: a Fortran package for large-scale nonlinear optimization (release A) (1992), Heidelberg: Springer, Heidelberg · Zbl 0761.90087
[29] Conn, AR; Gould, NIM; Toint, PL, Trust-region methods. MPS-SIAM series on optimization (2000), Philadelphia: SIAM, Philadelphia
[30] Cornuejols, G.; Tütüncü, R., Optimization methods in finance (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1117.91031
[31] Curtis, FE; Jiang, H.; Robinson, DP, An adaptive augmented Lagrangian method for large-scale constrained optimization, Math Progr, 152, 1-2, 201-245 (2015) · Zbl 1323.49015
[32] Dolan, ED; Moré, J., Benchmarking optimization software with performance profiles, Math Progr, 91, 2, 201-213 (2002) · Zbl 1049.90004
[33] Donde V, Lopez V, Lesieutre B, Pinar A, Yang C, Meza J (2005) Identification of severe multiple contingencies in electric power networks. In: Proceedings 37th North American power symposium, LBNL-57994
[34] Klaus, E.; Steinbach Marc, C.; Bock, HG; Kostina, E.; Phu, HX; Ranacher, R., Nonlinear optimization in gas networks, Modeling, simulation and optimization of complex processes, 139-148 (2005), Berlin: Springer, Berlin · Zbl 1069.90014
[35] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math Progr, 66, 327-349 (1994) · Zbl 0833.90088
[36] Fletcher R, Leyffer S (1998) User manual for filterSQP. Numerical analysis report NA/181, University of Dundee
[37] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math Progr, 91, 239-270 (2002) · Zbl 1049.90088
[38] Fletcher, R.; Leyffer, S.; di Pillo, G.; Murli, A., Filter-type algorithms for solving systems of algebraic equations and inequalities, High performance algorithms and software for nonlinear optimization, 259-278 (2003), Dordrecht: Kluwer, Dordrecht
[39] Fletcher, R.; Sainz de la Maza, E., Nonlinear programming and nonsmooth optimization by successive linear programming, Math Progr, 43, 235-256 (1989) · Zbl 0724.90062
[40] Fletcher, R.; Leyffer, S.; Toint, PL, On the global convergence of a filter-SQP algorithm, SIAM J Optim, 13, 1, 44-59 (2002) · Zbl 1029.65063
[41] Forsgren, A.; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev, 4, 4, 525-597 (2002) · Zbl 1028.90060
[42] Friedlander MP (2002) A globally convergent linearly constrained Lagrangian method for nonlinear optimization. Ph.D. thesis, Stanford University
[43] Friedlander, MP; Leyffer, S., Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs, SIAM J Sci Comput, 30, 4, 1706-1729 (2008) · Zbl 1179.65065
[44] Ghaoui, LE; Oks, M.; Oustry, F., Worst-case value-at-risk and robust portfolio optimization: a conic programming approach, Oper Res, 51, 4, 509-679 (2003) · Zbl 1165.91397
[45] Gill PE, Murray W, Saunders MA (1997) User’s guide for SQOPT 5.3: a Fortran package for large-scale linear and quadratic programming. Technical report NA 97-4, Department of Mathematics, University of California, San Diego
[46] Gill, PE; Murray, W.; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM J Optim, 12, 4, 979-1006 (2002) · Zbl 1027.90111
[47] Gill, PE; Murray, W.; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev, 47, 1, 99-131 (2005) · Zbl 1210.90176
[48] Gondzio, J.; Grothey, A., Reoptimization with the primal-dual interior point method, SIAM J Optim, 13, 3, 842-864 (2002) · Zbl 1101.90401
[49] Gould, NIM; Orban, D.; Toint, PL, Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput Optim Appl, 60, 3, 545-557 (2015) · Zbl 1325.90004
[50] Goux, J-P; Leyffer, S., Solving large MINLPs on computational grids, Optim Eng, 3, 327-346 (2002) · Zbl 1035.90049
[51] Huangfu Q, Hall JAJ (2013) Novel update techniques for the revised simplex method. Technical report ERGO-13-001, The School of Mathematics, University of Edinburgh, Edinburgh, UK
[52] Kawayir, Y.; Laird, C.; Wächter, A., Introduction to Ipopt: a tutorial for downloading, installing, and using Ipopt. Manual (2009), Yorktown Heights: IBM T.J. Watson Research Center, Yorktown Heights
[53] Konno, H.; Yamazaki, H., Mean-absolute deviation portfolio optimization model and its application to Tokyo stock market, Manag Sci, 37, 519-531 (1991)
[54] Leyffer, S., Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Comput Optim Appl, 18, 295-309 (2001) · Zbl 1009.90074
[55] Leyffer S, Munson TS (2007) A globally convergent filter method for MPECs. Preprint ANL/MCS-P1457-0907, Argonne National Laboratory, Mathematics and Computer Science Division
[56] Leyffer, S.; Lopez-Calva, G.; Nocedal, J., Interior methods for mathematical programs with complementarity constraints, SIAM J Optim, 17, 1, 52-77 (2006) · Zbl 1112.90095
[57] Lubin, M.; Hall, JAJ; Petra, CG; Anitescu, M., Parallel distributed-memory simplex for large-scale stochastic LP problems, Comput Optim Appl, 55, 3, 571-596 (2013) · Zbl 1276.90044
[58] Martin, A.; Möller, M.; Moritz, S., Mixed integer models for the stationary case of gas network optimization, Math Progr, 105, 563-582 (2006) · Zbl 1085.90035
[59] Momoh, JA; Koessler, RJ; Bond, MS; Stott, B.; Sun, D.; Papalexopoulos, A.; Ristanovic, P., Challenges to optimal power flow, IEEE Trans Power Syst, 12, 444-455 (1997)
[60] Moré, JJ; Toraldo, G., On the solution of quadratic programming problems with bound constraints, SIAM J Optim, 1, 1, 93-113 (1991) · Zbl 0752.90053
[61] Murtagh BA, Saunders MA (1993) MINOS 5.4 user’s guide. Report SOL 83-20R, Department of Operations Research, Stanford University
[62] Murtagh, BA; Saunders, MA; Buckley, AG; Goffin, J-L, A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints, Algorithms for constrained minimization of smooth nonlinear functions, vol 16. Mathematical programming studies, 84-117 (1982), Berlin: Springer, Berlin
[63] Penfield, P.; Spence, R.; Duinker, S., Tellegen’s theorem and electrical networks (1970), Cambridge: MIT Press, Cambridge
[64] Powell, MJD, Algorithms for nonlinear constraints that use Lagrangian functions, Math Progr, 14, 1, 224-248 (1978) · Zbl 0383.90092
[65] Rabinowitz, G.; Mehrez, A.; Oron, G., A nonlinear optimization model of water allocation for hydroelectric energy production and irrigation, Manag Sci, 34, 8, 973-990 (1988) · Zbl 0646.90053
[66] Raghunathan, A.; Biegler, LT, An interior point method for mathematical programs with complementarity constraints (MPCCs), SIAM J Optim, 15, 3, 720-750 (2005) · Zbl 1077.90079
[67] Sheble, GB; Fahd, GN, Unit commitment literature synopsis, IEEE Trans Power Syst, 9, 128-135 (1994)
[68] Shen, C.; Leyffer, S.; Fletcher, R., A nonmonotone filter method for nonlinear optimization, Comput Optim Appl, 52, 3, 583-607 (2012) · Zbl 1259.90140
[69] Smith E, Hall JAJ (2012) A high performance primal revised simplex solver for row-linked block angular linear programming problems. Technical report ERGO-12-003, The School of Mathematics, University of Edinburgh, Edinburgh, UK
[70] Vanderbei, RJ; Shanno, DF, An interior point algorithm for nonconvex nonlinear programming, COAP, 13, 231-252 (1999) · Zbl 1040.90564
[71] Wächter, A.; Biegler, LT, Line search filter methods for nonlinear programming: local convergence, SIAM J Optim, 16, 1, 32-48 (2005) · Zbl 1115.90056
[72] Wächter, A.; Biegler, LT, Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J Optim, 16, 1, 1-31 (2005) · Zbl 1114.90128
[73] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math Progr, 106, 1, 25-57 (2006) · Zbl 1134.90542
[74] Womersley, RS; Lau, K.; May, RL; Easton, AK, Portfolio optimisation problems, Computational techniques and applications: CTAC95, 795-802 (1996), Singapore: World Scientific Publishing Co., Singapore · Zbl 0910.90012
[75] Zhu, C.; Byrd, RH; Lu, P.; Nocedal, J., Algorithm 778: L-BFGS-B—Fortran subroutines for large-scale bound-constrained optimization, ACM Trans Math Softw (TOMS), 23, 4, 550-560 (1997) · Zbl 0912.65057
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.