×

Penalty-free method for nonsmooth constrained optimization via radial basis functions. (English) Zbl 1424.65087

Summary: We consider a general class of nonlinear constrained optimization problems, where derivatives of the objective function and constraints are unavailable. This property of problems can often impede the performance of optimization algorithms. Most algorithms usually determine a quasi-Newton direction and then use line search techniques. We propose a smoothing algorithm without the need to use a penalty function. A new algorithm is developed to modify the trust region and to handle the constraints based on radial basis functions (RBFs). The value of the objective function is reduced according to the relation of the predicted reduction of constraint violation achieved by the trial step. At each iteration, the constraints are approximated by a quadratic model obtained by RBFs. The aim of the present work is to keep the good position for the interpolation points in order to obtain a proper approximation in a small trust region. The numerical results are presented for some standard test problems.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arora JS. Introduction to Optimum Design. New York, NY, USA: McGraw-Hill, 1989.
[2] Belegundu AD. A Study of Mathematical Programming Methods for Structural Optimization. PhD, Department of Civil and Environmental Engineering, University of Iowa, Iowa, IA, USA, 1982.
[3] Benzi M, Golub GH, Liesen J. Numerical solution of saddle point problems. Acta Numerica 2005; 14: 1-137. · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[4] Bhatti MA, Polak E, Pister KS. OPTDYNA General Purpose Optimization Program for Problems With or Without Dynamic Constraints. Technical Report UCB/EERC-79/16, University of California, Berkeley, 1979.
[5] Bjorkman M, Holmstrom K. Global optimization of costly nonconvex functions using radial basis functions. Optim Eng 2000; 4: 373-397. · Zbl 1035.90061
[6] Booker AJ, Frank PD, Dennis Jr JE, Moore DW. Managing Surrogate Objectives to Optimize a Helicopter Rotor Design: Further Experiments. Proceedings of 8th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, 1998. · doi:10.2514/6.1998-4717
[7] Buhmann MD. Radial basis functions: theory and implementations. Cambridge Monographs on Applied and Computational Mathematics 2003; 12: 147-165. · Zbl 1038.41001
[8] Byrd RH. Robust trust region methods for constrained optimization. Third Siam Conference on Optimization, Houston, TX, USA, 1987.
[9] Byrd RH, Gilbert JC, Nocedal J. A trust region method based on interior point techniques for nonlinear programming. Math Program 2000; 89: 149-185. · Zbl 1033.90152 · doi:10.1007/PL00011391
[10] Chen ZW. A penalty-free-type nonmonotone trust-region method for nonlinear constrained optimization. Appl Math Comput 2006; 173: 1014-1046. · Zbl 1093.65058
[11] Chen ZW, Han JY, Xu DC. A nonmonotone trust region algorithm for optimization with simplebound constraints. Appl Math Opt 2001; 43: 65-85. · Zbl 0973.65049 · doi:10.1007/s002450010020
[12] Chin CM, Fletcher R. On the global convergence of an SLP-filter algorithm that takes EQP steps. Math Program 2003; 96: 161-177. · Zbl 1023.90060 · doi:10.1007/s10107-003-0378-6
[13] Coello CA, Montes EM. Constraint-handling in genetic algorithms through the use of dominance-based tournament selection. Adv Eng Inform, 2002; 3: 193-203.
[14] Coleman TF, Li A. An interior trust region approach for nonlinear minimization subject to bounds. Siam J Optim 1996; 6: 418-445. · Zbl 0855.65063 · doi:10.1137/0806023
[15] Conn AR, Gould NIM, Toint PhL. Global convergence of a class of trust region algorithms for optimization with simple bounds. Siam J Numer Anal 1998; 25: 433-460. · Zbl 0643.65031 · doi:10.1137/0725029
[16] Conn AR, Guold M, Toint PhL. Trust-Region Method, MPS-SIAM Series on Optimization. Siam, 2000.
[17] Conn AR, Scheinberg K, Toint PhL. On the convergence of derivative-free methods for unconstrained optimization. Approximation theory and optimization: tributes to MJD Powell 1986; 83-108. · Zbl 1042.90617
[18] Conn AR, Scheinberg K, Toint PhL. Recent progress in unconstrained nonlinear optimization without derivatives. Math Program 1997; 79: 345-397. · Zbl 0887.90154
[19] Conn AR, Scheinberg K, Toint PhL, Vicente LN. Geometry of interpolation sets in derivative free optimization. Math Program 2008; 111: 141-172. · Zbl 1163.90022 · doi:10.1007/s10107-006-0073-5
[20] Conn AR, Scheinberg K, Vicente LN. Introduction to Derivative-Free Optimization. Siam, 2009. · Zbl 1163.49001
[21] Conn AR, Toint PhL. An algorithm using quadratic interpolation for unconstrained derivative free optimization. Nonlinear Optimization and Applications 1996; 27-47. · Zbl 0976.90102
[22] Dennis J, EL-Alem MM, Maciel MC. A global convergence theory for general trust region based algorithms for equality constrained optimization. Siam J Optim 1997; 7: 177-207. · Zbl 0867.65031 · doi:10.1137/S1052623492238881
[23] Dennis J, Heinkenschloss M, Vicente LN. Trust-region interior-point SQP algorithms for a class of nonlinear programming problems. Siam J Control Optim 1989; 36: 1750-1794. · Zbl 0921.90137 · doi:10.1137/S036012995279031
[24] Dennis J, Vicente LN. On the convergence theory of trust-region-based algorithms for equality constrained optimization. Siam J Optim 1997; 7: 927-950. · Zbl 0891.65073 · doi:10.1137/S1052623494276026
[25] Fasshauer GE. Meshfree approximation methods with MATLAB. Singapore: World Scientific, 2007. · Zbl 1123.65001 · doi:10.1142/6437
[26] Gould NIM, Toint PhL. Nonlinear programming without a penalty function or a filter. Math Program 2010; 122: 155-196. · Zbl 1216.90069 · doi:10.1007/s10107-008-0244-7
[27] Hock W, Schittkowski K. Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematics Systems, No. 187, Berlin, Germany: Springer-Verlag, 1981. · Zbl 0452.90038 · doi:10.1007/978-3-642-48320-2
[28] Jones DR, Schonlau M, Welch WJ. Efficient global optimization of expensive black-box functions. J Global Optim 1989; 4: 455-492. · Zbl 0917.90270
[29] Kurokawa N. Global convergence of the derivative free trust region Algorithm using inexact information a function values. PhD, Graduate School Of Informatics Kyoto University, 2009.
[30] Liu X, Yuan Y. A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization. Siam J Optim 2011; 21: 545-571. · Zbl 1233.90257 · doi:10.1137/080739884
[31] Martnez JM, Sobral FN. Constrained derivative-free optimization on thin domains. J Global Optim 2013; 3: 12171232.
[32] Micchelli CA. Interpolation of scattered data: distance matrices and conditionally positive definite functions. Constr Approx 1986; 2: 11-22. · Zbl 0625.41005 · doi:10.1007/BF01893414
[33] Nelder JA, Mead R. A simplex method for function minimization. Comput J 1965; 7: 308-313. · Zbl 0229.65053 · doi:10.1093/comjnl/7.4.308
[34] Nocedal J, Wright S. Numerical Optimization. New York, NY, USA: Springer Science & Business Media, 2006. · Zbl 1104.65059
[35] Omojokun FO. Trust region algorithms for optimization with nonlinear equality and inequality constrains. PhD, University of Colorado at Boulder, USA, 1989.
[36] Pillo GD. Exact penalty methods. In Algorithms for Continuous Optimization. Springer Netherlands, 1994. · Zbl 0828.90128
[37] Plantenga TD. A trust region method for nonlinear programming based on primal interior point techniques. Siam J Sci Comput 1999; 20: 282-305. · Zbl 0912.90262 · doi:10.1137/S1064827595284403
[38] Plantenga TD. Hopspack 2.0 user manual. Sandia National Laboratories Technical Report Sandia National Laboratories Technical Report SAND 2009: 2009-6265. Harvard
[39] Powell MJD. UOBYQA: unconstrained optimization by quadratic approximation. Math Program 2002; 92: 555-582. · Zbl 1014.65050 · doi:10.1007/s101070100290
[40] Qeuvray R. Trust-Region Methods Based on Radial Basis Functions with Application to Biomedical Imaging. PhD, Ecole Polytechnique F´ed´erale de Lausanne, 2005.
[41] Regis RG, Shoemaker CA. A stochastic radial basis function method for the global optimization of expensive functions. Informs J Comput 2007; 19: 497-509. · Zbl 1241.90192 · doi:10.1287/ijoc.1060.0182
[42] Ulbrich S. On the superlinear local convergence of a filter-SQP method. Math Program 2004; 100: 217-245. · Zbl 1146.90525
[43] Vanderplaats GN, Moses F. Structural optimization by methods of feasible directions. Comput Struct; 1973, 3: 739-755. · doi:10.1016/0045-7949(73)90055-2
[44] Vicente LN, Vicente IN, Badgwell A, Sorensen DC. Trust-region interior point algorithms for a class of nonlinear programming problems. 1996.
[45] Wendland H. Scattered Data Approximation. Cambridge, UK: Cambridge University Press, 2005. 823 · Zbl 1075.65021
[46] Winfield D. Function minimization by interpolation in a data table. Ima J Appl Math 1973; 12: 339-347. · Zbl 0274.90060 · doi:10.1093/imamat/12.3.339
[47] Yamashita H. A globally convergent quasi-newton method for equality without a penalty function for nonlinear constrained optimization. Technical Report, Mathematical Systems Inc., Tokyo, Japan, 1979.
[48] Yamashita H, Yabe H. A globally convergent trust-region SQP method without function. Technical Report, Mathematical Systems Inc., Tokyo, Japan, 2003.
[49] Zhao Z, Meza JC, Van Hove M. Using pattern search methods for surface structure determination of nanomaterials. J Phys Condens Matter 2006; 18: 8693-8706. · doi:10.1088/0953-8984/18/39/002
[50] Zoppke-Donaldson C. A tolerance-tube approach to sequential quadratic programming with applications. PhD, Department of Mathematics and Computer Science, University of Dundee, Dundee, Scotland, UK, 1995.
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.