Delaunay-based derivative-free optimization via global surrogates. III: nonconvex constraints. (English) Zbl 1447.90035

Summary: This paper introduces a Delaunay-based derivative-free optimization algorithm, dubbed \(\varDelta\)-DOGS \((\varOmega)\), for problems with both (a) a nonconvex, computationally expensive objective function \(f(x)\), and (b) nonlinear, computationally expensive constraint functions \(c_\ell (x)\) which, taken together, define a nonconvex, possibly even disconnected feasible domain \(\varOmega\), which is assumed to lie within a known rectangular search domain \(\varOmega_s\), everywhere within which the \(f(x)\) and \(c_\ell (x)\) may be evaluated. Approximations of both the objective function \(f(x)\) as well as the feasible domain \(\varOmega\) are developed and refined as the iterations proceed. The approach is practically limited to the problems with less than about ten adjustable parameters. The work is an extension of our original Delaunay-based optimization algorithm (see [the second author et al.,ibid. 66, No. 3, 331–382 (2016; Zbl 1383.90045)]), and inherits many of the constructions and strengths of that algorithm, including: (1) a surrogate function \(p(x)\) interpolating all existing function evaluations and summarizing their trends, (2) a synthetic, piecewise-quadratic uncertainty function \(e(x)\) built on the framework of a Delaunay triangulation amongst existing datapoints, (3) a tunable balance between a global exploration (large \(K\)) and a local refinement (small \(K\)), (4) provable global convergence for a sufficiently large \(K\), under the assumption that the objective and constraint functions are twice differentiable with bounded Hessians, (5) an adaptive-\(K\) variant of the algorithm that efficiently tunes \(K\) automatically based on a target value of the objective function, and (6) remarkably fast global convergence on a variety of benchmark problems.


90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives


Zbl 1383.90045
Full Text: DOI


