Convergence of a subgradient method for computing the bound norm of matrices. (French) Zbl 0563.65029

For a linear map \(A: R^ n\to R^ m\), where \(R^ n\) and \(R^ m\) are endowed with norms \(\psi\) and \(\phi\), the bound norm is defined by \(S_{\phi \psi}(A)=\sup \{\phi (Ax):\psi (x)\leq 1\}.\) A subgradient method for computing \(S_{\phi \psi}\) is given and it is shown that it converges if \(\phi\) or \(\psi\) are polyhedral. The paper is written in French.
Reviewer: L.Elsner


65F35 Numerical computation of matrix norms, conditioning, scaling
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
Full Text: DOI


[1] Balas, E., Intersection cuts—A new type of cutting planes for integer programming, Oper. Res., 19, 19-39 (1971) · Zbl 0219.90035
[2] Balas, E., An intersection cut from the dual of the unit hypercube, Oper. Res., 19, 40-44 (1971) · Zbl 0219.90036
[3] Bourbaki, N., Eléments de Mathématiques. Espaces Vectoriels Topologiques (1966), Hermann, Ch. I, II, Fascicule XV · Zbl 0145.37702
[4] Cabot, V.; Francis, L., Solving certain non-convex quadratic minimization problems by ranking the extreme points, Oper. Res., 18, No. 1 (1970) · Zbl 0186.24201
[5] Cabot, V.; Francis, L., Variations on a cutting plane method for solving concave minimization problems with linear constraints, Naval Res. Logist. Quart., 21 (1974) · Zbl 0348.90131
[6] Dunford, N.; Schwartz, J., Linear Operators; Part I: General Theory (1958), Interscience
[7] Eggleston, G., Convexity (1958), Cambridge U.P, Cambridge Tracts 47 · Zbl 0086.15302
[8] Falk, J.; Hoffman, K. R., A successive underestimation method for concave minimization problems, Math. Oper. Res., 1, No. 3 (1976) · Zbl 0362.90082
[9] Ghizzetti, A., Theory and Applications of Monotone Operators, Proceedings of a NATO Advanced Study Institute (1968), Venice, Italy
[10] Glover, F.; Bowman, V. J., A note on zero one integer and concave programming, Oper. Res., 20, No. 1 (1972) · Zbl 0234.90037
[11] Glover, F.; Klingman, D., Concave programming applied to a special class of 0-1 integer programs, Oper. Res., 21, No. 1 (1973) · Zbl 0265.90033
[12] Glover, F., Convexity cuts and search, Oper. Res., 21, No. 1 (1973) · Zbl 0263.90020
[13] Goles, E.; Olivos, J., Comportement itératif des fonctions à seuil et applications, (Séminaire d’Analyse Numérique (1979), U.S.M.G. Lab. IMAG: U.S.M.G. Lab. IMAG Grenoble), No. 327 · Zbl 0454.68042
[15] Goles, E.; Olivos, J., Comportement itératif des fonctions à multiseuils, (Rapport de Recherche No. 189 (1980), U.S.M.G. Lab. IMAG: U.S.M.G. Lab. IMAG Grenoble) · Zbl 0445.94047
[17] Goles, E., Comportement oscillatoire d’une famille d’automates cellulaires non uniformes, (Thèse (1980), U.S.M.G. Lab. IMAG: U.S.M.G. Lab. IMAG Grenoble)
[20] Hoang-Tui, Concave programming under linear constraints, Soviet Math., 5 (1964) · Zbl 0132.40103
[21] Hohenbalken, B., A finite algorithm to maximize certain pseudo-concave functions on polytopes, Math. Programming, 8 (1975) · Zbl 0323.90042
[22] Konno, H., Maximization of convex quadratic function under linear constraints, Math. Programming, 11 (1976) · Zbl 0355.90052
[23] Kothe, G., Topological Vector Spaces I (1969), Springer
[24] Laurent, P. J., Approximation et Optimisation (1972), Hermann · Zbl 0238.90058
[25] Tao, Pham Dinh, Eléments homoduaux d’une matrice \(A\) relatif à un couple de normes (φ, ψ), (Applications au calcul de \(S_{φψ}(A) (1975)\), U.S.M.G. Lab. IMAG: U.S.M.G. Lab. IMAG Grenoble), Séminaire d’Analyse Numérique
[26] Tao, Pham Dinh, Calcul du maximum d’une forme quadratique définie positive sur la boule unité de \(φ_∝\), (Séminaire d’une Analyse Numerique (1976), U.S.M.G. Lab. IMAG: U.S.M.G. Lab. IMAG Grenoble)
[27] Tao, Pham Dinh, Méthodes directes et inderectes pour le calcul du maximum d’une forme quadratique définie positive sur la boule unité de la norme du Max, (Colloque Analyse Numéreque (1976), Port-Bail)
[32] Tao, Pham Dinh, Contribution à la théorie de normes et ses applications à l’analyse numérique, U.S.M.G. Thèse d’Etat (1981)
[33] Raghavachari, M., On connections between zero-one integer programming and concave programming under linear constraints, Oper. Res., 17 (1969) · Zbl 0176.49805
[34] Rockafellar, R. T., Convex Analysis (1970), Princeton U.P · Zbl 0229.90020
[35] Stoer, J.; Witzgall, C. J., Convexity and Optimization in Finite Dimensions (1970), U.S.M.G. Labo. IMAG: U.S.M.G. Labo. IMAG Springer · Zbl 0203.52203
[36] Taha, H. A., Concave minimization over a convex polyedron, Naval Research Logistics Quarterly, 20 (1973)
[37] Tchuente, M., Quelques propriétés des automates cellulaires uniformes (configurations stables, interpolation, simulation), (Seminaire d’Analyse Numérique (1976), U.S.M.G. Labo. IMAG: U.S.M.G. Labo. IMAG Grenoble)
[38] Tchuente, M., Contribution à l’étude des méthodes de calcul pour des systemèmes de type coopératif, Thèse d’Etat (1983), Grenoble
[39] Valentine, F. A., Convex Sets (1964), McGraw-Hill: McGraw-Hill New York · Zbl 0129.37203
[40] Varga, R. S., Matrix Iterative Analysis (1962), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0133.08602
[41] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic: Academic New York · Zbl 0204.48102
[42] Zwart, P. B., Nonlinear programming, Counterexamples to two global optimization algorithms, Opns. Res., 21 (1973) · Zbl 0274.90049
[43] Zwart, P. B., Global maximization of a convex function with linear inequality constraints, Opns. Res., 22 (1974) · Zbl 0322.90049
[44] Thoai, NG. V.; Tuy, H., Convergent algorithms for minimizing a concave function, Math. Opn. Res., 5 (1980) · Zbl 0472.90054
[45] Toland, J. F., On subdifferential calculus and duality in nonconvex optimization, Analyse non convexe. Analyse non convexe, Bull. Soc. Math., 60 (1979), Memoire · Zbl 0411.49012
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.