# American Institute of Mathematical Sciences

September  2018, 8(3): 315-326. doi: 10.3934/naco.2018020

## 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

Received  April 2017 Revised  June 2017 Published  June 2018

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.

Citation: M. S. Lee, B. S. Goh, H. G. Harno, K. H. Lim. On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 315-326. doi: 10.3934/naco.2018020
##### References:

show all references

##### References:
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$
Comparison of CPU time (second) between SQP and AGD
Comparison of number of iteration between SQP and AGD
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
 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
 [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] 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 [7] 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 [8] 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 [9] 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 [10] 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 [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, 2020, 10 (2) : 165-175. 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: