article

Derivative-free methods for bound constrained mixed-integer optimization

Authors:

F. RinaldiAuthors Info & Claims

Computational Optimization and Applications, Volume 53, Issue 2

Pages 505 - 526

https://doi.org/10.1007/s10589-011-9405-3

Published: 01 October 2012 Publication History

Abstract

We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixed integer nonlinear optimization problems arises frequently in many industrial and scientific applications and this motivates the increasing interest in the study of derivative-free methods for their solution. The continuous variables are handled by a linesearch strategy whereas to tackle the discrete ones we employ a local search-type approach. We propose different algorithms which are characterized by the way the current iterate is updated and by the stationarity conditions satisfied by the limit points of the sequences they produce.

References

[1]

Abramson, M.A., Audet, C., Chrissis, J.W., Walston, J.G.: Mesh adaptive direct search algorithms for mixed variable optimization. Optim. Lett. 3(1), 35-47 (2009).

[2]

Abramson, M.A., Audet, C., Couture, G., Dennis, J.E. Jr., Le Digabel, S.: The NOMAD project. Software available at http://www.gerad.ca/nomad

[3]

Abramson, M.A., Audet, C., Dennis, J.E. Jr.: Filter pattern search algorithms for mixed variable constrained optimization problems. Pac. J. Optim. 3(3), 477-500 (2007).

[4]

Audet, C., Dennis, J.E. Jr.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188-217 (2006).

Digital Library

[5]

Audet, C., Dennis, J.E. Jr.: A pattern search filter method for nonlinear programming without derivatives. SIAM J. Optim. 14(4), 980-1010 (2004).

Digital Library

[6]

Audet, C., Dennis, J.E. Jr.: Pattern search algorithms for mixed variable programming. SIAM J. Optim. 11(3), 573-594 (2001).

Digital Library

[7]

Dixon, L.C.W., Szegö, G.P.: Towards Global Optimization, vol. 2. North Holland, Amsterdam (1975).

[8]

Elster, C., Neumaier, A.: A grid algorithm for bound-constrained optimization of noisy functions. IMA J. Numer. Anal. 15, 585-608 (1995).

[9]

Floudas, C.A., Pardalos, P.M., Adjiman, C.S., Esposito, W.R., Gumus, Z., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems for Local and Global Optimization. Kluwer Academic, Dordrecht (1999).

[10]

Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, Berlin (1981).

Digital Library

[11]

Le Digabel, S.: Algorithm 909: NOMAD: Nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37(4) (2010).

[12]

Lin, C.-J., Lucidi, S., Palagi, L., Risi, A., Sciandrone, M.: A decomposition algorithm model for singly linearly constrained problems subject to lower and upper bounds. J. Optim. Theory Appl. 141, 107-126 (2009).

[13]

Liuzzi, G., Lucidi, S., Sciandrone, M.: Sequential penalty derivative-free methods for nonlinear constrained optimization. TR 01/2009 Dip. di Sistemi e Informatica, Università degli Studi di Firenze (2009).

[14]

Lucidi, S., Piccialli, V., Sciandrone, M.: An algorithm model for mixed variable programming. SIAM J. Optim. 14, 1057-1084 (2005).

Digital Library

[15]

Lucidi, S., Sciandrone, M.: A derivative-free algorithm for bound constrained optimization. Comput. Optim. Appl. 21(2), 119-142 (2002).

Digital Library

[16]

Lucidi, S., Sciandrone, M., Tseng, P.: Objective-derivative-free methods for constrained optimization. Math. Program. 92(1), 37-59 (2002).

[17]

Lewis, R.M., Torczon, V.: Pattern search algorithms for bound constrained minimization. SIAM J. Optim. 9(4), 1082-1099 (1999).

Digital Library

[18]

Schittkowski, K.: More Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 282. Springer, Berlin (1987).

Digital Library

[19]

Torczon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7(1), 1-25 (1997).

Digital Library

[20]

Törn, A., Zilinskas, A.: Global Optimization. Springer, Berlin (1989).

Cited By

