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

On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints

  • * Corresponding author

    * Corresponding author 
Abstract / Introduction Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by
  • Lagrange multipliers are usually used in numerical methods to solve equality constrained optimization problems. However, when the intersection between a search region for a current point and the feasible set defined by the equality constraints is empty, Lagrange multipliers cannot be used without additional conditions. To cope with this condition, a new method based on a two-phase approximate greatest descent approach is presented in this paper. In Phase-Ⅰ, an accessory function is used to drive a point towards the feasible set and the optimal point of an objective function. It has been observed that for some current points, it may be necessary to maximize the objective function while minimizing the constraint violation function in a current search region in order to construct the best numerical iterations. When the current point is close to or inside the feasible set and when optimality conditions are nearly satisfied, the numerical iterations are switched to Phase-Ⅱ. The Lagrange multipliers are defined and used in this phase. The approximate greatest descent method is then applied to minimize a merit function which is constructed from the optimality conditions. Results of numerical experiments are presented to show the effectiveness of the aforementioned two-phase method.

    Mathematics Subject Classification: Primary: 49M15, 65K10; Secondary: 90C30, 90C90.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Level curves of an objective function $f(x_1,x_2) = x_1+x^{2}_2$ which is minimized and is subjected to an equality constraint $x_1^2+x_2^2 = 1$

    Figure 2.  Comparison of CPU time (second) between SQP and AGD

    Figure 3.  Comparison of number of iteration between SQP and AGD

    Table 1.  Comparison of SQP method and a two-phase AGD method (Parameters: $n$- number of variables, $m$-number of equations, $k$-number of iterations, $f(x^*)$-optimal value)

    Problem Dim. SQP Two-Phase AGD
    $n$ $m$ $k$ $f(x^*)$ CPU Time (second) $k$ $f(x^*)$ CPU Time (second)
    BT02 3 1 19 $3.26\times 10^{-2}$ 0.9631 14 $3.26\times 10^{-2}$ 0.3323
    BT03 5 3 8 $4.09\times 10^{0} $ 0.9505 10 $4.09\times 10^{0} $ 0.5181
    BT04 3 2 13 $-4.55\times 10^{1} $ 0.9631 7 $-4.55\times 10^{1} $ 0.3484
    BT05 3 2 7 $9.61\times10^{2}$ 0.9157 8 $9.61\times10^{2}$ 0.4478
    BT06 5 2 19 $2.77\times 10^{-1} $ 0.9415 9 $2.77\times 10^{-1} $ 0.3677
    BT09 4 2 12 $-1.00\times 10^{0} $ 1.0625 12 $-1.00\times 10^{0} $ 0.4392
    BT10 2 2 6 $-1.00\times 10^{0} $ 0.8608 10 $-1.00\times 10^{0}$ 0.2908
    BT11 5 3 11 $8.23\times 10^{-1} $ 0.9820 10 $8.23\times 10^{-1} $ 0.5528
    BT12 5 3 8 $6.19\times 10^{0} $ 0.9406 24 $6.19\times 10^{0} $ 0.6012
    HS06 2 1 9 $5.32\times 10^{-17} $ 0.8338 5 $3.84\times 10^{-10} $ 0.2483
    HS07 2 1 9 $-1.73\times 10^{0} $ 0.9611 9 $ -1.73\times 10^{0} $ 0.3172
    HS08 2 2 6 $-1.00\times 10^{0} $ 0.8552 5 $-1.00\times 10^{0} $ 0.2725
    HS26 3 1 49 $1.94\times 10^{-11} $ 1.0768 12 $ 1.71\times 10^{-6} $ 0.3273
    HS27 3 1 22 $4.00\times 10^{-2}$ 2.5163 12 $4.00\times 10^{-2}$ 0.3359
    HS28 3 1 9 $6.42\times 10^{-16}$ 0.9985 5 $2.81\times 10^{-8} $ 0.3426
    HS39 4 2 12 $-1.00\times 10^{0} $ 0.8979 12 $-1.00\times 10^{0} $ 0.3527
    HS40 4 3 6 $-2.50\times 10^{-1}$ 0.9206 3 $-2.50\times 10^{-1}$ 0.3657
    HS46 5 2 29 $5.11\times 10^{-11}$ 1.1155 8 $2.93\times 10^{-5}$ 0.4488
    HS48 5 2 9 $6.14\times 10^{-13}$ 0.8890 3 $3.12\times 10^{-12}$ 0.3000
    HS49 5 2 26 $2.36\times 10^{-9}$ 1.0728 10 $2.03\times 10^{-4}$ 0.4787
    HS50 5 3 14 $2.10\times 10^{-14}$ 0.8918 9 $4.68\times 10^{-15}$ 0.3810
    HS51 5 3 8 $7.39\times 10^{-17}$ 0.8689 4 $1.94\times 10^{-11}$ 0.3319
    HS52 5 3 8 $5.33\times 10^{0}$ 0.8330 10 $5.33\times 10^{0}$ 0.4217
    HS53 5 3 7 $4.09\times 10^{0}$ 0.9753 10 $4.09\times 10^{0}$ 0.4867
    HS61 3 2 11 $-1.44\times 10^{2}$ 0.8812 7 $-1.44\times 10^{2}$ 0.3707
    HS77 5 2 16 $2.42\times 10^{-1}$ 0.9192 11 $2.42\times 10^{-1}$ 0.4633
    HS79 5 3 12 $7.88\times 10^{-2}$ 0.8923 5 $7.88\times 10^{-2}$ 0.3731
    HS1001Lnp 7 2 16 $6.81\times 10^{2}$ 0.9920 11 $6.81\times 10^{2}$ 0.7957
    maratos 2 1 3 $-1.00\times 10^{0} $ 0.8387 2 $-1.00\times 10^{0} $ 0.2440
    mswright 5 3 19 $1.29\times 10^{0}$ 1.1139 13 $1.29\times 10^{0}$ 0.5045
     | Show Table
    DownLoad: CSV
  •   I. Bongartz , A. R. Conn , N. I. M. Gould  and  P. L. Toint , CUTE: Constrained and unconstrained testing environment, ACM Transactions on Mathematical Software, 21 (1995) , 123-160.  doi: 10.1145/200979.201043.
      R. H. Bryd , F. Curtis  and  J. Nocedal , An inexact SQP method for equality constrained optimization, SIAM Journal of Optimization, 19 (2008) , 351-369.  doi: 10.1137/060674004.
      R. H. Bryd , F. Curtis  and  J. Nocedal , An inexact Newton method for nonconvex equality constrained optimization, Mathematical Programming, 122 (2010) , 273-299.  doi: 10.1007/s10107-008-0248-3.
      A. R. Conn, N. I. M. Gould and P. L. Toint, Trust Region Methods, SIAM, United States of America, 2000. doi: 10.1137/1.9780898719857.
      A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968.
      R. Fletcher  and  S. Leyffer , Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002) , 239-269.  doi: 10.1007/s101070100244.
      P. E. Gill , W. Murray , M. A. Saunders  and  M. H. Wright , Computing forward-difference intervals for numerical optimization, Society for Industrial and Applied Mathematics, 4 (1983) , 310-321.  doi: 10.1137/0904025.
      B. S. Goh , Greatest descent algorithms in unconstrained optimization, Journal of Optimization Theory and Applications, 142 (2009) , 275-289.  doi: 10.1007/s10957-009-9533-4.
      B. S. Goh , Convergence of algorithms in optimization and solutions of nonlinear equations, Journal of Optimization Theory and Applications, 144 (2010) , 43-55.  doi: 10.1007/s10957-009-9583-7.
      B. S. Goh , Approximate greatest descent methods for optimization with equality constraints, Journal of Optimization Theory and Applications, 148 (2011) , 505-527.  doi: 10.1007/s10957-010-9765-3.
      B. S. Goh, W. J. Leong and K. L. Teo, Robustness of convergence proofs in numerical methods in unconstrained optimization, in Optimization and Control Methods in Industrial Engineering and Construction, Intelligent Systems, Control and Automation: Science and Engineering 72 (ed. H. Xu and X. Wang), Springer Science+Business Media Dordrecht, 2014. doi: 10.1007/978-94-017-8044-5_1.
      N. I. M. Gould , D. Orban  and  P. L. Toint , CUTEr, a constrained and unconstrained testing environment (revisited), ACM Transactions on Mathematical Software, 29 (2003) , 373-394. 
      H. Z. Hassan , A. A. Mohamad  and  G. E. Atteia , An algorithm for the finite difference approximation of derivatives with arbitrary degree and order of accuracy, Journal of Computational and Applied Mathematics, 236 (1997) , 2622-2631.  doi: 10.1016/j.cam.2011.12.019.
      Y. C. Ho , Differential games, dynamic optimization and generalized control theory, Journal of Optimization Theory and Applications, 6 (1970) , 179-209.  doi: 10.1007/BF00926600.
      J. P. LaSalle, The Stability of Dynamical Systems, SIAM, Philadelphia, 1976.
      C. Li , Z. Wang  and  D. Zhu , A line search filter inexact reduced Hessian method for nonlinear equality constrained optimization, Journal of Applied Mathematics and Computing, 48 (2015) , 365-380.  doi: 10.1007/s12190-014-0807-0.
      R. S. Stepleman  and  N. D. Winarsky , Adaptive numerical differenctiation, Mathematics of Computation, 33 (1979) , 1257-1264.  doi: 10.1090/S0025-5718-1979-0537969-8.
      G. W. Stewart , A modification of Davidon's minimization method to accept difference approximation of derivatives, Journal of Association for Computing Machinery, 14 (1967) , 72-83.  doi: 10.1145/321371.321377.
      A. Vardi , A trust region algorithm for equality constrained minimization, SIAM Journal of Optimization, 22 (1983) , 575-591.  doi: 10.1137/0722035.
      T. L. Vincent  and  G. Leitmann , Control space properties of cooperative games, Journal of Optimization Theory and Applications, 6 (1970) , 91-116.  doi: 10.1007/BF00927045.
      Y. Yuan , Recent advances in trust region algorithms, Mathematical Programming, 151 (2015) , 249-281.  doi: 10.1007/s10107-015-0893-2.
      L. A. Zadeh , Optimality and non-scalar-valued performance criteria, IEEE Transactions on Automatic Control, 8 (1963) , 59-60.  doi: 10.1109/TAC.1963.1105511.
      X. Zhu  and  D. Pu , A restoration-free filter SQP algorithm for equality constrained optimization, Applied Mathematics and Computation, 219 (2013) , 6016-6029.  doi: 10.1016/j.amc.2012.12.002.
  • 加载中

Figures(3)

Tables(1)

SHARE

Article Metrics

HTML views(2179) PDF downloads(978) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return