[1] Abramson, M.A., Audet, C., Dennis, J.E., Le Digabel, S.: OrthoMADS: a deterministic MADS instance with orthogonal directions (2009) · Zbl 1189.90202
[2] Achterberg, T., Scip: solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41 (2009) · Zbl 1171.90476
[3] Alimo, S., Beyhaghi, P., Meneghello, G., Bewley, T.: Delaunay-based optimization in cfd leveraging multivariate adaptive polyharmonic splines (maps). The American Institute of Aeronautics and Astronautics, SciTech Meeting (2017) (2017)
[4] Alimohammadi, S., He, D.: Multi-stage algorithm for uncertainty analysis of solar power forecasting. In: Power and Energy Society General Meeting (PESGM), 2016, pp. 1-5. IEEE (2016)
[5] Audet, C.; Dennis, JE, A pattern search filter method for nonlinear programming without derivatives, SIAM J. Optim., 14, 4, 980-1010 (2004) · Zbl 1073.90066
[6] Audet, C.; Dennis, JE, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 1, 188-217 (2006) · Zbl 1112.90078
[7] Audet, C.; Dennis, JE, A progressive barrier for derivative-free nonlinear programming, SIAM J. Optim., 20, 1, 445-472 (2009) · Zbl 1187.90266
[8] Belitz, P., Bewley, T.: New horizons in sphere-packing theory, part ii: lattice-based derivative-free optimization via global surrogates. J. Glob. Optim. pp. 1-31 (2013) · Zbl 1273.90241
[9] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tighteningtechniques for non-convex minlp, Optim. Methods Softw., 24, 4-5, 597-634 (2009) · Zbl 1179.90237
[10] Bertsekas, DP, On penalty and multiplier methods for constrained minimization, SIAM J. Control Optim., 14, 2, 216-235 (1976) · Zbl 0324.49029
[11] Beyhaghi, P.; Bewley, TR, Delaunay-based derivative-free optimization via global surrogates, part ii: convex constraints, J. Global Optim., 66, 3, 383-415 (2016) · Zbl 1384.90122
[12] Beyhaghi, P., Cavaglieri, D., Bewley, T.: Delaunay-based derivative-free optimization via global surrogates, part i: linear constraints. J. Glob. Optim. pp. 1-52 (2015) · Zbl 1383.90045
[13] Boissonnat, J.-D., Devillers, O., Hornus, S.: Incremental construction of the delaunay triangulation and the delaunay graph in medium dimension. In: Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pp. 208-216. ACM (2009) · Zbl 1380.68382
[14] Booker, AJ; Dennis, JE Jr; Frank, PD; Serafini, DB; Torczon, V.; Trosset, MW, A rigorous framework for optimization of expensive functions by surrogates, Struct. Optim., 17, 1, 1-13 (1999)
[15] Boyd, S.; Vandenberghe, L., Convex Optimization (2010), Cambridge: Cambridge University Press, Cambridge
[16] Jones, DR, A taxonomy of global optimization methods based on response surfaces, J. Global Optim., 21, 4, 39 (2001)
[17] 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
[18] Forsgren, A.; Gill, PE, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 4, 1132-1152 (1998) · Zbl 0915.90236
[19] Forsgren, A.; Gill, PE; Wright, MH, Interior Methods for Nonlinear Optimization (2002), Philadelphia: SIAM, Philadelphia
[20] 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
[21] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: A Schur-complement method for sparse quadratic programming. Technical report, DTIC Document (1987) · Zbl 0725.65060
[22] Gill, P.E., Saunders, M.A., Wong, E.: On the performance of SQP methods for nonlinear optimization. In: Modeling and Optimization: Theory and Applications, pp. 95-123. Springer, Berlin (2015) · Zbl 1372.65170
[23] Gramacy, RB; Gray, GA; Le Digabel, S.; Lee, HKH; Ranjan, P.; Wells, G.; Wild, SM, Modeling an augmented lagrangian for blackbox constrained optimization, Technometrics, 58, 1, 1-11 (2016)
[24] Hoffman, KL, A method for globally minimizing concave functions over convex sets, Math. Program., 20, 1, 22-32 (1981) · Zbl 0441.90096
[25] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181 (1993) · Zbl 0796.49032
[26] Jones, DR; Schonlau, M.; Welch, WJ, Efficient global optimization of expensive black-box functions, J. Global Optim., 13, 4, 455-492 (1998) · Zbl 0917.90270
[27] Kort, B.W., Bertsekas, D.P.: A new penalty function method for constrained minimization. In: Proceedings of the 1972 IEEE Conference on Decision and Control, 1972 and 11th Symposium on Adaptive Processes, pp. 162-166. IEEE, New York (1972)
[28] Kort, BW; Bertsekas, DP, Combined primal-dual and penalty methods for convex programming, SIAM J. Control Optim., 14, 2, 268-294 (1976) · Zbl 0332.90035
[29] Krige, DG, A statistical approach to some basic mine valuation problems on the Witwatersrand, J. South. Afr. Inst. Min. Metall., 52, 119-139 (1952)
[30] Lawrence, C.T., Zhou, J.L., Tits, A.L.: User’s guide for CFSQP version 2.0: AC code for solving (large scale) constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality constraints (1994)
[31] Le Digabel, S., Algorithm 909: nomad: nonlinear optimization with the mads algorithm, ACM Trans. Math. Softw. (TOMS), 37, 4, 44 (2011) · Zbl 1365.65172
[32] Lewis, RM; Torczon, V., Pattern search algorithms for bound constrained minimization, SIAM J. Optim., 9, 4, 1082-1099 (1999) · Zbl 1031.90047
[33] Lewis, RM; Torczon, V., Pattern search methods for linearly constrained minimization, SIAM J. Optim., 10, 3, 917-941 (2000) · Zbl 1031.90048
[34] Lewis, RM; Torczon, V., A globally convergent augmented lagrangian pattern search algorithm for optimization with general constraints and simple bounds, SIAM J. Optim., 12, 4, 1075-1089 (2002) · Zbl 1011.65030
[35] Long, CC; Marsden, AL; Bazilevs, Y., Shape optimization of pulsatile ventricular assist devices using FSI to minimize thrombotic risk, Comput. Mech., 54, 4, 921-932 (2014) · Zbl 1314.74056
[36] Madani, R.; Ashraphijuo, M.; Lavaei, J., Promises of conic relaxation for contingency-constrained optimal power flow problem, IEEE Trans. Power Syst., 31, 2, 1297-1307 (2016)
[37] Marsden, AL; Feinstein, JA; Taylor, CA, A computational framework for derivative-free optimization of cardiovascular geometries, Comput. Methods Appl. Mech. Eng., 197, 21, 1890-1905 (2008) · Zbl 1194.76296
[38] Marsden, AL; Wang, M.; Dennis, JE Jr; Moin, P., Optimal aeroacoustic shape design using the surrogate management framework, Optim. Eng., 5, 2, 235-262 (2004) · Zbl 1116.90417
[39] McKay, MD; Beckman, RJ; Conover, WJ, A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 42, 1, 55-61 (2000)
[40] Meer, J.T.M.T., Duijne, H.V., Nieuwenhuis, R., Rijnaarts, H.H.M.: Prevention and reduction of pollution of groundwater at contaminated megasites: integrated management strategy, and its application on megasite cases. In: Quevauviller, P. (ed.) Groundwater Science and Policy: An International Overview, pp. 405-420 (2008)
[41] Misener, R.; Floudas, CA, Antigone: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 2-3, 503-526 (2014) · Zbl 1301.90063
[42] Moghadam, ME; Migliavacca, F.; Vignon-Clementel, IE; Hsia, T-Y; Marsden, AL, Optimization of shunt placement for the norwood surgery using multi-domain modeling, J. Biomech. Eng., 134, 5, 051002 (2012)
[43] Molga, Marcin., Smutnicki, Czesław.: Test functions for optimization needs. Test functions for optimization needs, 101, (2005)
[44] Parr, JM; Keane, AJ; Forrester, AIJ; Holden, CME, Infill sampling criteria for surrogate-based optimization with constraint handling, Eng. Optim., 44, 10, 1147-1166 (2012)
[45] Pee, EY; Royset, JO, On solving large-scale finite minimax problems using exponential smoothing, J. Optim. Theory Appl., 148, 2, 390-421 (2011) · Zbl 1216.90097
[46] Picheny, V., Gramacy, R.B., Wild, S., Le Digabel, S.: Bayesian optimization under mixed constraints with a slack-variable augmented lagrangian. In: Advances in Neural Information Processing Systems, pp. 1435-1443 (2016)
[47] Polak, E.; Royset, JO; Womersley, RS, Algorithms with adaptive smoothing for finite minimax problems, J. Optim. Theory Appl., 119, 3, 459-484 (2003) · Zbl 1061.90117
[48] Pussoli, BF; Da Silva, LW; Barbosa, JR; Kaviany, M., Optimization of peripheral finned-tube evaporators using entropy generation minimization, Int. J. Heat Mass Transf., 55, 25-26, 7838-7846 (2012)
[49] Ramachandra, AB; Sankaran, S.; Humphrey, JD; Marsden, AL, Computational simulation of the adaptive capacity of vein grafts in response to increased pressure, J. Biomech. Eng., 137, 3, 031009 (2015)
[50] Rasmussen, CE, Gaussian processes for machine learning, Int. J. Neural Syst., 14, 2, 69-106 (2006)
[51] Sacks, J.; Welch, WJ; Mitchell, TJ; Wynn, HP, Design and analysis of computer experiments, Stat. Sci., 4, 4, 409-423 (1989)
[52] Schonlau, M., Welch, W.J., Jones, D.R.: A data-analytic approach to Bayesian global optimization. In: Department of Statistics and Actuarial Science and The Institute for Improvement in Quality and Productivity, 1997 ASA Conference (1997)
[53] Simionescu, PA, Computer-Aided Graphing and Simulation Tools for AutoCAD Users (2014), Boca Raton: CRC Press, Boca Raton
[54] Snoek, J., Larochelle, H., Adams, R.P.: Practical Bayesian optimization of machine learning algorithms. In: Advances in Neural Information Processing Systems, pp. 2951-2959 (2012)
[55] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047
[56] Torczon, V., On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1, 1-25 (1997) · Zbl 0884.65053
[57] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542
[58] Wahba, G., Spline Models for Observational Data (1990), Philadelphia: SIAM, Philadelphia · Zbl 0813.62001
[59] Watson, DF, Computing the n-dimensional delaunay tessellation with application to voronoi polytopes, Comput. J., 24, 2, 167-172 (1981)
[60] Wild, SM; Regis, RG; Shoemaker, CA, Orbit: optimization by radial basis function interpolation in trust-regions, SIAM J. Sci. Comput., 30, 6, 3197-3219 (2008) · Zbl 1178.65065
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.