×

Semi-infinite programming. (English) Zbl 1124.90042

Summary: A semi-infinite programming problem is an optimization problem in which finitely many variables appear in infinitely many constraints. This model naturally arises in an abundant number of applications in different fields of mathematics, economics and engineering. The paper, which intends to make a compromise between an introduction and a survey, treats the theoretical basis, numerical methods, applications and historical background of the field.

MSC:

90C34 Semi-infinite programming

Software:

SIPAMPL
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Amaya, J.; Gómez, J.A., Strong duality for inexact linear programming problems, Optimization, 49, 243-269, (2001) · Zbl 1168.90557
[2] Anderson, E.J.; Nash, P., Linear programming in infinite dimensional spaces, (1987), Wiley New York
[3] Bank, B.; Guddat, J.; Klatte, D.; Kummer, B.; Tammer, K., Non-linear parametric optimization, (1983), Birkhäuser Verlag Basel · Zbl 0502.49002
[4] Bard, J.F., Practical bilevel optimization, Algorithms and applications, nonconvex optimization and its applications, 30, (1998), Kluwer Dordrecht · Zbl 0943.90078
[5] Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programs, Operations research letters, 25, 1-13, (1999) · Zbl 0941.90053
[6] Birbil, S.I.; Bouza, G.; Frenk, H.; Still, G., Equilibrium constrained optimization problems, European journal of operational research, 169, 3, 1108-1127, (2006) · Zbl 1079.90152
[7] Bonnans, J.F.; Shapiro, A., Optimization problems with perturbations: A guided tour, SIAM review, 40, 2, 228-264, (1998) · Zbl 0915.49021
[8] Bonnans, J.F.; Shapiro, A., Perturbation analysis of optimization problems, (2000), Springer-Verlag New York-Berlin-Heidelberg · Zbl 0966.49001
[9] Borwein, J.M., The limiting Lagrangian as a consequence of the helly’s theorem, Journal of optimization. theory and applications, 33, 497-513, (1981) · Zbl 0427.49029
[10] J.M. Borwein, Semi-infinite programming duality: How special is it?, in: A.V. Fiacco, K.O. Kortanek (Eds.), Semi-Infinite Programming and Applications, Lecture Notes in Economics and Mathematical Systems, vol. 215, 1983, pp. 10-36. · Zbl 0514.49019
[11] Brosowski, B., Parametric semi-infinite optimization, (1982), Verlag Peter Lang Frankfurt · Zbl 0502.49001
[12] Cánovas, M.J.; López, M.A.; Parra, J., Upper semicontinuity of the feasible set mapping for linear inequality systems, Set-valued analysis, 10, 361-378, (2002) · Zbl 1080.90076
[13] Cánovas, M.J.; López, M.A.; Parra, J., Stability in the discretization of a parametric semi-infinite convex inequality system, Mathematics of operations research, 27, 755-774, (2002) · Zbl 1082.90570
[14] Cánovas, M.J.; López, M.A.; Parra, J.; Todorov, M.I., Stability and well-posedness in linear semi-infinite programming, SIAM journal on optimization, 10, 82-98, (1999) · Zbl 0955.90141
[15] Cánovas, M.J.; López, M.A.; Parra, J.; Todorov, M.I., Solving strategies and well-posedness in linear semi-infinite programming, Annals of operations research, 101, 171-190, (2001) · Zbl 0997.90082
[16] Charnes, A.; Cooper, W.W.; Kortanek, K.O., Duality, Haar programs and finite sequence spaces, Proceedings of the national Academy of science, 48, 783-786, (1962) · Zbl 0105.12804
[17] Charnes, A.; Cooper, W.W.; Kortanek, K.O., Duality in semi-infinite programs and some works of Haar and Carathéodory, Management sciences, 9, 209-228, (1963) · Zbl 0995.90615
[18] Charnes, A.; Cooper, W.W.; Kortanek, K.O., On the theory of semi-infinite programming and a generalization of the kuhn – tucker saddle point theorem for arbitrary convex functions, Naval research logistics quarterly, 16, 41-51, (1969) · Zbl 0169.22201
[19] Dall’Aglio, M., On some applications of LSIP to probability and statistics, (), 237-254 · Zbl 1055.90073
[20] Dambrine, M.; Pierre, M., About stability of equilibrium shapes, Mathematical modelling and numerical analysis, 34, 811-834, (2000) · Zbl 0966.49023
[21] Faigle, U.; Kern, W.; Still, G., Algorithmic principles of mathematical programming, (2002), Kluwer Dordrecht · Zbl 1036.90001
[22] Fajardo, M.D.; López, M.A., Locally farkas – minkowski systems in convex semi-infinite programming, Journal of optimization theory and applications, 103, 313-335, (1999) · Zbl 0945.90069
[23] Ferrer, A., Applying global optimization to a problem in short-term hydrothermal scheduling, (), 263-285 · Zbl 1138.90451
[24] A.V. Fiacco, K.O. Kortanek (Eds.), Semi-Infinite Programming and Applications, Lecture Notes in Economics and Mathematical Systems, vol. 215, 1983.
[25] Gayá, V.; López, M.A.; Vera de Serio, V.N., Stability in convex semi-infinite programming and rates of convergence of optimal solutions of discretized finite subproblems, Optimization, 52, 693-713, (2003) · Zbl 1072.90046
[26] Glashoff, K.; Gustafson, S.-A., Linear optimization and approximation, (1983), Springer Verlag Berlin
[27] M.A. Goberna, Linear semi-infinite optimization: Recent advances, in: V. Jeyakumar, A.M. Rubinov (Eds.), Continuous Optimization, Current Trends and Modern Applications Series: Applied Optimization, vol. 99, 2005. · Zbl 1115.90060
[28] Goberna, M.A.; López, M.A., Optimal value function in semi-infinite programming, Journal of optimization. theory and applications, 59, 261-280, (1988) · Zbl 0628.90046
[29] Goberna, M.A.; López, M.A., Topological stability of linear semi-infinite inequality systems, Journal of optimization theory and applications, 89, 227-236, (1996) · Zbl 0866.90128
[30] Goberna, M.A.; López, M.A., Linear semi-infinite optimization, (1998), Wiley Chichester · Zbl 1374.90392
[31] Goberna, M.A.; López, M.A., A comprehensive survey of linear semi-infinite optimization theory, (), 3-27 · Zbl 0909.90256
[32] Goberna, M.A.; López, M.A., Linear semi-infinite programming theory: an updated survey, European journal of operations research, 143, 390-405, (2002) · Zbl 1058.90067
[33] Goberna, M.A.; López, M.A.; Todorov, M.I., Stability theory for linear inequality systems, SIAM journal on matrix analysis and applications, 17, 730-743, (1996) · Zbl 0864.15009
[34] Goberna, M.A.; López, M.A.; Todorov, M.I., Stability theory for linear inequality systems II: upper semicontinuity of the solution set mapping, SIAM journal on optimization, 7, 1138-1151, (1997) · Zbl 0897.15006
[35] Gómez, W.; Gómez, J.-A., Cutting plane algorithms for robust conic convex optimization problems, Optimization methods and software, 21, 5, 779-803, (2006) · Zbl 1112.90054
[36] S. Görner, Ein Hybridverfahren zur Lösung nicht-linearer semi-infiniter Optimierungsprobleme, Ph.D. Thesis, Technische Universität Berlin, Berlin, 1997.
[37] G. Gramlich, R. Hettich, A software package for semi-infinite optimization, in: Numerical Methods of Nonlinear Programming and Their Implementations, Proceeding of the International Conference, Opti-Soft, Quedlinburg/Ger. 1989, Mathematical Research 60 (1991) 29-39. · Zbl 0737.65048
[38] F. Guerra, J.A. Orozco, J.-J. Rückmann, On constraint qualifications in semi-infinite optimization, Parametric optimization and related topics VII, Aportaciones Mat. Investig. 18, Soc. Mat. Mexicana, México (2004) 133-141. · Zbl 1070.90122
[39] J. Guddat, F. Guerra-Vázquez, H.Th. Jongen, Parametric optimization: Singularities, pathfollowing and jumps, B.G. Teubner, Stuttgart; Wiley, Chichester, 1990. · Zbl 0718.90056
[40] Gustafson, S.-A.; Kortanek, K.O., Numerical treatment of a class of semi-infinite programming problems, Naval research logistics quarterly, 20, 477-504, (1973) · Zbl 0272.90073
[41] Haar, A., Über lineare ungleichungen, Acta Mathematica Szeged, 2, 1-14, (1924) · JFM 50.0699.02
[42] E. Haaren-Retagne, A semi-infinite programming algorithm for robot trajectory planning, Dissertation, University Trier, 1992.
[43] ()
[44] Hettich, R., An implementation of a discretization method for semi-infinite programming, Mathematical programming, 34, 354-361, (1986) · Zbl 0592.90061
[45] Hettich, R.; Jongen, H.Th., Semi-infinite programming: conditions of optimality and applications, (), 1-11 · Zbl 0381.90085
[46] Hettich, R.; Zencke, P., Numerische methoden der approximation und der semi-infiniten optimierung, (1982), Teubner Stuttgart · Zbl 0481.65033
[47] R. Hettich, G. Still, On Generalized semi-infinite programming problems, Working paper, University of Trier, 1986. · Zbl 0855.90129
[48] Hettich, R.; Kortanek, K.O., Semi-infinite programming: theory, methods and applications, SIAM review, 35, 380-429, (1993) · Zbl 0784.90090
[49] Hettich, R.; Still, G., Semi-infinite programming models in robotics, () · Zbl 0737.90068
[50] Hettich, R.; Still, G., Second order optimality conditions for generalized semi-infinite programming problems, Optimization, 34, 195-211, (1995) · Zbl 0855.90129
[51] A. Hoffmann, R. Reinhardt, On reverse Chebyshev approximation problems, Technical University of Illmenau, Preprint No. M08/94, 1994.
[52] John, F., Extremum problems with inequalities as subsidiary conditions, Studies and essays: Courant anniversary volume, (1948), Interscience Publisher (Wiley) New York, pp. 187-204
[53] Jongen, H. Th.; Jonker, P.; Twilt, F., Nonlinear optimization in finite dimensions, (2000), Kluwer Dordrecht · Zbl 0985.90083
[54] Jongen, H.Th.; Zwier, G., On the local structure of the feasible set in semi-infinite optimization, (), 185-202 · Zbl 0562.90089
[55] Jongen, H.Th.; Wetterling, W.; Zwier, G., On sufficient conditions for local optimality in semi-infinite programming, Optimization, 18, 165-178, (1987) · Zbl 0616.90070
[56] Jongen, H.Th.; Rückmann, J.-J., On stability and deformation in semi-infinite optimization, (), 29-67 · Zbl 0910.90256
[57] Jongen, H.Th.; Rückmann, J.-J.; Stein, O., Generalized semi-infinite optimization: A first order optimality condition and examples, Mathematical programming, 83, 145-158, (1998) · Zbl 0949.90090
[58] Jongen, H.Th.; Stein, O., On generic one-parametric semi-infinite optimization, SIAM journal of optimization, 7, 4, 1103-1137, (1997) · Zbl 0890.90171
[59] Kawasaki, H., An envelope-like effect of infinitely many inequality constraints on second order necessary conditions for minimization problems, Mathematical programming, 41, 73-96, (1988) · Zbl 0661.49012
[60] Kaplan, A.; Tichatschke, R., On the numerical treatment of a class of semi-infinite terminal problems, Optimization, 41, 1-36, (1997) · Zbl 0872.49013
[61] D. Klatte, Stability of stationary solutions in semi-infinite optimization via the reduction approach, in: Advances in optimization, Proceeding 6th French-German Colloquium, Lambrecht/Germany 1991, Lecture Notes Economics and Mathematical Systems vol. 382, 1992, pp. 155-170.
[62] Klatte, D.; Henrion, R., Regularity and stability in nonlinear semi-infinite optimization, (), 69-102 · Zbl 0911.90330
[63] Kortanek, K.O., On the 1962-1972 decade of semi-infinite programming: A subjective view, (), 3-41 · Zbl 1055.90078
[64] Krabs, W., Optimization and approximation, (1979), Wiley New York · Zbl 0409.90051
[65] León, T.; Vercher, E., Optimization under uncertainty and linear semi-infinite programming: A survey, (), 327-348 · Zbl 1055.90074
[66] Luc, D.T.; Martı´nez-Legaz, J.E.; Seeger, A., Least deviation decomposition with respect to a pair of convex set, Journal of convex analysis, 6, 115-140, (1999) · Zbl 0940.41019
[67] Li, W.; Nahak, C.; Singer, I., Constraint qualifications for semi-infinite systems of convex inequalities, SIAM journal on optimization, 11, 31-52, (2000) · Zbl 0999.90045
[68] Luo, Z.-Q.; Pang, J.-S.; Ralph, D., Mathematical programs with equilibrium constraints, (1997), Cambridge University Press Cambridge
[69] Y. Nesterov, A. Nemirovski, Interior point polynomial algorithms in convex programming, SIAM Studies in Applied Mathematics 13, Philadelphia, 1994.
[70] Outrata, J.; Kovcvara, M.; Zowe, J., Nonsmooth approach to optimization problems with equilibrium constraints, Theory, applications and numerical results, nonconvex optimization and its applications, 28, (1998), Kluwer Dordrecht
[71] Puente, R.; Vera de Serio, V.N., Locally farkas-Minkowski linear semi-infinite systems, Top, 7, 103-121, (1999) · Zbl 0936.15012
[72] Polak, E., On the mathematical foundation of nondifferentiable optimization in engineering design, SIAM review, 29, 21-89, (1987)
[73] Polak, E., Optimization. algorithms and consistent approximations, Applied mathematical sciences, 124, (1997), Springer-Verlag New York
[74] Reemtsen, R.; Görner, S., Numerical methods for semi-infinite programming: A survey, (), 195-275 · Zbl 0908.90255
[75] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton, New Jersey · Zbl 0229.90020
[76] Rogosinski, W.W., Moments of non-negative mass, Proceedings of royal society of London (series A), 245, 1-27, (1958) · Zbl 0082.32404
[77] Rupp, Th., Kuhn – tucker curves for one-parametric semi-infinite programming, Optimization, 20, 61-77, (1989) · Zbl 0672.90100
[78] Shapiro, A., Second order derivatives of extremal value functions and optimality conditions for semi-infinite programs, Mathematics of operations research, 10, 207-219, (1985) · Zbl 0569.90070
[79] Shapiro, A., On Lipschitzian stability of optimal solutions of parametrized semi-infinite programs, Mathematics of operations research, 19, 3, 743-752, (1994) · Zbl 0822.90134
[80] Shapiro, A., Sensitivity analysis of parametrized programs via generalized equations, SIAM journal of control optimization, 32, 2, 553-571, (1994) · Zbl 0922.49018
[81] Shapiro, A., On duality theory of conic linear problems, (), 135-165 · Zbl 1055.90088
[82] Soyster, A.L., Convex programming with set-inclusive constraints and applications to inexact linear programming, Operations research, 21, 1154-1157, (1973) · Zbl 0266.90046
[83] O. Stein, On parametric semi-infinite Optimization, Thesis, University Aachen, Shaker, 1997.
[84] Stein, O., Bilevel strategies in semi-infinite programming, (2003), Kluwer Boston
[85] Stein, O.; Still, G., On optimality conditions for generalized semi-infinite programming problems, Journal of optimization theory and applications, 104, 443-458, (2000) · Zbl 0964.90047
[86] Stein, O.; Still, G., On generalized semi-infinite optimization and bilevel optimization, European journal of operational research, 142, 3, 444-462, (2002) · Zbl 1081.90063
[87] Stein, O.; Still, G., Solving semi-infinite optimization problems with interior point techniques, SIAM journal on control and optimization, 42, 3, 769-788, (2003) · Zbl 1046.90093
[88] Still, G., Generalized semi-infinite programming: theory and methods, European journal of operational research, 119, 301-313, (1999) · Zbl 0933.90063
[89] Still, G., Discretization in semi-infinite programming: the rate of convergence, Mathematical programming series A, 91, 1, 53-69, (2001) · Zbl 1051.90023
[90] Still, G., Approximation theory methods for solving elliptic eigenvalue problems, Zeitschrift für angewandte Mathematik und mechanik, 83, 7, 468-478, (2003) · Zbl 1079.65112
[91] G. Still, Approximation and Optimization: Classical results and new developments, Parametric optimization and related topics VII, Aportaciones Mat. Investig. 18, Soc. Mat. Mexicana, México, 2004, pp. 207-233.
[92] G. Still, E. Haaren-Retagne, R. Hettich, A numerical comparison of two approaches to compute membrane eigenvalues by defect-minimization, International Series of Numerical Mathematics 96, Birkh a˝user Verlag, 1991, pp. 209-224. · Zbl 0725.65094
[93] R. Tichatschke, Lineare Semi-Infinite Optimierungsaufgaben und ihre Anwendungen in der Approximationstheorie, Karl-Marx-Stadt: Wissenschaftliche Schriftenreihe der Technischen Hochschule, 1981.
[94] Tichatschke, R.; Hettich, R.; Still, G., Connections between generalized inexact and semi-infinite linear programming, ZOR-methods and models of OR, 33, 367-382, (1989) · Zbl 0694.90076
[95] Tschernikow, S.N., O teoreme chaara dlja beskonteschnych sistem linejnych neravenctv, Uspekhi matematicheskikh nauk, 113, 199-200, (1963)
[96] Vaz, A.; Fernandes, E.; Gomes, M., SIPAMPL: semi-infinite programming with AMPL, ACM transactions on mathematical software, 30, 1, 47-61, (2004) · Zbl 1068.90001
[97] Vaz, A.; Fernandes, E.; Gomes, M., A sequential quadratic programming with a dual parametrization approach to nonlinear semi-infinite programming, Top, 11, 1, 109-130, (2003) · Zbl 1069.90101
[98] Wetterling, W., Definitheitsbedingungen für relative extrema bei optimierungs- und approximationsaufgaben, Numerische Mathematik, 15, 122-136, (1970) · Zbl 0184.39101
[99] Yong-Jin, Z., Generalizations of some fundamental theorems on linear inequalities, Acta Mathematica sinica, 16, 25-40, (1966) · Zbl 0147.34102
[100] Extended SIP bibliography. <http://www.home.math.utwente.nl/stillgj/sip.html>.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.