Le but de cette Note est de démontrer des résultats dans l'optimisation de deux variables entières qui correspondent aux résultats fondamentaux de l'analyse convexe des variables réelles, à savoir qu'un minimum local d'une fonction convexe est global ; que la fonction marginale d'une fonction convexe est convexe ; et que deux ensembles convexes disjoints peuvent être séparés par un hyperplan.
The goal of this Note is to prove results in optimization of two integer variables which correspond to fundamental results in convex analysis of real variables, viz. that a local minimum of a convex function is global; that the marginal function of a convex function is convex; and that two disjoint convex sets can be separated by a hyperplane.
Accepté le :
Publié le :
@article{CRMATH_2008__346_1-2_49_0,
author = {Kiselman, Christer O.},
title = {Minima locaux, fonctions marginales et hyperplans s\'eparants dans l'optimisation discr\`ete},
journal = {Comptes Rendus. Math\'ematique},
pages = {49--52},
publisher = {Elsevier},
volume = {346},
number = {1-2},
year = {2008},
doi = {10.1016/j.crma.2007.10.047},
language = {fr},
url = {http://www.numdam.org/articles/10.1016/j.crma.2007.10.047/}
}
TY - JOUR AU - Kiselman, Christer O. TI - Minima locaux, fonctions marginales et hyperplans séparants dans l'optimisation discrète JO - Comptes Rendus. Mathématique PY - 2008 SP - 49 EP - 52 VL - 346 IS - 1-2 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2007.10.047/ DO - 10.1016/j.crma.2007.10.047 LA - fr ID - CRMATH_2008__346_1-2_49_0 ER -
%0 Journal Article %A Kiselman, Christer O. %T Minima locaux, fonctions marginales et hyperplans séparants dans l'optimisation discrète %J Comptes Rendus. Mathématique %D 2008 %P 49-52 %V 346 %N 1-2 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2007.10.047/ %R 10.1016/j.crma.2007.10.047 %G fr %F CRMATH_2008__346_1-2_49_0
Kiselman, Christer O. Minima locaux, fonctions marginales et hyperplans séparants dans l'optimisation discrète. Comptes Rendus. Mathématique, Tome 346 (2008) no. 1-2, pp. 49-52. doi : 10.1016/j.crma.2007.10.047. http://www.numdam.org/articles/10.1016/j.crma.2007.10.047/
[1] Theory of capacities, Ann. Inst. Fourier (Grenoble), Volume 5 (1953/1954), pp. 131-295 (1995)
[2] Submodular functions and convexity (Bachem, A.; Grötschel, M.; Korte, B., eds.), Mathematical Programming—The State of the Art, Springer-Verlag, Berlin, 1983, pp. 235-257
[3] Discrete Convex Analysis, Society for Industrial and Applied Mathematics, Philadelphia, 2003
Cité par Sources :
