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

Pham Dinh Tao

Linear Algebra Appl. 62, 163-182 (1984).

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

MSC:

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

Keywords:

nonconvex optimization; polyhedral norms; bound norm; subgradient method

References:

[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