# American Institute of Mathematical Sciences

March  2021, 11(1): 45-61. doi: 10.3934/naco.2020014

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

Received  June 2019 Revised  August 2019 Published  February 2020

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.

Citation: M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
##### References:

show all references

##### References:
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
The AGD with rectangular search regions approaching the minimum point $x^{*}$ from the initial point $x(0)$
Performance profiles based on the CPU time
Performance profiles based on the number of iterations
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}$
 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}$
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}$
 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}$
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}$
 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}$
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}$
 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}$
 [1] Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467 [2] Editorial Office. Retraction: Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin and Zhike Han, Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-957. doi: 10.3934/dcdss.2019064 [3] Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081 [4] Zaizheng Li, Qidi Zhang. Sub-solutions and a point-wise Hopf's lemma for fractional $p$-Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020293 [5] Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117 [6] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [7] Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374 [8] Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120 [9] José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271 [10] Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006 [11] Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378 [12] Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115 [13] Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331 [14] Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 [15] Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049 [16] Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106 [17] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [18] Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044 [19] Álvaro Castañeda, Pablo González, Gonzalo Robledo. Topological Equivalence of nonautonomous difference equations with a family of dichotomies on the half line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020278 [20] Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020395

Impact Factor: