American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Note on "Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method"
  • JIMO Home
  • This Issue
  • Next Article
    Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria
July  2012, 8(3): 705-726. doi: 10.3934/jimo.2012.8.705

On an exact penalty function method for semi-infinite programming problems

Cheng Ma 1, , Xun Li 1, , Ka-Fai Cedric Yiu 1, , Yongjian Yang 2, and  Liansheng Zhang 3,

1. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China, China
2. 

Department of Mathematics, Shanghai University, 99, Shangda Road, Shanghai, China
3. 

Department of Mathematics, Shanghai University, 99, Shangda Road, 200444, Shanghai

Received  April 2011 Revised  February 2012 Published  June 2012

In this paper, we study a new exact and smooth penalty function for semi-infinite programming problems with continuous inequality constraints. Through this exact penalty function, we can transform a semi-infinite programming problem into an unconstrained optimization problem. We find that, under some reasonable conditions when the penalty parameter is sufficiently large, the local minimizer of this penalty function is the local minimizer of the primal problem. Moreover, under some mild assumptions, the local exactness property is explored. The numerical results demonstrate that it is an effective and promising approach for solving constrained semi-infinite programming problems.
Keywords: smooth and exact penalty function, nonsmooth optimization, Constrained semi-infinite programming problem, extended Managasarian-Fromovitz constraint qualification..
Mathematics Subject Classification: Primary: 90-08; Secondary: 90C34, 49M3.
Citation: Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
References:
[1]

J. V. Burke, An exact penalization viewpoint of constrained optimization, SIAM J. Control and Optimization, 29 (1991), 968-998. doi: 10.1137/0329054.

[2]

H. Cheng and B. Özçam, A discretization based smoothing method for solving semi-infinite variational inequalities, Journal of Industrial and Management Optimization, 1 (2005), 219-233.

[3]

A. R. Conn and N. I. M. Gould, An exact penalty function for semi-infinite programming, Mathematical Programming, 37 (1987), 19-40. doi: 10.1007/BF02591681.

[4]

R. DeVore and G. Lorentz, "Constructive Approximation," Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 303, Springer-Verlag, Berlin, 1993.

[5]

Z. G. Feng, K. L. Teo and Y. Zhao, Branch and bound method for sensor scheduling in discrete time, Journal of Industrial and Management Optimization, 1 (2005), 499-512.

[6]

P. Gribik, A central-cutting-plane algorithm for semi-infinite programming problems, in "Semi-Infinite Programming" (ed. R. Hettich) (Proc. Workshop, Bad Honnef, 1978), Lecture Notes in Control and Information Sci., 15, Springer, Berlin-New York, (1979), 66-82.

[7]

R. Hettich, An implementation of a discretization method for semi-infinite programming, Mathematical Programming, 34 (1986), 354-361. doi: 10.1007/BF01582235.

[8]

R. Hettich and G. Gramlich, A note on an implementation of a method for quadratic semi-infinite programming, Mathematical Programming, 46 (1990), 249-254. doi: 10.1007/BF01585742.

[9]

W. Huyer and A. Neumair, A new exact penalty function, SIAM J. Optimization, 13 (2003), 1141-1159. doi: 10.1137/S1052623401390537.

[10]

B. Jerez, General equilibrium with asymmetric information: A dual approach, Journal of Economic Theory, in press.

[11]

H. T. Jongen, F. Twilt and G.-W. Weber, Semi-infinite optimization: Structure and stability of the feasible set, Journal of Optimization Theory and Application, 72 (1992), 529-552. doi: 10.1007/BF00939841.

[12]

B. Li, C. J. Yu, K. L. Teo and G. R. Duan, An exact penalty function method for continuous inequality constrained optimal control problem, Journal of Optimization Theory and Applications, published online, 2011.

[13]

D.-H. Li, L. Qi, J. Tam and S.-Y. Wu, A smoothing Newton method for semi-infinite programming, Journal of Global Optimization, 30 (2004), 169-194. doi: 10.1007/s10898-004-8266-z.

[14]

C. Ling, Q. Ni, L. Qi and S.-Y. Wu, A new smoothing Newton-type algorithm for semi-infinite programming, Journal of Global Optimization, 47 (2010), 133-159. doi: 10.1007/s10898-009-9462-7.

[15]

