Geodesic
The set of target vectors in a problem of semi-infinite linear programming with a duality gap
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 4, pp. 43-52 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We propose a geometric method for the analysis of duality relations in a pair of semi-infinite linear programming (SILP) problems. The method is based on the use of the conical hull of the coefficients in the constraint system. A relation between the presence of a duality gap and the nonclosedness of the boundary of the conical hull of points in a multidimensional space is established. The geometric approach is used to construct an opposite pair of dual problems and to explore the duality relation for this pair. We construct a nontrivial example of a SILP problem in which the duality gap occurs for noncollinear target vectors.
Keywords: semi-infinite linear programming, duality gap, geometric approach, convex nonclosed cone, set of target vectors. 
@article{TIMM_2016_22_4_a4,
     author = {N. N. Astaf'ev and A. V. Ivanov and S. P. Trofimov},
     title = {The set of target vectors in a problem of semi-infinite linear programming with a duality gap},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {43--52},
     year = {2016},
     volume = {22},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_4_a4/}
}
TY  - JOUR
AU  - N. N. Astaf'ev
AU  - A. V. Ivanov
AU  - S. P. Trofimov
TI  - The set of target vectors in a problem of semi-infinite linear programming with a duality gap
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 43
EP  - 52
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_4_a4/
LA  - ru
ID  - TIMM_2016_22_4_a4
ER  - 
%0 Journal Article
%A N. N. Astaf'ev
%A A. V. Ivanov
%A S. P. Trofimov
%T The set of target vectors in a problem of semi-infinite linear programming with a duality gap
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 43-52
%V 22
%N 4
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_4_a4/
%G ru
%F TIMM_2016_22_4_a4
N. N. Astaf'ev; A. V. Ivanov; S. P. Trofimov. The set of target vectors in a problem of semi-infinite linear programming with a duality gap. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 4, pp. 43-52. http://geodesic.mathdoc.fr/item/TIMM_2016_22_4_a4/

[1] Chames A., Cooper W.W., Kortanek K.O., “A duality theory for convex programs with convex constraints”, Bull. Amer. Math. Soc., 68:6 (1962), 605–608 | DOI | MR

[2] Goberna M.A., Lopez M.A., Linear semi-infinite optimization, Wiley, Chichester, 1998, 356 pp. | MR | Zbl

[3] Karney D.F., “Duality gaps in semi-infinite linear programming - an approximation problem”, Math. Progr., 20:1 (1981), 129–143 | DOI | MR | Zbl

[4] Soyster A.L., “A note on duality gaps in linear programming over convex sets”, J. Optim. Theory Appl., 13:4 (1974), 484–489 | DOI | MR | Zbl

[5] Duffin R.J., Karlovitz L.A., “An infinite linear program with a duality gap”, Management Sci., 12:1 (1965), 122–134 | DOI | MR | Zbl

[6] Glashoff K., Gustafson S.A., Linear optimization and approximation: An introduction to the theoretical analysis and numerical treatment of semi-infinite programs, Springer, N. Y., 1983, 212 pp. | MR | Zbl

[7] Chernikov S.N., Lineinye neravenstva, Nauka, M., 1968, 489 pp. | MR

[8] Trofimov S.P., “Kriterii razryva dvoistvennosti dlya polubeskonechnykh zadach lineinogo programmirovaniya”, Protivorechivye modeli optimizatsii, sb. nauch. tr., IMM UNTs AN SSSR, Sverdlovsk, 1987, 64–70 | MR

[9] Rockafellar R.T., Convex analysis, Princeton University Press, Princeton; New Jork, 1970, 260 pp. | MR | Zbl

[10] Kretschmer K.S., “Programmes in paired spaces”, Canad. J. Math., 13 (1961), 221–238 | DOI | MR | Zbl

[11] Astafev N.N., “Protivopolozhnye zadachi lineinogo programmirovaniya, dvoistvennost, prilozheniya k balansovoi modeli”, Diskretnaya optimizatsiya i issledovanie operatsii, materialy ross. konf., In-t matematiki SO RAN, Novosibirsk, 2007, 12–16

[12] Programma chislennogo analiza sootnoshenii dvoistvennosti. Repozitorii MATLAB-programmy (data obrascheniya: 20.08.2016) https://github.com/re3burn/DGA

[13] Astafev N.N., Beskonechnye sistemy lineinykh neravenstv, Nauka, M., 1991, 136 pp. | MR