
-
Previous Article
Approximate greatest descent in neural network optimization
- NACO Home
- This Issue
-
Next Article
A controlled treatment strategy applied to HIV immunology model
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 |
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.
References:
[1] |
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. |
[2] |
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. |
[3] |
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. |
[4] |
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. |
[5] |
A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968. |
[6] |
R. Fletcher and S. Leyffer,
Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269.
doi: 10.1007/s101070100244. |
[7] |
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. |
[8] |
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. |
[9] |
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. |
[10] |
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. |
[11] |
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. |
[12] |
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. Google Scholar |
[13] |
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. |
[14] |
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. |
[15] |
J. P. LaSalle, The Stability of Dynamical Systems, SIAM, Philadelphia, 1976. |
[16] |
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. |
[17] |
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. |
[18] |
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. |
[19] |
A. Vardi,
A trust region algorithm for equality constrained minimization, SIAM Journal of Optimization, 22 (1983), 575-591.
doi: 10.1137/0722035. |
[20] |
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. |
[21] |
Y. Yuan,
Recent advances in trust region algorithms, Mathematical Programming, 151 (2015), 249-281.
doi: 10.1007/s10107-015-0893-2. |
[22] |
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. |
[23] |
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. |
show all references
References:
[1] |
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. |
[2] |
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. |
[3] |
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. |
[4] |
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. |
[5] |
A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968. |
[6] |
R. Fletcher and S. Leyffer,
Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269.
doi: 10.1007/s101070100244. |
[7] |
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. |
[8] |
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. |
[9] |
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. |
[10] |
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. |
[11] |
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. |
[12] |
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. Google Scholar |
[13] |
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. |
[14] |
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. |
[15] |
J. P. LaSalle, The Stability of Dynamical Systems, SIAM, Philadelphia, 1976. |
[16] |
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. |
[17] |
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. |
[18] |
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. |
[19] |
A. Vardi,
A trust region algorithm for equality constrained minimization, SIAM Journal of Optimization, 22 (1983), 575-591.
doi: 10.1137/0722035. |
[20] |
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. |
[21] |
Y. Yuan,
Recent advances in trust region algorithms, Mathematical Programming, 151 (2015), 249-281.
doi: 10.1007/s10107-015-0893-2. |
[22] |
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. |
[23] |
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. |



Problem | Dim. | SQP | Two-Phase AGD | |||||
CPU Time (second) | CPU Time (second) | |||||||
BT02 | 3 | 1 | 19 | 0.9631 | 14 | 0.3323 | ||
BT03 | 5 | 3 | 8 | 0.9505 | 10 | 0.5181 | ||
BT04 | 3 | 2 | 13 | 0.9631 | 7 | 0.3484 | ||
BT05 | 3 | 2 | 7 | 0.9157 | 8 | 0.4478 | ||
BT06 | 5 | 2 | 19 | 0.9415 | 9 | 0.3677 | ||
BT09 | 4 | 2 | 12 | 1.0625 | 12 | 0.4392 | ||
BT10 | 2 | 2 | 6 | 0.8608 | 10 | 0.2908 | ||
BT11 | 5 | 3 | 11 | 0.9820 | 10 | 0.5528 | ||
BT12 | 5 | 3 | 8 | 0.9406 | 24 | 0.6012 | ||
HS06 | 2 | 1 | 9 | 0.8338 | 5 | 0.2483 | ||
HS07 | 2 | 1 | 9 | 0.9611 | 9 | 0.3172 | ||
HS08 | 2 | 2 | 6 | 0.8552 | 5 | 0.2725 | ||
HS26 | 3 | 1 | 49 | 1.0768 | 12 | 0.3273 | ||
HS27 | 3 | 1 | 22 | 2.5163 | 12 | 0.3359 | ||
HS28 | 3 | 1 | 9 | 0.9985 | 5 | 0.3426 | ||
HS39 | 4 | 2 | 12 | 0.8979 | 12 | 0.3527 | ||
HS40 | 4 | 3 | 6 | 0.9206 | 3 | 0.3657 | ||
HS46 | 5 | 2 | 29 | 1.1155 | 8 | 0.4488 | ||
HS48 | 5 | 2 | 9 | 0.8890 | 3 | 0.3000 | ||
HS49 | 5 | 2 | 26 | 1.0728 | 10 | 0.4787 | ||
HS50 | 5 | 3 | 14 | 0.8918 | 9 | 0.3810 | ||
HS51 | 5 | 3 | 8 | 0.8689 | 4 | 0.3319 | ||
HS52 | 5 | 3 | 8 | 0.8330 | 10 | 0.4217 | ||
HS53 | 5 | 3 | 7 | 0.9753 | 10 | 0.4867 | ||
HS61 | 3 | 2 | 11 | 0.8812 | 7 | 0.3707 | ||
HS77 | 5 | 2 | 16 | 0.9192 | 11 | 0.4633 | ||
HS79 | 5 | 3 | 12 | 0.8923 | 5 | 0.3731 | ||
HS1001Lnp | 7 | 2 | 16 | 0.9920 | 11 | 0.7957 | ||
maratos | 2 | 1 | 3 | 0.8387 | 2 | 0.2440 | ||
mswright | 5 | 3 | 19 | 1.1139 | 13 | 0.5045 |
Problem | Dim. | SQP | Two-Phase AGD | |||||
CPU Time (second) | CPU Time (second) | |||||||
BT02 | 3 | 1 | 19 | 0.9631 | 14 | 0.3323 | ||
BT03 | 5 | 3 | 8 | 0.9505 | 10 | 0.5181 | ||
BT04 | 3 | 2 | 13 | 0.9631 | 7 | 0.3484 | ||
BT05 | 3 | 2 | 7 | 0.9157 | 8 | 0.4478 | ||
BT06 | 5 | 2 | 19 | 0.9415 | 9 | 0.3677 | ||
BT09 | 4 | 2 | 12 | 1.0625 | 12 | 0.4392 | ||
BT10 | 2 | 2 | 6 | 0.8608 | 10 | 0.2908 | ||
BT11 | 5 | 3 | 11 | 0.9820 | 10 | 0.5528 | ||
BT12 | 5 | 3 | 8 | 0.9406 | 24 | 0.6012 | ||
HS06 | 2 | 1 | 9 | 0.8338 | 5 | 0.2483 | ||
HS07 | 2 | 1 | 9 | 0.9611 | 9 | 0.3172 | ||
HS08 | 2 | 2 | 6 | 0.8552 | 5 | 0.2725 | ||
HS26 | 3 | 1 | 49 | 1.0768 | 12 | 0.3273 | ||
HS27 | 3 | 1 | 22 | 2.5163 | 12 | 0.3359 | ||
HS28 | 3 | 1 | 9 | 0.9985 | 5 | 0.3426 | ||
HS39 | 4 | 2 | 12 | 0.8979 | 12 | 0.3527 | ||
HS40 | 4 | 3 | 6 | 0.9206 | 3 | 0.3657 | ||
HS46 | 5 | 2 | 29 | 1.1155 | 8 | 0.4488 | ||
HS48 | 5 | 2 | 9 | 0.8890 | 3 | 0.3000 | ||
HS49 | 5 | 2 | 26 | 1.0728 | 10 | 0.4787 | ||
HS50 | 5 | 3 | 14 | 0.8918 | 9 | 0.3810 | ||
HS51 | 5 | 3 | 8 | 0.8689 | 4 | 0.3319 | ||
HS52 | 5 | 3 | 8 | 0.8330 | 10 | 0.4217 | ||
HS53 | 5 | 3 | 7 | 0.9753 | 10 | 0.4867 | ||
HS61 | 3 | 2 | 11 | 0.8812 | 7 | 0.3707 | ||
HS77 | 5 | 2 | 16 | 0.9192 | 11 | 0.4633 | ||
HS79 | 5 | 3 | 12 | 0.8923 | 5 | 0.3731 | ||
HS1001Lnp | 7 | 2 | 16 | 0.9920 | 11 | 0.7957 | ||
maratos | 2 | 1 | 3 | 0.8387 | 2 | 0.2440 | ||
mswright | 5 | 3 | 19 | 1.1139 | 13 | 0.5045 |
[1] |
Caiping Liu, Heungwing Lee. Lagrange multiplier rules for approximate solutions in vector optimization. Journal of Industrial & Management Optimization, 2012, 8 (3) : 749-764. doi: 10.3934/jimo.2012.8.749 |
[2] |
Theodore Tachim-Medjo. Optimal control of a two-phase flow model with state constraints. Mathematical Control & Related Fields, 2016, 6 (2) : 335-362. doi: 10.3934/mcrf.2016006 |
[3] |
Feng Ma, Mingfang Ni. A two-phase method for multidimensional number partitioning problem. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 203-206. doi: 10.3934/naco.2013.3.203 |
[4] |
Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 |
[5] |
Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123 |
[6] |
Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019075 |
[7] |
Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365 |
[8] |
Stefan Berres, Ricardo Ruiz-Baier, Hartmut Schwandt, Elmer M. Tory. An adaptive finite-volume method for a model of two-phase pedestrian flow. Networks & Heterogeneous Media, 2011, 6 (3) : 401-423. doi: 10.3934/nhm.2011.6.401 |
[9] |
Anurag Jayswala, Tadeusz Antczakb, Shalini Jha. Second order modified objective function method for twice differentiable vector optimization problems over cone constraints. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 133-145. doi: 10.3934/naco.2019010 |
[10] |
Feimin Huang, Dehua Wang, Difan Yuan. Nonlinear stability and existence of vortex sheets for inviscid liquid-gas two-phase flow. Discrete & Continuous Dynamical Systems - A, 2019, 39 (6) : 3535-3575. doi: 10.3934/dcds.2019146 |
[11] |
Theodore Tachim Medjo. A two-phase flow model with delays. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3273-3294. doi: 10.3934/dcdsb.2017137 |
[12] |
Jan Prüss, Jürgen Saal, Gieri Simonett. Singular limits for the two-phase Stefan problem. Discrete & Continuous Dynamical Systems - A, 2013, 33 (11&12) : 5379-5405. doi: 10.3934/dcds.2013.33.5379 |
[13] |
Marianne Korten, Charles N. Moore. Regularity for solutions of the two-phase Stefan problem. Communications on Pure & Applied Analysis, 2008, 7 (3) : 591-600. doi: 10.3934/cpaa.2008.7.591 |
[14] |
Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019046 |
[15] |
T. Tachim Medjo. Averaging of an homogeneous two-phase flow model with oscillating external forces. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3665-3690. doi: 10.3934/dcds.2012.32.3665 |
[16] |
Eberhard Bänsch, Steffen Basting, Rolf Krahl. Numerical simulation of two-phase flows with heat and mass transfer. Discrete & Continuous Dynamical Systems - A, 2015, 35 (6) : 2325-2347. doi: 10.3934/dcds.2015.35.2325 |
[17] |
Ciprian G. Gal, Maurizio Grasselli. Longtime behavior for a model of homogeneous incompressible two-phase flows. Discrete & Continuous Dynamical Systems - A, 2010, 28 (1) : 1-39. doi: 10.3934/dcds.2010.28.1 |
[18] |
Jie Jiang, Yinghua Li, Chun Liu. Two-phase incompressible flows with variable density: An energetic variational approach. Discrete & Continuous Dynamical Systems - A, 2017, 37 (6) : 3243-3284. doi: 10.3934/dcds.2017138 |
[19] |
V. S. Manoranjan, Hong-Ming Yin, R. Showalter. On two-phase Stefan problem arising from a microwave heating process. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1155-1168. doi: 10.3934/dcds.2006.15.1155 |
[20] |
Daniela De Silva, Fausto Ferrari, Sandro Salsa. Recent progresses on elliptic two-phase free boundary problems. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 6961-6978. doi: 10.3934/dcds.2019239 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]