\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A modified Nelder-Mead barrier method for constrained optimization

Abstract Full Text(HTML) Figure(2) / Table(1) Related Papers Cited by
  • An interior point modified Nelder Mead method for nonlinearly constrained optimization is described. This method neither uses nor estimates objective function or constraint gradients. A modified logarithmic barrier function is used. The method generates a sequence of points which converges to KKT point(s) under mild conditions including existence of a Slater point. Numerical results are presented that show the algorithm performs well in practice.

    Mathematics Subject Classification: Primary:65K05.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The current polytope $ x_0 $, $ x_1 $, and $ x_2 $ is shown in solid lines. The modified Nelder Mead sub-algorithm first tries to replace the worst polytope point $ x_2 $ with one of $ x_{ic} $, $ x_{oc} $, $ x_r $ or $ x_e $. These four points lie on the dashed line through $ x_2 $ and the centroid $ \bar{x} $ of the remaining polytope points. If this fails to give sufficient descent, the fictitious polytope $ y_1 $, $ y_2 $, $ H $ is used, where the fictitious polytope's worst point $ H $ is reflected through the centroid $ \bar{y} $ of that polytope's remaining points, giving a fictitous new low point $ x_0 $. The expand step is then tried from this fictitious polytope, giving the pseudo-expand point $ x_{pe} $. The points $ y_1,\ldots,y_n $ ($ y_1 $ and $ y_2 $ here) and $ x_{pe} $ form a frame around $ x_0 $

    Figure 2.  Data profiles for PENMECO and V-ORTHOMADS on 100 randomly generated cones test functions from [24], in 12, 18, and 24 dimensions with 11 constraints. Each curve gives the number of problems solved to an accuracy $ E_f < 10^{-4} $ within $ N $ simplex gradients, which is $ N(n+1) $ evaluations of $ f $

    Table 1.  Numerical results for the 26 test problems. Problems 1-11 are smooth, the rest are nonsmooth.

    PENMECO ORTHOMADS PATTERNSEARCH
    function $ n $ $ q $ nf nc(all) nc(I) $ E_f $ $ \max(c) $ nf nc $ E_f $ nf $ E_f $
    1 HS43 Rosen-Suzuki 4 3 8186 8209 - 4e-9 -3e-8 1328 2116 4e-4 2725 0.5
    2 HS44 4 10 6556 6587 17 4e-9 -1e-9 26 365 0 4577 2e-7
    3 HS45 5 10 7896 7949 41 2e-9 -4e-10 56 494 0 5359 0.43
    4 HS72 4 10 3802 4401 - 2e-8 -2e-15 5074 6411 3e-4 15760 5e-4
    5 HS76 4 7 3194 3458 140 1e-10 -2e-11 411 1156 0.01 76909 0.014
    6 HS93 6 1 14709 22001 - 6e-3 -1e-13 4643 6827 3e-3 1105 2e-3
    7 HS100 7 4 45073 45163 - 4e-6 -1e-3 2694 4792 5e-4 5205 5e-3
    8 HS108 9 14 24982 26198 1058 2e-8 -2e-8 5226 14443 0.4 13307 0.26
    9 Audet-Dennis cresc. 10 2 52532 52921 - 3e-7 -4e-9 22267 29561 1e-4 26004 0.84
    10 mod. Jennrich-Sam. 12 10 71702 80014 - 3.4 -0.10 6336 33694 28.5 17145 29.4
    11 mod. vardim 21 1 79667 80468 468 1e-7 -1e-7 17997 80002 5e-7 - -
    12 LV4.1 mad1 2 1 2421 2427 - 4e-9 -3e-11 369 587 4e-9 635 3e-4
    13 LV4.2 mad2 2 1 1924 1932 - 2e-9 -2e-9 323 504 8e-6 1827 1e-7
    14 LV4.3 mad4 2 1 3070 3076 - 4e-9 -3e-11 4034 4639 4e-9 1995 1e-6
    15 LV4.4 mad5 2 1 3363 3410 - 5e-9 -9e-11 147 265 5e-5 695 8e-5
    16 mod. Beale 5 3 27525 27591 15 1e-9 -8e-10 5022 9087 0.03 37462 0.24
    17 LV4.5 pentagon 6 15 29246 29373 108 5e-6 -1e-9 6948 12452 0.04 13472 0.16
    18 LV4.7 mod. equil 7 8 23739 23821 - 4e-5 -0.03 53633 53701 1.9 12322 3e-3
    19 mod. Zakharov 8 2 32469 32921 86 1e-10 -5e-11 10982 22115 1e-4 47017 8e-10
    20 LV4.8 Wong2 10 3 79589 80000 - 8e-5 -3e-9 18436 24656 0.17 9420 0.2
    21 maxQ10 10 8 79777 80001 - 2e-4 -3e-5 11916 22834 1.8 14195 3.4
    22 chainLQ 10 8 79861 80995 995 2e-7 -5e-7 0 821 infeas. 59740 15
    23 crescentI 20 1 79720 80000 - 8e-5 -9e-9 23788 33759 0.78 52699 0.013
    24 crescentII 20 1 79603 80029 29 8e-10 -8e-10 41328 50365 2e-9 29710 6e-9
    25 chainCB3I 20 1 79712 80000 - 9e-11 -3e-10 44512 80007 1e-3 55562 0.032
    26 chainCB3II 20 1 66735 66752 - 9e-6 -2e-3 69767 70523 4e-4 71610 0.14
     | Show Table
    DownLoad: CSV
  • [1] C. Audet and J. E. Dennis Jr., Analysis of generalized pattern searches, SIAM J. Optim., 13 (2003), 889-903.  doi: 10.1137/S1052623400378742.
    [2] C. Audet and J. E. Dennis Jr., Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17 (2006), 188-217.  doi: 10.1137/040603371.
    [3] C. Audet and J. E. Dennis Jr., A progressive barrier for derivative free nonlinear programming, SIAM J. Optim., 20 (2009), 445-472.  doi: 10.1137/070692662.
    [4] M. A. Abramson, C. Audet, J. E. Dennis Jr. and S. Le Digabel, orthoMADS: a deterministic MADS instance with orthogonal directions, SIAM J. Optim., 20 (2009), 948-966. doi: 10.1137/080716980.
    [5] F. H. Clarke, Optimization and Non-smooth Analysis, SIAM classics in applied mathematics, New York, 1990. doi: 10.1137/1.9781611971309.
    [6] I. D. Coope and C. J. Price, Frame based methods for unconstrained optimization, J. Optim. Theory and Appl., 107 (2000), 261-274.  doi: 10.1023/A:1026429319405.
    [7] I. D. Coope and C. J. Price, On the convergence of grid based methods for unconstrained optimization, SIAM J. Optim., 11 (2001), 859-869.  doi: 10.1137/S1052623499354989.
    [8] I. D. Coope and C. J. Price, Positive bases in numerical optimization, Comput. Optim. and Appl., 21 (2002), 169-175.  doi: 10.1023/A:1013760716801.
    [9] C. Davis, Theory of positive linear dependence, Amer. J. Math., 76 (1954), 733-746. doi: 10.2307/2372648.
    [10] A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968.
    [11] F. Gao and L. Han, Implementing the Nelder Mead simplex algorithm with adaptive parameters, Comput. Optim. Appl., 51 (2012), 259-277. 
    [12] W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer, Berlin, 1981. doi: 10.1007/BF00934594.
    [13] N. Karmitsa, Test Problems for Large-Scale Nonsmooth Minimization, Department of Mathematical Information Technology Report B. 4/2007, University of Jyväskylä, Finland, 2007.
    [14] C. T. Kelley, Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition, SIAM J. Optim., 10 (1999), 43-55.  doi: 10.1137/S1052623497315203.
    [15] T. G. KoldaR. M. Lewis and V. Torczon, Optimization by direct search: New perspectives on some classical and modern methods, SIAM Rev., 45 (2003), 385-482.  doi: 10.1137/S003614450242889.
    [16] J. C. LagariasJ. A. ReedsM. H. Wright and P. E. Wright, Convergence properties of the Nelder-Mead simplex method in low dimensions, SIAM J. Optim., 9 (1999), 112-147.  doi: 10.1137/S1052623496303470.
    [17] J. C. LagariusB. Poonen and M. H. Wright, Convergence of the restricted Nelder Mead algorithm in two dimensions, SIAM J. Optim., 22 (2012), 501-532.  doi: 10.1137/110830150.
    [18] L. Lukšan and J. Vlček, Test problems for nonsmooth unconstrained and linearly constrained optimization, Tech. Report 798, Prague: Institute of Computer Science, Academy of Sciences of the Czech Republic, 2000.
    [19] K. I. M. McKinnon, A simplex method for function minimization, SIAM J. Optim., 9 (1999), 148-158.  doi: 10.1137/S1052623496303482.
    [20] J. J. MoreB. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software, 7 (1981), 17-41.  doi: 10.1145/355934.355936.
    [21] L. Nazareth and P. Tseng, Gilding the lily: a variant of the Nelder Mead algorithm based on golden-section search, Comput. Optim. Appl., 22 (2002), 133-144.  doi: 10.1023/A:1014842520519.
    [22] J. A. Nelder and R. Mead, A simplex method for function minimization, Computer J., 7 (1965), 308-313.  doi: 10.1093/comjnl/7.4.308.
    [23] M. J. D. Powell, Direct search algorithms for optimization calculations, Acta Numerica, 7 (1998), 287-336.  doi: 10.1017/S0962492900002841.
    [24] C. J. Price., Direct search nonsmooth constrained optimization via rounded $\ell_1$ penalty functions, Optim. Methods & Software, (2020), DOI: 10.1080/10556788.2020.1746961
    [25] C. J. Price and I. D. Coope, Frames and grids in unconstrained and linearly constrained optimization: a non-smooth approach, SIAM J. Optim., 14 (2003), 415-438.  doi: 10.1137/S1052623402407084.
    [26] C. J. PriceI. D. Coope and D. Byatt, A convergent variant of the Nelder Mead algorithm, J. Optim. Theory and Appl., 113 (2002), 5-19.  doi: 10.1023/A:1014849028575.
    [27] ,,
    [28] V. Torczon, On the convergence of pattern search algorithms, SIAM J. Optim., 7 (1997), 1-25.  doi: 10.1137/S1052623493250780.
    [29] P. Tseng, Fortified-descent simplicial search method: a general approach, SIAM J. Optim., 10 (1999), 269-288.  doi: 10.1137/S1052623495282857.
    [30] M. H. Wright, Direct search methods: once scorned now respectable, in Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis Addison-Wesley, Reading, MA and Longman, Harlow, UK, 1996.
    [31] W.-C. Yu, Positive basis and a class of direct search techniques, Scientia Sinica (special issue), 1 (1979).
    [32] W. C. Yu and Y.-X. Li, A direct search method by the local positive basis for the nonlinearly constrained optimization, Chinese Annals of Math., 2 (1981), 269-280. 
  • 加载中

Figures(2)

Tables(1)

SHARE

Article Metrics

HTML views(1598) PDF downloads(353) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return