×

Adapting derivative free optimization methods to engineering models with discrete variables. (English) Zbl 1293.65092

Summary: In this paper we extend Continuous Derivative Free (CDF) algorithms that solve optimization models with continuous variables to the solution of optimization models with both continuous and discrete variables. The algorithm fits naturally to the solution of discretized models arising from continuous models. Roughly speaking, the finer the discretization, the closer the discretized solution is to its continuous counterpart. The algorithm also finds stationary points of real problems with continuous and discrete variables. Encouraging results are reported on an access point communication problem and on models solved with a Field Programmable Gate Array (FPGA) device, which generally forces a fixed point discretization of the problem.

MSC:

65K10 Numerical optimization and variational techniques

Software:

BOBYQA; MINPACK-2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramson MA, Audet C, Chrissis JW, Walston JG (2009) Mesh adaptive search algorithms for mixed variable optimization. Optim Lett 3:35–47 · Zbl 1154.90551 · doi:10.1007/s11590-008-0089-2
[2] Audet C, Dennis JE Jr (2001) Pattern search algorithms for mixed variable programming. SIAM J Optim 11(3):573–594 · Zbl 1035.90048 · doi:10.1137/S1052623499352024
[3] Audet C, Dennis JE Jr (2006) Mesh adaptive direct search algorithms for constrained optimization. SIAM J Optim 17(2):642–664 · Zbl 1128.90060 · doi:10.1137/040620886
[4] Averbakh I, Berman O, Drezner Z, Wesolowsky GO (2007) The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation. Eur J Oper Res 179:956–967 · Zbl 1163.90587 · doi:10.1016/j.ejor.2005.11.041
[5] Averick BM, Carter RG, Moré JJ (1991) The minpack-2 test problem collection. Technical memorandum 150, Argonne National Laboratory, May 1991
[6] Bosio S, Capote A, Cesana M (2007) Radio planning of wireless local area networks. IEEE/ACM Trans Netw 15(6):1414–1427 · doi:10.1109/TNET.2007.896478
[7] Coope ID, Price CJ (2000) Frame based methods for unconstrained optimization. J Optim Theory Appl 107(2):261–274 · Zbl 0983.90074 · doi:10.1023/A:1026429319405
[8] Custódio AL, Rocha H, Vicente LN (2010) Incorporating minimum Frobenius norm models in direct search. Comput Optim Appl 46:265–278 · Zbl 1190.90280 · doi:10.1007/s10589-009-9283-0
[9] Douglas SC (2007) Fixed-point algorithms for the blind separation of arbitrary complex-valued non-Gaussian signal mixtures. J Appl Signal Process 2007(1), doi: 10.1155/2007/36525
[10] García-Palomares UM, González Castaño FJ, Burguillo Rial JC (2006) A combined global and local search approach to global optimization. J Glob Optim 34:409–426 · Zbl 1149.90426 · doi:10.1007/s10898-005-3249-2
[11] García-Palomares UM, Rodríguez JF (2002) New sequential and parallel derivative-free algorithms for unconstrained minimization. SIAM J Optim 13(1):79–96 · Zbl 1049.90133 · doi:10.1137/S1052623400370606
[12] González Castaño FJ, Montenegro EC, Burguillo Rial JC, García Palomares UM (2008) Outdoor WLAN planning via non-monotone derivative free optimization: Algorithm adaptation and case study. Comput Optim Appl 40(3):405–419 · Zbl 1153.90543 · doi:10.1007/s10589-007-9091-3
[13] Gratton S, Toint PhL, Troltzsch A (2010) An active-set trust-region method for derivative-free nonlinear bound-constrained optimization. Technical report, Cerfacs
[14] Hansen P, Mladenovic N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449–467 · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[15] Hansen P, Mladenović N, Urosević D (2006) Variable neighborhood search and local branching. Comput Oper Res 33:3034–3045 · Zbl 1086.90042 · doi:10.1016/j.cor.2005.02.033
[16] Imran A, Salhi S, Wassan N (2009) A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. Eur J Oper Res 197:509–518 · Zbl 1159.90525 · doi:10.1016/j.ejor.2008.07.022
[17] Kamenetsky M, Unbehaun M (2002) Coverage planning for outdoor wireless LAN systems. In: 2002 International Zurich seminar on broadcast communications, pp 49.1–49.6
[18] Kim JS, Deng L, Mangalagiri P, Irick K, Sobti K, Kandemir M, Narayanan V, Chakrabarti C, Pitsianis N, Sun X (2009) Au automated framework for accelerating numerical algorithms on reconfigurable platforms using algorithmic/architectural optimization. IEEE Trans Comput 58(12):1654–1667 · Zbl 1367.65254 · doi:10.1109/TC.2009.78
[19] Leyffer S (2001) Integrating SQP and branch and bound for mixed integer nonlinear programming. Comput Optim Appl 18(3):295–309 · Zbl 1009.90074 · doi:10.1023/A:1011241421041
[20] Li Y, Kang L-S (2002) A robust algorithm for solving nonlinear programming problems. Int J Comput Math 79:523–536 · Zbl 0999.65053 · doi:10.1080/00207160210947
[21] Lucidi S, Piccialli V, Sciandrone M (2005) An algorithm model for mixed variable programming. SIAM J Control Optim 15(4):1057–1084 · Zbl 1077.65064 · doi:10.1137/S1052623403429573
[22] Lucidi S, Sciandrone M (2002) On the global convergence of derivative-free methods for unconstrained optimization. SIAM J Optim 13(1):97–116 · Zbl 1027.90112 · doi:10.1137/S1052623497330392
[23] Messmer P, Bodenner R (2006) Accelerating scientific applications using FPGAs. Xcell Journal, 70–73
[24] Powell MJD (2009) The BOBYQA algorithm for bound constrained optimization without derivatives. Technical report, Cambridge University
[25] Rodríguez-Henríquez F, Saqib NA, Díaz-Pérez A (2003) 4.2 Gbit/s single-chip FPGA implementation of AES algorithm. Electron Lett 39:1115–1116 · doi:10.1049/el:20030746
[26] Sansaloni T, Pérez-Pascual A, Valls J (2003) Area-efficient FPGA-based FFT processor. Electron Lett 39:19 · doi:10.1049/el:20030892
[27] Siwale I (2007) A note on mixed variable mathematical programs. Technical report, Ike’s Research Ltd, England. http://www.aptech.com/papers/MixedVarMath.pdf
[28] Sutter G, Deschamps JP (2009) High speed fixed point dividers for FPGAs. In: International conference on field programming logic and applications, pp 448–452
[29] Tachibana T, Murata Y, Shibata N, Yasumoto K (2007) Minoru Ito. Proposal of flexible implementation of genetic algorithms on FPGAs. Syst Comput Jpn 38:28–38 · Zbl 05441975 · doi:10.1002/scj.20779
[30] Torn A, Montaz A, Viitanen S (1999) Stochastic global optimization problem classes and solution techniques. J Glob Optim 14:437–447 · Zbl 0952.90030 · doi:10.1023/A:1008395408187
[31] Unbehaun M, Kamenetsky M (2003) On the deployment of picocelular wireless infrastructure. IEEE Wirel Commun 10:70–80 · doi:10.1109/MWC.2003.1265855
[32] Vavouras M, Papadimitriou K, Papaefstathiou I (2009) Implementation of a genetic algorithm on a virtex-ii pro FPGA. In: Proceeding of the ACM/SIGDA international symposium on FPGAs, p 287
[33] Vicente LN (2009) Implicitly and densely discrete black-box optimization problems. Optim Lett 3:475–482 · Zbl 1170.90441 · doi:10.1007/s11590-009-0120-2
[34] Whitacre JM (2007) Adaptation and self-organization in evolutionary algorithms. PhD thesis, School of Chemical Sciences and Engineering, The University of New South Wales
[35] Wu A, So S (2003) VLSI implementation of genetic four-step search for block matching algorithm. IEEE Trans Consum Electron 49:1474–1481 · doi:10.1109/TCE.2003.1261256
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.