doi: 10.3934/jimo.2022084
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

An approach to solve local and global optimization problems based on exact objective filled penalty functions

1. 

School of Management, Fudan University, Shanghai, 200433, China

2. 

School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

*Corresponding author: Jiahui Tang

Received  January 2022 Revised  April 2022 Early access May 2022

Fund Project: This work is supported by National Natural Science Foundation of China(No.72072036)

In this work, an exact objective penalty function and an exact objective filled penalty function are proposed to solve constrained optimization problems. There are two main innovations of these two functions: using the exact objective penalty function to find a locally optimal point; a better locally optimal point than the current one can be found by exact objective filled penalty function. A local search method and a global search method for constrained optimization problems are proposed. We can use this new global search method to compute an approximately globally optimal point for constrained optimization problems. The convergence of the sequences obtained by the new algorithms are also analyzed respectively. Finally, the rationality of these two search methods are illustrated by numerical experiments.

Citation: Jiahui Tang, Yifan Xu, Wei Wang. An approach to solve local and global optimization problems based on exact objective filled penalty functions. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022084
References:
[1]

T. Antczak, Exactness of penalization for exact minimax penalty function method in nonconvex programming, Appl. Math. Mech. -Engl. Ed., 36 (2015), 541-556.  doi: 10.1007/s10483-015-1929-9.

[2]

N. Echebest and M. D. Sanchez, M. L. Schuverdt, convergence results of an augmented Lagrangian method using the exponential penalty function, J. Optim. Theory Appl., 168 (2016), 92-108.  doi: 10.1007/s10957-015-0735-7.

[3]

J. P. EvansF. J. Gould and J. W. Tolle, Exact penalty functions in nonlinear programming, Mathematieal Programming, 4 (1973), 72-97.  doi: 10.1007/BF01584647.

[4]

R. P. Ge and and Y. F. Qin, A class of filled functions for finding a global minimizer of a function of several variables, Journal of Optimization Theory and Applications, 54 (1987), 241-252.  doi: 10.1007/BF00939433.

[5]

Q. Hu and W. Wang, A filled function method based on filter for global optimization with box constrained, Operations Research Transactions, 20 (2016), 1-11.  doi: 10.15960/j.cnki.issn.1007-6093.2016.03.006.

[6]

L. Y. LiZ. Y. Wu and Q. Long, A new objective penalty function approach for solving constrained minimax problems, J. Oper. Res. Soc. China, 2 (2014), 93-108.  doi: 10.1007/s40305-014-0041-3.

[7]

S. J. LianA. H. Du and J. H. Tang, A new class of simple smooth exact penalty functions for quality constrained optimization problems, Operations Research Transactions, 21 (2017), 33-43.  doi: 10.15960/j.cnki.issn.1007-6093.2017.01.004.

[8]

S. J. Lian, Smoothing approximation to $l_{1}$ exact penalty function for inequality constrained optimization, Applied Mathematics and Computation, 219 (2012), 3113-3121.  doi: 10.1016/j.amc.2012.09.042.

[9]

S. J. LianJ. H. Tang and A. H. Du, A new class of penalty functions for quality constrained smooth optimization, Operations Research Transactions, 22 (2018), 108-116.  doi: 10.15960/j.cnki.issn.1007-6093.2018.04.010.

[10]

S. J. Lian and Y. Q. Duan, Smoothing of the lower-order exact penalty function for inquality constrained optimization, Journal of Inequalities and Applications, 2016 (2016), 1-12.  doi: 10.1186/s13660-016-1126-9.

[11]

S. J. Lian and L. S. Zhang, A simple smooth exact penalty function for smooth optimization problem, J. Syst. Sci. Complex., 25 (2012), 521-528.  doi: 10.1007/s11424-012-9226-1.

[12]

S. J. LianB. Z. Liu and L. S. Zhang, A family of penalty functions approximate to $l_{1}$ exact penalty function, Acta Mathmaticae Applicatae Sinica, 30 (2007), 961-971.  doi: 10.3321/j.issn:0254-3079.2007.06.001.

[13]

S. Lucidi and V. Piccialli, New class of globally convexized filled functions for global optimization, J. Glob. Optim., 24 (2002), 219-236.  doi: 10.1023/A:1020243720794.

[14]

Z. Q. MengC. Y. DangM. JiangX. S. Xu and R. Shen, Exaceness and algorithm of an objective penalty function, J. Glob. Optim., 56 (2013), 691-711.  doi: 10.1007/s10898-012-9900-9.

[15]

Z. Q. MengR. ShenC. Y. Dang and M. Jiang, A barrier objective penalty function algorithm for mathematical programming, Journal of System and Mathematical Science (Chinese Series), 36 (2016), 75-92. 

[16]

Z. Q. MengR. ShenC. Y. Dang and M. Jiang, Augmented Lagrangian objective penalty function, Numer. Func. Anal. Optim., 36 (2015), 1471-1492.  doi: 10.1080/01630563.2015.1070864.

[17]

Z. Q. MengQ. Y. HuC. Y. Dang and X. Q. Yang, An objective penalty function method for nonlinear programming, Appl. Math. Lett., 17 (2004), 683-689.  doi: 10.1016/S0893-9659(04)90105-X.

[18]

G. Di PilloS. Lucidi and F. Rinaldi, An approach to constrained global optimization based on exact penalty functions, J. Glob. Optim., 54 (2012), 251-260.  doi: 10.1007/s10898-010-9582-0.

[19]

G. Di PilloS. Lucidi and F. Rinaldi, A derivative-free algorithm for constrained global optimization based on exact penalty functions, J. Optim. Theory Appl., 164 (2015), 862-882.  doi: 10.1007/s10957-013-0487-1.

[20]

J. H. TangW. Wang and Y. F. Xu, Two classes of smooth objective penalty functions for constrained problem, Numerical Functional Analysis and Optimization, 40 (2019), 341-364.  doi: 10.1080/01630563.2018.1554586.

[21]

J. H. Tang, W. Wang and Y. F. Xu, Lower-order smoothed objective penalty functions based on filling properties for constrained optimization problems, Optimization. doi: 10.1080/02331934.2020.1818746.

[22]

W. WangY. J. Yang and L. S. Zhang, Unification of filled function and tunnelling function in global optimization, Acta Mathematicae Applicatae Sinica (English Series), 23 (2007), 59-66.  doi: 10.1007/s10255-006-0349-9.

[23]

W. WangQ. Yuan and J. H. Tang, Dimensionality reduction algorithm for global optimization problems with closed box constraints, Mathematical Modeling and Its Applications, 8 (2019), 38-43.  doi: 10.3969/j.issn.2095-3070.2019.01.005.

[24]

W. X. Wang, Y. L. Shang and L. S. Zhang, A new T-F function theory and algorithm for nonlinear integer programming, The First International Symposium on Optimization and Systems Biology(OSB'07), (2007), 382-390.

[25]

Y. ZhengZ. Q. Meng and R. Shen, An M-Objective penalty function algorithm under big penalty parameters, J. Syst. Sci. Complex., 2 (2016), 455-471.  doi: 10.1007/s11424-015-3204-3.

[26]

W. I. Zangwill, Non-linear programming via penalty functions, Manage. Sci., 13 (1967), 44-358.  doi: 10.1287/mnsc.13.5.344.

show all references

References:
[1]

T. Antczak, Exactness of penalization for exact minimax penalty function method in nonconvex programming, Appl. Math. Mech. -Engl. Ed., 36 (2015), 541-556.  doi: 10.1007/s10483-015-1929-9.

[2]

N. Echebest and M. D. Sanchez, M. L. Schuverdt, convergence results of an augmented Lagrangian method using the exponential penalty function, J. Optim. Theory Appl., 168 (2016), 92-108.  doi: 10.1007/s10957-015-0735-7.

[3]

J. P. EvansF. J. Gould and J. W. Tolle, Exact penalty functions in nonlinear programming, Mathematieal Programming, 4 (1973), 72-97.  doi: 10.1007/BF01584647.

[4]

R. P. Ge and and Y. F. Qin, A class of filled functions for finding a global minimizer of a function of several variables, Journal of Optimization Theory and Applications, 54 (1987), 241-252.  doi: 10.1007/BF00939433.

[5]

Q. Hu and W. Wang, A filled function method based on filter for global optimization with box constrained, Operations Research Transactions, 20 (2016), 1-11.  doi: 10.15960/j.cnki.issn.1007-6093.2016.03.006.

[6]

L. Y. LiZ. Y. Wu and Q. Long, A new objective penalty function approach for solving constrained minimax problems, J. Oper. Res. Soc. China, 2 (2014), 93-108.  doi: 10.1007/s40305-014-0041-3.

[7]

S. J. LianA. H. Du and J. H. Tang, A new class of simple smooth exact penalty functions for quality constrained optimization problems, Operations Research Transactions, 21 (2017), 33-43.  doi: 10.15960/j.cnki.issn.1007-6093.2017.01.004.

[8]

S. J. Lian, Smoothing approximation to $l_{1}$ exact penalty function for inequality constrained optimization, Applied Mathematics and Computation, 219 (2012), 3113-3121.  doi: 10.1016/j.amc.2012.09.042.

[9]

S. J. LianJ. H. Tang and A. H. Du, A new class of penalty functions for quality constrained smooth optimization, Operations Research Transactions, 22 (2018), 108-116.  doi: 10.15960/j.cnki.issn.1007-6093.2018.04.010.

[10]

S. J. Lian and Y. Q. Duan, Smoothing of the lower-order exact penalty function for inquality constrained optimization, Journal of Inequalities and Applications, 2016 (2016), 1-12.  doi: 10.1186/s13660-016-1126-9.

[11]

S. J. Lian and L. S. Zhang, A simple smooth exact penalty function for smooth optimization problem, J. Syst. Sci. Complex., 25 (2012), 521-528.  doi: 10.1007/s11424-012-9226-1.

[12]

S. J. LianB. Z. Liu and L. S. Zhang, A family of penalty functions approximate to $l_{1}$ exact penalty function, Acta Mathmaticae Applicatae Sinica, 30 (2007), 961-971.  doi: 10.3321/j.issn:0254-3079.2007.06.001.

[13]

S. Lucidi and V. Piccialli, New class of globally convexized filled functions for global optimization, J. Glob. Optim., 24 (2002), 219-236.  doi: 10.1023/A:1020243720794.

[14]

Z. Q. MengC. Y. DangM. JiangX. S. Xu and R. Shen, Exaceness and algorithm of an objective penalty function, J. Glob. Optim., 56 (2013), 691-711.  doi: 10.1007/s10898-012-9900-9.

[15]

Z. Q. MengR. ShenC. Y. Dang and M. Jiang, A barrier objective penalty function algorithm for mathematical programming, Journal of System and Mathematical Science (Chinese Series), 36 (2016), 75-92. 

[16]

Z. Q. MengR. ShenC. Y. Dang and M. Jiang, Augmented Lagrangian objective penalty function, Numer. Func. Anal. Optim., 36 (2015), 1471-1492.  doi: 10.1080/01630563.2015.1070864.

[17]

Z. Q. MengQ. Y. HuC. Y. Dang and X. Q. Yang, An objective penalty function method for nonlinear programming, Appl. Math. Lett., 17 (2004), 683-689.  doi: 10.1016/S0893-9659(04)90105-X.

[18]

G. Di PilloS. Lucidi and F. Rinaldi, An approach to constrained global optimization based on exact penalty functions, J. Glob. Optim., 54 (2012), 251-260.  doi: 10.1007/s10898-010-9582-0.

[19]

G. Di PilloS. Lucidi and F. Rinaldi, A derivative-free algorithm for constrained global optimization based on exact penalty functions, J. Optim. Theory Appl., 164 (2015), 862-882.  doi: 10.1007/s10957-013-0487-1.

[20]

J. H. TangW. Wang and Y. F. Xu, Two classes of smooth objective penalty functions for constrained problem, Numerical Functional Analysis and Optimization, 40 (2019), 341-364.  doi: 10.1080/01630563.2018.1554586.

[21]

J. H. Tang, W. Wang and Y. F. Xu, Lower-order smoothed objective penalty functions based on filling properties for constrained optimization problems, Optimization. doi: 10.1080/02331934.2020.1818746.

[22]

W. WangY. J. Yang and L. S. Zhang, Unification of filled function and tunnelling function in global optimization, Acta Mathematicae Applicatae Sinica (English Series), 23 (2007), 59-66.  doi: 10.1007/s10255-006-0349-9.

[23]

W. WangQ. Yuan and J. H. Tang, Dimensionality reduction algorithm for global optimization problems with closed box constraints, Mathematical Modeling and Its Applications, 8 (2019), 38-43.  doi: 10.3969/j.issn.2095-3070.2019.01.005.

[24]

W. X. Wang, Y. L. Shang and L. S. Zhang, A new T-F function theory and algorithm for nonlinear integer programming, The First International Symposium on Optimization and Systems Biology(OSB'07), (2007), 382-390.

[25]

Y. ZhengZ. Q. Meng and R. Shen, An M-Objective penalty function algorithm under big penalty parameters, J. Syst. Sci. Complex., 2 (2016), 455-471.  doi: 10.1007/s11424-015-3204-3.

[26]

W. I. Zangwill, Non-linear programming via penalty functions, Manage. Sci., 13 (1967), 44-358.  doi: 10.1287/mnsc.13.5.344.

Table 1.  Numerical Results of the EOP Algorithm
$ k $ $ \sigma_{k} $ $ \varepsilon_{k} $ $ M_{k} $ $ x_{k} $ $ f(x_{k}) $
1 $ 10 $ 0.01 -25 $ (0.5045, -1.21, -1.12, -1.99)^{T} $
2 $ 50 $ 0.001 -25 $ ( 0.7231, -1.4788, 2.6252, -5.0909 )^{T} $ $ -44.5773 $
3 $ 500 $ 0.0001 -25 $ ( 0.7273, -1.4895, 2.6217, -5.1149 )^{T} $ $ -44.3926 $
4 $ 5000 $ $ 1e-05 $ -25 $ ( 0.7300, -1.4963, 2.6195, -5.1301 )^{T} $ $ -44.2751 $
5 $ 50000 $ $ 1e-06 $ -25 $ ( 0.7306, -1.4978, 2.6190, -5.1333 )^{T} $ $ -44.2502 $
6 $ 500000 $ $ 1e-07 $ -25 $ ( 0.7309, -1.4987, 2.6187, -5.1355 )^{T} $ $ -44.2331 $
$ k $ $ \sigma_{k} $ $ \varepsilon_{k} $ $ M_{k} $ $ x_{k} $ $ f(x_{k}) $
1 $ 10 $ 0.01 -25 $ (0.5045, -1.21, -1.12, -1.99)^{T} $
2 $ 50 $ 0.001 -25 $ ( 0.7231, -1.4788, 2.6252, -5.0909 )^{T} $ $ -44.5773 $
3 $ 500 $ 0.0001 -25 $ ( 0.7273, -1.4895, 2.6217, -5.1149 )^{T} $ $ -44.3926 $
4 $ 5000 $ $ 1e-05 $ -25 $ ( 0.7300, -1.4963, 2.6195, -5.1301 )^{T} $ $ -44.2751 $
5 $ 50000 $ $ 1e-06 $ -25 $ ( 0.7306, -1.4978, 2.6190, -5.1333 )^{T} $ $ -44.2502 $
6 $ 500000 $ $ 1e-07 $ -25 $ ( 0.7309, -1.4987, 2.6187, -5.1355 )^{T} $ $ -44.2331 $
Table 2.  Numerical Results of the EOP Algorithm and EOFP Algorithm
$ n $ 10 15
local optimal point of the EOP Algorithm (-0.0074, -0.0005, -0.0020, -0.0000, 0.0439, 0.0045, -0.0016, 0.0035, -0.0020, 0.0014)T (0.0000, 0.0000, -0.0000, 0.0000, -0.0000, 1.0001, 0.9974, 0.0000, -0.0000, 0.0000, -0.0000, -0.0000, 0.0000, 0.0000, -0.0000, )T
globla optimal point of the EOFP Algorithm (0.0007, 0.0003, 0.0003, -0.0000, 0.0018, 0.0008, 0.0006, 0.0004, 0.0003, 0.0002)T (0.1986, 0.3573, -0.0269, 0.1132, -0.0393, -0.3979, -0.2196, 0.0445, -0.0046, 0.4476, -0.0678, -0.1024, 0.0134, 0.0345, -0.3531)T
local optimal value of the EOP Algorithm $ -0.97385 $ $ 0.89497 $
gobal optimal value of the EOFP Algorithm $ -0.99993 $ $ -1.50000 $
$ n $ 10 15
local optimal point of the EOP Algorithm (-0.0074, -0.0005, -0.0020, -0.0000, 0.0439, 0.0045, -0.0016, 0.0035, -0.0020, 0.0014)T (0.0000, 0.0000, -0.0000, 0.0000, -0.0000, 1.0001, 0.9974, 0.0000, -0.0000, 0.0000, -0.0000, -0.0000, 0.0000, 0.0000, -0.0000, )T
globla optimal point of the EOFP Algorithm (0.0007, 0.0003, 0.0003, -0.0000, 0.0018, 0.0008, 0.0006, 0.0004, 0.0003, 0.0002)T (0.1986, 0.3573, -0.0269, 0.1132, -0.0393, -0.3979, -0.2196, 0.0445, -0.0046, 0.4476, -0.0678, -0.1024, 0.0134, 0.0345, -0.3531)T
local optimal value of the EOP Algorithm $ -0.97385 $ $ 0.89497 $
gobal optimal value of the EOFP Algorithm $ -0.99993 $ $ -1.50000 $
[1]

Jiawei Chen, Shengjie Li, Jen-Chih Yao. Vector-valued separation functions and constrained vector optimization problems: optimality and saddle points. Journal of Industrial and Management Optimization, 2020, 16 (2) : 707-724. doi: 10.3934/jimo.2018174

[2]

Ahmet Sahiner, Gulden Kapusuz, Nurullah Yilmaz. A new smoothing approach to exact penalty functions for inequality constrained optimization problems. Numerical Algebra, Control and Optimization, 2016, 6 (2) : 161-173. doi: 10.3934/naco.2016006

[3]

Liuyang Yuan, Zhongping Wan, Qiuhua Tang. A criterion for an approximation global optimal solution based on the filled functions. Journal of Industrial and Management Optimization, 2016, 12 (1) : 375-387. doi: 10.3934/jimo.2016.12.375

[4]

Benedetto Piccoli. Optimal syntheses for state constrained problems with application to optimization of cancer therapies. Mathematical Control and Related Fields, 2012, 2 (4) : 383-398. doi: 10.3934/mcrf.2012.2.383

[5]

Eleonora Catsigeras, Yun Zhao. Observable optimal state points of subadditive potentials. Discrete and Continuous Dynamical Systems, 2013, 33 (4) : 1375-1388. doi: 10.3934/dcds.2013.33.1375

[6]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. A new exact penalty function method for continuous inequality constrained optimization problems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 895-910. doi: 10.3934/jimo.2010.6.895

[7]

Ling Yun Wang, Wei Hua Gui, Kok Lay Teo, Ryan Loxton, Chun Hua Yang. Time delayed optimal control problems with multiple characteristic time points: Computation and industrial applications. Journal of Industrial and Management Optimization, 2009, 5 (4) : 705-718. doi: 10.3934/jimo.2009.5.705

[8]

Kazimierz Malanowski, Helmut Maurer. Sensitivity analysis for state constrained optimal control problems. Discrete and Continuous Dynamical Systems, 1998, 4 (2) : 241-272. doi: 10.3934/dcds.1998.4.241

[9]

René Henrion. Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 655-668. doi: 10.3934/naco.2012.2.655

[10]

X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287

[11]

Bao Qing Hu, Song Wang. A novel approach in uncertain programming part II: a class of constrained nonlinear programming problems with interval objective functions. Journal of Industrial and Management Optimization, 2006, 2 (4) : 373-385. doi: 10.3934/jimo.2006.2.373

[12]

Bin Li, Kok Lay Teo, Cheng-Chew Lim, Guang Ren Duan. An optimal PID controller design for nonlinear constrained optimal control problems. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1101-1117. doi: 10.3934/dcdsb.2011.16.1101

[13]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391

[14]

Enrique Fernández-Cara, Irene Marín-Gayte. Theoretical and numerical results for some bi-objective optimal control problems. Communications on Pure and Applied Analysis, 2020, 19 (4) : 2101-2126. doi: 10.3934/cpaa.2020093

[15]

Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial and Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181

[16]

P. Candito, S. A. Marano, D. Motreanu. Critical points for a class of nondifferentiable functions and applications. Discrete and Continuous Dynamical Systems, 2005, 13 (1) : 175-194. doi: 10.3934/dcds.2005.13.175

[17]

Piotr Fijałkowski. A global inversion theorem for functions with singular points. Discrete and Continuous Dynamical Systems - B, 2018, 23 (1) : 173-180. doi: 10.3934/dcdsb.2018011

[18]

Qian Liu, Xinmin Yang, Heung Wing Joseph Lee. On saddle points of a class of augmented lagrangian functions. Journal of Industrial and Management Optimization, 2007, 3 (4) : 693-700. doi: 10.3934/jimo.2007.3.693

[19]

Sebastian Albrecht, Marion Leibold, Michael Ulbrich. A bilevel optimization approach to obtain optimal cost functions for human arm movements. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 105-127. doi: 10.3934/naco.2012.2.105

[20]

Piernicola Bettiol. State constrained $L^\infty$ optimal control problems interpreted as differential games. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 3989-4017. doi: 10.3934/dcds.2015.35.3989

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (63)
  • HTML views (33)
  • Cited by (0)

Other articles
by authors

[Back to Top]