Y. Liu and K. L. Teo, An adaptive dual parametrization algorithm for quadratic semi-infinite programming problems, Journal of Global Optimization, 24 (2002), 205-217. doi: 10.1023/A:1020234019886.

[16]

Y. Liu, K. L. Teo and S.-Y. Wu, An new quadratic semi-infinite programming algorithm based on dual parameterization, Journal of Global Optimization, 29 (2005), 401-413. doi: 10.1023/B:JOGO.0000047910.80739.95.

[17]

C. Ma and C. Y. Wang, A nonsmooth Levenberg-Marquardt method for solving semi-infinite programming problems, Journal of Computational and Applied Mathematics, 230 (2009), 633-642. doi: 10.1016/j.cam.2009.01.004.

[18]

Q. Ni, C. Ling, L. Qi and K. L. Teo, A truncated projected Newton-type algorithm for large-scale semi-infinite programming, SIAM J. Optimization, 16 (2006), 1137-1154. doi: 10.1137/040619867.

[19]

J.-S. Pang, Error bound in mathematical programming, Mathematical Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.

[20]

C. Price and I. Coope, Numerical experienments in semi-infinite programming, Computational Optimization and Application, 6 (1996), 169-189.

[21]

L. Qi, S.-Y. Wu and G. L. Zhou, Semismooth newton methods for solving semi-infinite programming problems, Journal of Global Optimization, 27 (2003), 215-232. doi: 10.1023/A:1024814401713.

[22]

R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems, Journal of Optimization Theory and Application, 71 (1991), 85-103. doi: 10.1007/BF00940041.

[23]

R. T. Rockafellar and R. J.-B. Wets, "Variational Analysis," Grundlehren der Math. Wissenschaften, 317, Springer-Verlag, Berlin, 1998.

[24]

G. Still, Discretization in semi-infinite programming: The rate of convergence, Mathematical Programming, 91 (2001), 53-69.

[25]

H. Voigt, Semi-infinite transportation problems, Zeitschrift für Analysis und ihre Anwendungen, 17 (1998), 729-741.

[26]

J.-P. Z. Wang and B. G. Lindsay, A penalized nonparametric maximum likelihood approach to species richness estimation, Journal of the American Statistical Association, 100 (2005), 942-959. doi: 10.1198/016214504000002005.

[27]

G. A. Watson, Globally convergent methods for semi-infinite programming, BIT, 21 (1981), 362-373. doi: 10.1007/BF01941472.

[28]

G. W. Weber and Ö. Uǧur, Optimization and dynamics of gene-environment networks with intervals, Journal of Industrial and Management Optimization, 3 (2007), 357-379.

[29]

S.-Y. Wu, S.-C. Fang and C.-J. Lin, Solving quadratic semi-infinite programming problems by using relaxed cutting-plane scheme, Journal of Computational and Applied Mathematics, 129 (2001), 89-104. doi: 10.1016/S0377-0427(00)00544-6.

[30]

Z. L. Wu and J. J. Ye, First-order and second-order conditions for error bounds, SIAM J. Optimization, 14 (2003), 621-645. doi: 10.1137/S1052623402412982.

[31]

K. F. C. Yiu, X. Q. Yang, S. Nordholm and K. L. Teo, Near-field broadband beamformer design via multidimensional semi-infinite linear programming techniques, IEEE Transactions on Speech and Audio Processing, 11 (2003), 725-732. doi: 10.1109/TSA.2003.815527.

[32]

C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial and Management Optimization, 6 (2010), 895-910.

[33]

K. Zhang and S. Wang, Convergence property of an interior penalty approach to pricing American option, Journal of Industrial and Management Optimization, 7 (2011), 435-447.

[34]

H. J. Zhou, K. F. C. Yiu and L. K. Li, Evaluating American put options on zero-coupon bonds by a penalty method, Journal of Computational and Applied Mathematics, 235 (2011), 3921-3931. doi: 10.1016/j.cam.2011.01.038.

show all references

References:
[1]

J. V. Burke, An exact penalization viewpoint of constrained optimization, SIAM J. Control and Optimization, 29 (1991), 968-998. doi: 10.1137/0329054.

[2]

H. Cheng and B. Özçam, A discretization based smoothing method for solving semi-infinite variational inequalities, Journal of Industrial and Management Optimization, 1 (2005), 219-233.

[3]

