Article Contents
Article Contents

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

• * Corresponding author
• 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:

• 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
•  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)