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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[9]

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

[10]

B. Jerez, General equilibrium with asymmetric information: A dual approach,, Journal of Economic Theory, ().   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

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

[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.  Google Scholar

[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.  Google Scholar

[23]

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

[24]

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

[25]

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

[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.  Google Scholar

[27]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

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

[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.  Google Scholar

[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.  Google Scholar

[7]

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

[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.  Google Scholar

[9]

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

[10]

B. Jerez, General equilibrium with asymmetric information: A dual approach,, Journal of Economic Theory, ().   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

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

[20]

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

[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.  Google Scholar

[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.  Google Scholar

[23]

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

[24]

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

[25]

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

[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.  Google Scholar

[27]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 & 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 & 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 & 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 & Management Optimization, 2020  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 & 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 & 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 & 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 & 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 & Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022
[10]

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 & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533
[11]

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 & Imaging, 2008, 2 (3) : 317-333. doi: 10.3934/ipi.2008.2.317
[12]

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

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

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

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & Imaging, 2012, 6 (4) : 599-621. doi: 10.3934/ipi.2012.6.599

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences