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.  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]

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

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[3]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391
[4]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[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]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058
[7]

Qianqian Hou, Tai-Chia Lin, Zhi-An Wang. On a singularly perturbed semi-linear problem with Robin boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 401-414. doi: 10.3934/dcdsb.2020083
[8]

Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099
[9]

Helin Guo, Huan-Song Zhou. Properties of the minimizers for a constrained minimization problem arising in Kirchhoff equation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1023-1050. doi: 10.3934/dcds.2020308
[10]

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

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[12]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[13]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[14]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135
[15]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006
[16]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[17]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[18]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018
[19]

Monia Capanna, Jean C. Nakasato, Marcone C. Pereira, Julio D. Rossi. Homogenization for nonlocal problems with smooth kernels. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020385
[20]

Jérôme Lohéac, Chaouki N. E. Boultifat, Philippe Chevrel, Mohamed Yagoubi. Exact noise cancellation for 1d-acoustic propagation systems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020055

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences