Abstract
When an optimization problem is posed in a product space it is classical to decompose this problem. The goal of this paper is to show how such an approach can be used when the problem to be solved is not naturally posed in a product space. By associating systematically to this problem an equivalent one posed in ann-fold cartesian product space, we obtain by decomposition of the latter both a splitting of operators and a desintegration of constraints for the former. Applications to three rather classical mathematical programming problems are given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Auslender, “Etude numérique des problèmes d'optimisation avec contraintes”, Doctoral thesis, University of Grenoble (Grenoble, 1969).
A. Auslender,Optimisation, méthodes numériques (Masson, Paris, 1976).
J. Baranger and T. Dumont “Decomposition and projection for nonlinear boundary value problems”, Discussion paper, UER de Mathématiques, University of Lyon I (Lyon, September 1980).
A. Bensoussan and P. Kenneth, “Sur l'analogie entre les méthodes de régularisation et de pénalisation”,Revue d'Informatique et de Recherche Opérationnelle 13-R3 (1968) 13–25.
J. Cea,Optimisation (Dunod, Paris, 1971).
J. Dumont, “Décomposition par projection de certains problèmes elliptiques non linéaires”, 3rd C. Thesis, University of Lyon (Lyon 1978).
I. Ekeland and R. Temam,Analyse convexe et problèmes variationnels (Dunod, Paris, 1974).
W. Findeisen, “Parametric optimization by primal method in multilevel systems”,IEEE Transactions on Systems Science and Cybernetics 4 (1968) 155–164.
N. Gastinel,Analyse numérique linéaire (Hermann, Paris, 1966).
L. G. Gubin, B.T. Polyak and E.V. Raik, “The method of projections for finding the common point of convex sets”,USSR Computational Mathematics and Mathematical Physics 7 (1967) 1–24 (Translation of theZhurnal vychislitelnoj Matematiki i matematicheskoj Fiziki).
Y. Haugazeau, “Sur les inéquations variationnelles et la minimisation de fonctionnelles convexes”, Doctoral thesis, University of Paris (Paris 1968).
A.A. Kaplan, “Determination of the extremum of a linear function of a convex set”,Soviet Mathematics Doklady 9 (1968) 269–271 (Translation of the Pure Mathematics Section of the Doklady Akademii Nauk SSSR)
J.E. Kelley, “The cutting plane method for solving convex programs”,Journal of the Society for Industrial and Applied Mathematics 6 (1958) 15–22.
P.J. Laurent and B. Martinet, “Méthodes duales pour le calcul du minimum d'une fonction convexe sur une intersection de convexes”, in: A. V. Balakrishnan, M. Contensou, B.F. de Veubeke, P. Krée, J. L. Lions and N.N. Moiseev, eds,Lecture Notes in Mathematics 132 (Springer, Berlin, 1970) pp. 159–180.
J.L. Lions and R. Temam, “Eclatement et décentralisation en calcul des variations”, in: A.V. Balakrishnan, M. Contensou, B.F. de Veubeke, P. Krée, J.L. Lions and N.N. Moiseev, eds.,Lecture Notes in Mathématics 132 (Springer, Berlin, 1970) pp. 196–217.
J.L. Lions and G.I. Marchouk,Sur les méthodes numériques en sciences physiques et économiques (Dunod, Paris, 1974).
L. McLinden, “Symmetrized separable convex programming”,Transactions of the American Mathematical Society 247 (1979) 1–44.
B. Martinet, “Algorithmes pout la résolution des problèmes d'optimisation et de minimax”, Doctoral thesis, University of Grenoble (Grenoble, 1972).
B. Martinet and A. Auslander, “Méthodes de décomposition pour la minimisation d'une fonction sur un espace produit”,SIAM Journal on Control 12 (1974) 635–642.
Y.I. Merzlyakov, “On a relaxation method of solving systems of linear inequalities”USSR Computational Mathematics and Mathematical Physics 2 (1962) 482–487 (Translation of the Zhurnal vychislitelnoj Matematiki i matematicheskoj Fiziki).
M. D. Mesarovic, D. Macko and Y. Takahara,Theory of hierarchical multilevel systems (Academic Press, New York, 1970).
J.J. Moreau, “Proximité et dualité dans un espace hilbertien”,Bulletin de la Société Mathématique de France 93 (1965) 273–299.
W. Oettli, “An iterative method, having a linear rate of convergence, for solving a pair of dual linear programs”,Mathematical Programming 3 (1972) 302–311.
E.L. Peterson, “Generalization and symmetrization of duality in geometric programming”, Discussion paper, Northwestern University, [Evanston, 1972].
G. Pierra, “Eclatement de contraintes en parallèle pour la minimisation d'une forme quadratique” in: J. Cea, ed.,Lecture Notes in Computer Science 41 (Springer, Berlin, 1976) pp. 200–218.
G. Pierra, “Crossing of algorithms in decomposition methods”, in: G. Gardabassi and A. Locatelli, eds.,Large Scale Systems theory and applications (ISA, Pittsburg, 1976) pp. 309–319.
G. Pierra, “Méthodes de décomposition et croisement d'algorithmes pour des problèmes d'optimisation”, Doctoral thesis, University of Grenoble (Grenoble 1976).
R. T. Rockafellar, “Monotone operators and the proximal point algorithm”,SIAM Journal on Control 14 (1976) 877–898.
R. Temam, “Quelques méthodes de décomposition en analyse numérique”, in:Actes, Congrès International des Mathématiciens 1970 (Gauthier-Villars, Paris, 1971) pp. 311–319.
N.N. Yanenko,Méthode à pas fractionnaires (Armand Colin, Paris, 1968).
R.S. Varga,Matrix iterative analysis (Prentice Hall, Englewood Cliffs, N.J., 1962).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Pierra, G. Decomposition through formalization in a product space. Mathematical Programming 28, 96–115 (1984). https://doi.org/10.1007/BF02612715
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02612715