• 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

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

[3]

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

[4]

R. DeVore and G. Lorentz, "Constructive Approximation,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 303 (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.   Google Scholar

[6]

P. Gribik, A central-cutting-plane algorithm for semi-infinite programming problems,, in, 15 (1979), 66.   Google Scholar

[7]

R. Hettich, An implementation of a discretization method for semi-infinite programming,, Mathematical Programming, 34 (1986), 354.  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.  doi: 10.1007/BF01585742.  Google Scholar

[9]

W. Huyer and A. Neumair, A new exact penalty function,, SIAM J. Optimization, 13 (2003), 1141.  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.  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, (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.  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.  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.  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.  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.  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.  doi: 10.1137/040619867.  Google Scholar

[19]

J.-S. Pang, Error bound in mathematical programming,, Mathematical Programming, 79 (1997), 299.  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.   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.  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.  doi: 10.1007/BF00940041.  Google Scholar

[23]

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

[24]

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

[25]

H. Voigt, Semi-infinite transportation problems,, Zeitschrift für Analysis und ihre Anwendungen, 17 (1998), 729.   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.  doi: 10.1198/016214504000002005.  Google Scholar

[27]

G. A. Watson, Globally convergent methods for semi-infinite programming,, BIT, 21 (1981), 362.  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.   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.  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.  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.  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.   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.   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.  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.  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.   Google Scholar

[3]

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

[4]

R. DeVore and G. Lorentz, "Constructive Approximation,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 303 (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.   Google Scholar

[6]

P. Gribik, A central-cutting-plane algorithm for semi-infinite programming problems,, in, 15 (1979), 66.   Google Scholar

[7]

R. Hettich, An implementation of a discretization method for semi-infinite programming,, Mathematical Programming, 34 (1986), 354.  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.  doi: 10.1007/BF01585742.  Google Scholar

[9]

W. Huyer and A. Neumair, A new exact penalty function,, SIAM J. Optimization, 13 (2003), 1141.  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.  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, (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.  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.  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.  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.  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.  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.  doi: 10.1137/040619867.  Google Scholar

[19]

J.-S. Pang, Error bound in mathematical programming,, Mathematical Programming, 79 (1997), 299.  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.   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.  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.  doi: 10.1007/BF00940041.  Google Scholar

[23]

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

[24]

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

[25]

H. Voigt, Semi-infinite transportation problems,, Zeitschrift für Analysis und ihre Anwendungen, 17 (1998), 729.   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.  doi: 10.1198/016214504000002005.  Google Scholar

[27]

G. A. Watson, Globally convergent methods for semi-infinite programming,, BIT, 21 (1981), 362.  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.   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.  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.  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.  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.   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.   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.  doi: 10.1016/j.cam.2011.01.038.  Google Scholar

[1]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[3]

Ziteng Wang, Shu-Cherng Fang, Wenxun Xing. On constraint qualifications: Motivation, design and inter-relations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 983-1001. doi: 10.3934/jimo.2013.9.983

[4]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281

[5]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709

[6]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881

[7]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018

[8]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[9]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[10]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463

[11]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[12]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[13]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

[14]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[15]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261

[16]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090

[17]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Metrics

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

[Back to Top]