On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization

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

doi:10.3934/naco.2020014

Article Contents

2021, Volume 11, Issue 1: 45-61. Doi: 10.3934/naco.2020014

This issue Previous Article On the GSOR iteration method for image restoration Next Article Piecewise quadratic bounding functions for finding real roots of polynomials

On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization

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

^* Corresponding author: M. S. LEE (Email: moksianglee@gmail.com)
^* Corresponding author: M. S. LEE (Email: moksianglee@gmail.com)

Received: May 31, 2019

Revised: July 31, 2019

Early access: February 2020

Published: March 2021

Abstract Full Text(HTML) Figure(4) / Table(6) Related Papers Cited by

Abstract

A bang-bang iteration method equipped with a component-wise line search strategy is introduced to solve unconstrained optimization problems. The main idea of this method is to formulate an unconstrained optimization problem as an optimal control problem to obtain an optimal trajectory. However, the optimal trajectory can only be generated by impulsive control variables and it is a straight line joining a guessed initial point to a minimum point. Thus, a priori bounds are imposed on the control variables in order to obtain a feasible solution. As a result, the optimal trajectory is made up of bang-bang control sub-arcs, which form an iterative model based on the Lyapunov function's theorem. This is to ensure monotonic decrease of the objective function value and convergence to a desirable minimum point. However, a chattering behavior may occur near the solution. To avoid this behavior, the Newton iterations are then applied to the proposed method via a two-phase approach to achieve fast convergence. Numerical experiments show that this new approach is efficient and cost-effective to solve the unconstrained optimization problems.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. A backtracking procedure to obtain the next iterative point $ x(k+1) $ from the current point $ x(k) $ on an objective function with two variables

Download: Full-size image PowerPoint slide

Figure 2. The AGD with rectangular search regions approaching the minimum point $ x^{*} $ from the initial point $ x(0) $

Download: Full-size image PowerPoint slide

Figure 3. Performance profiles based on the CPU time

Download: Full-size image PowerPoint slide

Figure 4. Performance profiles based on the number of iterations

Download: Full-size image PowerPoint slide

| Show Table

DownLoad: CSV

| Show Table

DownLoad: CSV

Table 1. The iterations of the AGDRN method on Booth function (40) in Phase-Ⅰ and Phase-Ⅱ

Phase-Ⅰ
$ k $	$ f(x) $	$ \\|g(x)\\| $	$ \\|\Delta x\\| $
0	$ 3.79\times 10^{3} $	$ 3.69\times 10^{2} $	$ 1.80\times 10^{1} $
1	$ 3.69\times 10^{2} $	$ 1.15\times 10^{2} $	$ 1.41\times 10^{1} $
2	$ 3.69\times 10^{2} $	$ 1.15\times 10^{2} $	$ 1.27\times 10^{1} $
3	$ 2.38\times 10^{1} $	$ 9.17\times 10^{1} $	$ 1.15\times 10^{1} $
4	$ 4.04\times 10^{1} $	$ 3.62\times 10^{1} $	$ 3.09\times 10^{0} $
5	$ 1.01\times 10^{1} $	$ 1.48\times 10^{1} $	$ 2.78\times 10^{0} $
6	$ 4.51\times 10^{0} $	$ 4.29\times 10^{0} $	$ 7.52\times 10^{-1} $
7	$ 2.10\times 10^{0} $	$ 2.95\times 10^{0} $	$ 6.76\times 10^{-1} $
8	$ 1.60\times 10^{0} $	$ 2.60\times 10^{0} $	$ 1.83\times 10^{-1} $
9	$ 1.22\times 10^{0} $	$ 2.28\times 10^{0} $	$ 1.64\times 10^{-1} $
10	$ 9.13\times 10^{-1} $	$ 1.99\times 10^{0} $	$ 1.48\times 10^{-1} $
11	$ 6.77\times 10^{-1} $	$ 1.74\times 10^{0} $	$ 1.33\times 10^{-1} $
12	$ 4.96\times 10^{-1} $	$ 1.52\times 10^{0} $	$ 1.20\times 10^{-1} $
13	$ 3.57\times 10^{-1} $	$ 1.33\times 10^{0} $	$ 1.08\times 10^{-1} $
14	$ 2.52\times 10^{-1} $	$ 1.16\times 10^{0} $	$ 9.71\times 10^{-2} $
Phase-Ⅱ
$ j $	$ f(x) $	$ \\|g(x)\\| $	{det H}
0	$ 2.52\times 10^{-1} $	$ 1.16\times 10^{0} $	$ 3.60\times 10^{1} $
1	$ 4.54\times 10^{-18} $	$ 4.34\times 10^{-9} $	$ 3.60\times 10^{1} $