A. R. Conn and N. I. M. Gould, An exact penalty function for semi-infinite programming, Mathematical Programming, 37 (1987), 19-40. doi: 10.1007/BF02591681.

[4]

R. DeVore and G. Lorentz, "Constructive Approximation," Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 303, Springer-Verlag, Berlin, 1993.

[5]

Z. G. Feng, K. L. Teo and Y. Zhao, Branch and bound method for sensor scheduling in discrete time, Journal of Industrial and Management Optimization, 1 (2005), 499-512.

[6]

P. Gribik, A central-cutting-plane algorithm for semi-infinite programming problems, in "Semi-Infinite Programming" (ed. R. Hettich) (Proc. Workshop, Bad Honnef, 1978), Lecture Notes in Control and Information Sci., 15, Springer, Berlin-New York, (1979), 66-82.

[7]

R. Hettich, An implementation of a discretization method for semi-infinite programming, Mathematical Programming, 34 (1986), 354-361. doi: 10.1007/BF01582235.

[8]

R. Hettich and G. Gramlich, A note on an implementation of a method for quadratic semi-infinite programming, Mathematical Programming, 46 (1990), 249-254. doi: 10.1007/BF01585742.

[9]

W. Huyer and A. Neumair, A new exact penalty function, SIAM J. Optimization, 13 (2003), 1141-1159. doi: 10.1137/S1052623401390537.

[10]

B. Jerez, General equilibrium with asymmetric information: A dual approach, Journal of Economic Theory, in press.

[11]

H. T. Jongen, F. Twilt and G.-W. Weber, Semi-infinite optimization: Structure and stability of the feasible set, Journal of Optimization Theory and Application, 72 (1992), 529-552. doi: 10.1007/BF00939841.

[12]

B. Li, C. J. Yu, K. L. Teo and G. R. Duan, An exact penalty function method for continuous inequality constrained optimal control problem, Journal of Optimization Theory and Applications, published online, 2011.

[13]

D.-H. Li, L. Qi, J. Tam and S.-Y. Wu, A smoothing Newton method for semi-infinite programming, Journal of Global Optimization, 30 (2004), 169-194. doi: 10.1007/s10898-004-8266-z.

[14]

C. Ling, Q. Ni, L. Qi and S.-Y. Wu, A new smoothing Newton-type algorithm for semi-infinite programming, Journal of Global Optimization, 47 (2010), 133-159. doi: 10.1007/s10898-009-9462-7.

[15]

Y. Liu and K. L. Teo, An adaptive dual parametrization algorithm for quadratic semi-infinite programming problems, Journal of Global Optimization, 24 (2002), 205-217. doi: 10.1023/A:1020234019886.

[16]

Y. Liu, K. L. Teo and S.-Y. Wu, An new quadratic semi-infinite programming algorithm based on dual parameterization, Journal of Global Optimization, 29 (2005), 401-413. doi: 10.1023/B:JOGO.0000047910.80739.95.

[17]

C. Ma and C. Y. Wang, A nonsmooth Levenberg-Marquardt method for solving semi-infinite programming problems, Journal of Computational and Applied Mathematics, 230 (2009), 633-642. doi: 10.1016/j.cam.2009.01.004.

[18]

Q. Ni, C. Ling, L. Qi and K. L. Teo, A truncated projected Newton-type algorithm for large-scale semi-infinite programming, SIAM J. Optimization, 16 (2006), 1137-1154. doi: 10.1137/040619867.

[19]

J.-S. Pang, Error bound in mathematical programming, Mathematical Programming, 79 (1997), 299-332. doi: 10.1007/BF02614322.

[20]

C. Price and I. Coope, Numerical experienments in semi-infinite programming, Computational Optimization and Application, 6 (1996), 169-189.

[21]

L. Qi, S.-Y. Wu and G. L. Zhou, Semismooth newton methods for solving semi-infinite programming problems, Journal of Global Optimization, 27 (2003), 215-232. doi: 10.1023/A:1024814401713.

[22]

R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems, Journal of Optimization Theory and Application, 71 (1991), 85-103. doi: 10.1007/BF00940041.

[23]

R. T. Rockafellar and R. J.-B. Wets, "Variational Analysis," Grundlehren der Math. Wissenschaften, 317, Springer-Verlag, Berlin, 1998.

[24]