Ploskas NSahinidis N(2022)Review and comparison of algorithms and software for mixed-integer derivative-free optimizationJournal of Global Optimization10.1007/s10898-021-01085-082:3(433-462)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10898-021-01085-0
Giovannelli TLiuzzi GLucidi SRinaldi F(2022)Derivative-free methods for mixed-integer nonsmooth constrained optimizationComputational Optimization and Applications10.1007/s10589-022-00363-182:2(293-327)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10589-022-00363-1
Larson JLeyffer SPalkar PWild S(2021)A method for convex black-box integer global optimizationJournal of Global Optimization10.1007/s10898-020-00978-w80:2(439-477)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10898-020-00978-w
Show More Cited By

Derivative-free methods for bound constrained mixed-integer optimization
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Derivative-free methods for mixed-integer nonsmooth constrained optimization
Abstract
In this paper, mixed-integer nonsmooth constrained optimization problems are considered, where objective/constraint functions are available only as the output of a black-box zeroth-order oracle that does not provide derivative information. A new ...
Derivative-Free Methods for Mixed-Integer Constrained Optimization Problems

Methods which do not use any derivative information are becoming popular among researchers, since they allow to solve many real-world engineering problems. Such problems are frequently characterized by the presence of discrete variables, which can ...
Sequential Penalty Derivative-Free Methods for Nonlinear Constrained Optimization

We consider the problem of minimizing a continuously differentiable function of several variables subject to smooth nonlinear constraints. We assume that the first order derivatives of the objective function and of the constraints can be neither ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Optimization and Applications

Computational Optimization and Applications Volume 53, Issue 2

October 2012

343 pages

ISSN:0926-6003

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ploskas NSahinidis N(2022)Review and comparison of algorithms and software for mixed-integer derivative-free optimizationJournal of Global Optimization10.1007/s10898-021-01085-082:3(433-462)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10898-021-01085-0
Giovannelli TLiuzzi GLucidi SRinaldi F(2022)Derivative-free methods for mixed-integer nonsmooth constrained optimizationComputational Optimization and Applications10.1007/s10589-022-00363-182:2(293-327)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10589-022-00363-1
Larson JLeyffer SPalkar PWild S(2021)A method for convex black-box integer global optimizationJournal of Global Optimization10.1007/s10898-020-00978-w80:2(439-477)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10898-020-00978-w
Porcelli MToint P(2017)BFO, A Trainable Derivative-free Brute Force Optimizer for Nonlinear Bound-constrained Optimization and Equilibrium Computations with Continuous and Discrete VariablesACM Transactions on Mathematical Software10.1145/308559244:1(1-25)Online publication date: 28-Jun-2017
https://dl.acm.org/doi/10.1145/3085592
Ciccazzo ADi Pillo GLatorre V(2016)A SVM Surrogate Model-Based Method for Parametric Yield OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.250130735:7(1224-1228)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1109/TCAD.2015.2501307
Liuzzi GLucidi SRinaldi F(2015)Derivative-Free Methods for Mixed-Integer Constrained Optimization ProblemsJournal of Optimization Theory and Applications10.1007/s10957-014-0617-4164:3(933-965)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s10957-014-0617-4
Ciccazzo ALatorre VLiuzzi GLucidi SRinaldi F(2015)Derivative-Free Robust Optimization for Circuit DesignJournal of Optimization Theory and Applications10.1007/s10957-013-0441-2164:3(842-861)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s10957-013-0441-2
Grippo LRinaldi F(2015)A class of derivative-free nonmonotone optimization algorithms employing coordinate rotations and gradient approximationsComputational Optimization and Applications10.1007/s10589-014-9665-960:1(1-33)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s10589-014-9665-9
Newby EAli M(2015)A trust-region-based derivative free algorithm for mixed integer programmingComputational Optimization and Applications10.1007/s10589-014-9660-160:1(199-229)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s10589-014-9660-1
MüLler JShoemaker CPiché R(2013)SO-MIComputers and Operations Research10.1016/j.cor.2012.08.02240:5(1383-1400)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.cor.2012.08.022

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents