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

M. S. Lee; B. S. Goh; H. G. Harno; K. H. Lim

doi:10.3934/naco.2018020

Article Contents

2018, Volume 8, Issue 3: 315-326. Doi: 10.3934/naco.2018020

This issue Previous Article A controlled treatment strategy applied to HIV immunology model Next Article Approximate greatest descent in neural network optimization

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

1.
School of Economics and Management, Xiamen University Malaysia, Selangor, Malaysia
2.
School of Electrical Engineering, Computing and Mathematical Sciences, Curtin University, Perth, Australia
3.
Department of Aerospace and Software Engineering, Gyeongsang National University, South Korea
4.
Department of Electrical and Computer Engineering, Curtin University Malaysia, Sarawak, Malaysia

* Corresponding author
* Corresponding author

Received: April 2017

Revised: June 2017

Published: June 2018

Abstract Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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$

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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
Problem	$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

Related Papers

Cited by

References

	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.