G. Still, Discretization in semi-infinite programming: The rate of convergence, Mathematical Programming, 91 (2001), 53-69.

[25]

H. Voigt, Semi-infinite transportation problems, Zeitschrift für Analysis und ihre Anwendungen, 17 (1998), 729-741.

[26]

J.-P. Z. Wang and B. G. Lindsay, A penalized nonparametric maximum likelihood approach to species richness estimation, Journal of the American Statistical Association, 100 (2005), 942-959. doi: 10.1198/016214504000002005.

[27]

G. A. Watson, Globally convergent methods for semi-infinite programming, BIT, 21 (1981), 362-373. doi: 10.1007/BF01941472.

[28]

G. W. Weber and Ö. Uǧur, Optimization and dynamics of gene-environment networks with intervals, Journal of Industrial and Management Optimization, 3 (2007), 357-379.

[29]

S.-Y. Wu, S.-C. Fang and C.-J. Lin, Solving quadratic semi-infinite programming problems by using relaxed cutting-plane scheme, Journal of Computational and Applied Mathematics, 129 (2001), 89-104. doi: 10.1016/S0377-0427(00)00544-6.

[30]

Z. L. Wu and J. J. Ye, First-order and second-order conditions for error bounds, SIAM J. Optimization, 14 (2003), 621-645. doi: 10.1137/S1052623402412982.

[31]

K. F. C. Yiu, X. Q. Yang, S. Nordholm and K. L. Teo, Near-field broadband beamformer design via multidimensional semi-infinite linear programming techniques, IEEE Transactions on Speech and Audio Processing, 11 (2003), 725-732. doi: 10.1109/TSA.2003.815527.

[32]

C. J. Yu, K. L. Teo, L. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems, Journal of Industrial and Management Optimization, 6 (2010), 895-910.

[33]

K. Zhang and S. Wang, Convergence property of an interior penalty approach to pricing American option, Journal of Industrial and Management Optimization, 7 (2011), 435-447.

[34]

H. J. Zhou, K. F. C. Yiu and L. K. Li, Evaluating American put options on zero-coupon bonds by a penalty method, Journal of Computational and Applied Mathematics, 235 (2011), 3921-3931. doi: 10.1016/j.cam.2011.01.038.

[1]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485
[2]

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
[3]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[4]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1133-1144. doi: 10.3934/jimo.2021012
[5]

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
[6]

Zhi Guo Feng, Kok Lay Teo, Volker Rehbock. A smoothing approach for semi-infinite programming with projected Newton-type algorithm. Journal of Industrial and Management Optimization, 2009, 5 (1) : 141-151. doi: 10.3934/jimo.2009.5.141
[7]

Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial and Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851
[8]

Xiaodong Fan, Tian Qin. Stability analysis for generalized semi-infinite optimization problems under functional perturbations. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1221-1233. doi: 10.3934/jimo.2018201
[9]

Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022
[10]

Roman Chapko, B. Tomas Johansson. An alternating boundary integral based method for a Cauchy problem for the Laplace equation in semi-infinite regions. Inverse Problems and Imaging, 2008, 2 (3) : 317-333. doi: 10.3934/ipi.2008.2.317
[11]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial and Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[12]

Jinchuan Zhou, Naihua Xiu, Jein-Shan Chen. Solution properties and error bounds for semi-infinite complementarity problems. Journal of Industrial and Management Optimization, 2013, 9 (1) : 99-115. doi: 10.3934/jimo.2013.9.99
[13]

Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[14]

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
[15]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[16]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[17]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial and Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319
[18]

Yibing Lv, Zhongping Wan. Linear bilevel multiobjective optimization problem: Penalty approach. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1213-1223. doi: 10.3934/jimo.2018092
[19]

Azhar Ali Zafar, Khurram Shabbir, Asim Naseem, Muhammad Waqas Ashraf. MHD natural convection boundary-layer flow over a semi-infinite heated plate with arbitrary inclination. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 1007-1015. doi: 10.3934/dcdss.2020059
[20]

Rafael del Rio, Mikhail Kudryavtsev, Luis O. Silva. Inverse problems for Jacobi operators III: Mass-spring perturbations of semi-infinite systems. Inverse Problems and Imaging, 2012, 6 (4) : 599-621. doi: 10.3934/ipi.2012.6.599

2021 Impact Factor: 1.411

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy