Abstract
This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Calamai, P.H., Moré, J.J.: Projected gradient methods for linear constrained problems. Math. Program. 39, 93–116 (1987)
Chen, C., Qi, L., Sun, D.: Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comput. 67, 519–540 (1998)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
Coope, I.D., Watson, G.A.: A projected Lagrangian algorithm for semi-infinite programming. Math. Program. 32, 337–356 (1985)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, I–II. Springer, New York (2003)
Fischer, A.: Solution of monotone complementarity problems with locally Lipschitzian functions. Math. Program. 76, 513–532 (1997)
Gabriel, S.A., Moré, J.J.: Smoothing of mixed complementarity problems. In: Ferris, M.C., Pang, J.S. (eds.) Complementarity and Variational Problems: State of the Art, pp. 105–116. SIAM, Philadelphia (1997)
Goberna, M.A., López, M.A.: Semi-Infinite Programming: Recent Advances. Kluwer Academic, Dordrecht (2001)
Hettich, R., Kortanek, K.O.: Semi-infinite programming: theory, methods, and applications. SIAM Rev. 35, 380–429 (1993)
Li, D.H., Qi, L., Tam, J., Wu, S.Y.: A smoothing Newton method for semi-infinite programming. J. Glob. Optim. 30, 169–194 (2004)
Ling, C., Qi, L., Zhou, G., Wu, S.Y.: Global convergence of a robust smoothing SQP method for semi-infinite programming. J. Optim. Theory Appl. 129, 147–164 (2006)
Meng, F., Sun, D., Zhao, G.: Semismoothness of solutions to generalized equations and the Moreau–Yosida regularization. Math. Program. 104, 561–581 (2005)
Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977)
Pang, J.S., Qi, L.: Nonsmooth equations: motivation and algorithms. SIAM J. Optim. 3, 443–465 (1993)
Polak, E.: On the mathematical foundation of nondifferentiable optimization in engineering design. SIAM Rev. 29, 21–89 (1987)
Polak, E.: Optimization: Algorithms and Consistent Approximation. Springer, New York (1997)
Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)
Qi, L., Shapiro, A., Ling, C.: Differentiability and semismoothness properties of integral functions and their applications. Math. Program. Ser. A 102, 223–248 (2005)
Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87, 1–35 (2000)
Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)
Qi, L., Wu, S.Y., Zhou, G.: Semismooth Newton methods for solving semi-infinite programming problems. J. Glob. Optim. 27, 215–232 (2003)
Shapiro, A.: First and second order optimality conditions and perturbation analysis of semi-infinite programming problems. In: Reemtsen, R., Rükmann, J. (eds.) Semi-Infinite Programming, pp. 103–133. Kluwer Academic, Boston (1998)
Still, G.: Discretization in semi-infinite programming: the rate of convergence. Math. Program. 91, 53–69 (2001)
Sun, D., Womersley, R.S., Qi, H.: A feasible semismooth asymptotically Newton method for mixed complementarity problems. Math. Program. 94, 167–187 (2002)
Teo, K.L., Rehbock, V., Jennings, L.S.: A new computational algorithm for functional inequality constrained optimization problems. Automatica 29, 789–792 (1993)
Teo, K.L., Yang, X.Q., Jennings, L.S.: Computational discretization algorithms for functional inequality constrained optimization. Ann. Oper. Res. 98, 215–234 (2000)
Watson, G.A.: Numerical experiments with globally convergent methods for semi-infinite programming problems. In: Fiacco, A.V., Kortanek, K.O. (eds.) Semi-Infinite Programming and Applications, pp. 193–205. Springer, Berlin (1981)
Wu, S.Y., Li, D.H., Qi, L., Zhou, G.: An iterative method for solving KKT system of the semi-infinite programming. Optim. Methods Softw. 20, 629–643 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Qi’s work is supported by the Hong Kong Research Grant Council.
Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168).
Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038).
Zhou’s work is supported by Australian Research Council.
Rights and permissions
About this article
Cite this article
Qi, L., Ling, C., Tong, X. et al. A smoothing projected Newton-type algorithm for semi-infinite programming. Comput Optim Appl 42, 1–30 (2009). https://doi.org/10.1007/s10589-007-9117-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9117-x