| Show Table

DownLoad: CSV

Table 2. The iterations of the AGDRN method on Powell function (41) in Phase-Ⅰ and Phase-Ⅱ

Phase-Ⅰ
$ k $	$ f(x) $	$ \\|g(x)\\| $	$ \\|\Delta x\\| $
0	$ 2.60\times 10^{2} $	$ 2.53\times 10^{2} $	$ 5.00\times 10^{0} $
1	$ 6.56\times 10^{0} $	$ 1.31\times 10^{1} $	$ 3.54\times 10^{0} $
2	$ 1.31\times 10^{0} $	$ 4.51\times 10^{0} $	$ 2.61\times 10^{0} $
3	$ -2.46\times 10^{-1} $	$ 9.70\times 10^{-1} $	$ 1.06\times 10^{0} $
Phase-Ⅱ
$ j $	$ f(x) $	$ \\|g(x)\\| $	{det H}
0	$ -2.46\times 10^{-1} $	$ 9.70\times 10^{-1} $	$ 5.00\times 10^{-1} $
1	$ -5.49\times 10^{-1} $	$ 6.63\times 10^{-1} $	$ 1.36\times 10^{1} $
2	$ -5.82\times 10^{-1} $	$ 5.20\times 10^{-2} $	$ 1.09\times 10^{1} $
3	$ -5.82\times 10^{-1} $	$ 7.61\times 10^{-4} $	$ 1.06\times 10^{1} $
4	$ -5.82\times 10^{-1} $	$ 1.71\times 10^{-7} $	$ 1.06\times 10^{1} $

| Show Table

DownLoad: CSV

Table 3. Comparison of Phase-Ⅱ replacement with other methods to minimize the Gulf research and development function

Methods	$ \boldsymbol{f(x^{*})} $	$ \boldsymbol{\\|g(x)\\|} $	k	CPU Time (s)
AGDS	$ 5.40\times 10^{-5} $	$ 6.40\times 10^{-9} $	37	$ 9.06\times 10^{-1} $
BTR	$ 5.40\times 10^{-5} $	$ 5.96\times 10^{-8} $	81	$ 1.75\times 10^{0} $
AGDRN	$ 3.11\times 10^{-2} $	$ 6.61\times 10^{-2} $	500	$ 2.15\times 10^{1} $
AGD-RS	$ 5.40\times 10^{-5} $	$ 1.35\times 10^{-7} $	83	$ 1.63\times 10^{0} $

| Show Table

DownLoad: CSV

Table 4. Comparison of Phase-Ⅱ replacement with other methods to minimize the Kowalik Osborne function

Methods	$ \boldsymbol{f(x^{*})} $	$ \boldsymbol{\\|g(x)\\|} $	$ \boldsymbol{k} $	CPU Time (s)
AGDS	$ 3.08\times 10^{-4} $	$ 8.60\times 10^{-8} $	14	$ 6.09\times 10^{-1} $
BTR	$ 3.08\times 10^{-4} $	$ 5.76\times 10^{-8} $	16	$ 5.94\times 10^{-1} $
AGDRN	$ 5.08\times 10^{-4} $	$ 3.84\times 10^{-3} $	499	$ 2.38\times 10^{1} $
AGD-RS	$ 3.08\times 10^{-4} $	$ 8.60\times 10^{-8} $	14	$ 4.06\times 10^{-1} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	N. Andrei, An unconstrained optimization test functions collection, Adv. Model. Optim., 10 (2008), 147-161.
[2]	D. Bushaw, Optimal discontinuous forcing terms, in Contributions to the Theory of Nonlinear Oscillations, Vol. IV (ed. S. Lefshetz), Princeton Univ. Press, Princeton, New Jersey, (1958), 29–52.
[3]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.
[4]	R. Fletcher, Practical Methods of Optimization Volume 1: Unconstrained Optimization, John Wiley & Sons, 1987.
[5]	I. Flüotz and H. Junr, Optimum and quasi-optimum control of third-and fourth-order systems, Technical Report 2, 1963.
[6]	A. Fuller, Relay control systems optimized for various performance criteria, in Automatic and Remote Control, Proc. First World Congress IFAC Moscow, vol. 1, 1960, 510–519.
[7]	P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Computing forward-difference intervals for numerical optimization, SIAM Journal on Scientific and Statistical Computing, 4 (1983), 310-321. doi: 10.1137/0904025.
[8]	B. S. Goh, Algorithms for unconstrained optimization problems via control theory, Journal of Optimization Theory and Applications, 92 (1997), 581-604. doi: 10.1023/A:1022607507153.
[9]	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.
[10]	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.
[11]	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.
[12]	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, Springer Netherlands, (2014), 1–9.
[13]	B. S. Goh and D. B. McDonald, Newton methods to solve a system of nonlinear algebraic equations, Journal of Optimization Theory and Applications, 164 (2015), 261-276. doi: 10.1007/s10957-014-0544-4.
[14]	A. Hedar, Studies on Metaheuristics for Continuous Global Optimization Problems, PhD Thesis, Kyoto University, Japan, 2004.
[15]	J. Kowalik and J. Morrison, Analysis of kinetic data for allosteric enzyme reactions as a nonlinear regression problem, Mathematical Biosciences, 2 (1968), 57-66.
[16]	I. Kupka, The ubiquity of fuller's phenomenon, Nonlinear Controllability and Optimal Control, 133 (1990), 313-350.
[17]	J. P. LaSalle, Time optimal control systems, Proceedings of the National Academy of Sciences of the United States of America. doi: 10.1073/pnas.45.4.573.
[18]	J. P. LaSalle, Recent advances in liapunov stability theory, SIAM Review, 6 (1964), 1-11. doi: 10.1137/1006001.
[19]	M. S. Lee, B. S. Goh, H. G. Harno and K. H. Lim, On a two-phase approximate greatest descent method for nonlinear optimization with equality constraints, Numerical Algebra, Control & Optimization, 8 (2018), 325-336. doi: 10.3934/naco.2018020.
[20]	G. Leitmann, The Calculus of Variations and Optimal Control, Vol. 20 of Mathematical Concepts and Methods in Science and Engineering, Plenum Press, New York, 1981.
[21]	J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software (TOMS), 7 (1981), 17-41. doi: 10.1145/355934.355936.
[22]	J. M. Ortega, Stability of difference equations and convergence of iterative processes, SIAM Journal on Numerical Analysis, 10 (1973), 268-282. doi: 10.1137/0710026.
[23]	J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, NY, 1970.
[24]	B. T. Polyak, Newton's method and its use in optimization, European Journal of Operational Research, 181 (2007), 1086-1096. doi: 10.1016/j.ejor.2005.06.076.
[25]	M. I. Zelikin and V. F. Borisov, Regimes with increasingly more frequent switchings in optimal control problems, Tr. Mat. Inst. Akad. Nauk SSSR, 197 (1991), 85-167.
[26]	M. I. Zelikin and V. F. Borisov, Theory of Chattering Control: With Applications to Astronautics, Robotics, Economics, and Engineering, Springer Science & Business Media, 2012. doi: 10.1007/978-1-4612-2702-1.