M.Sc Thesis
M.Sc Student Steinberg Daureen Computation of Matrix Norms with Applications to Robust Optimization Department of Industrial Engineering and Management Professor Arkadi Nemirovski

Abstract

The research is devoted to investigating the problem of computing the norm ||A||E,F=max||Ax||F: xєE,||x||E≤1of linear mapping xAx, acting from a finite dimensional normed space (E,|| . ||E) to a finite dimensional normed space (F,|| . ||F). We focused on the case where (E,|| . ||E) = (Rn,|| . ||p) and (F,|| . ||F)= (Rm,|| . ||r), so that A can be identified with an m X n matrix; the associated norm ||A||E,F is denoted by ||A||p,r. In our research we proved that ||A||p,r is NP hard in the case when 1 ≤ r < p ≤ ∞ - this results coincides with our conjecture that the only easy cases to compute ||A||p,r are when (p=1, 1 ≤ r ≤∞), (r=∞, 1 ≤ p ≤ ∞), (p=r=2). We also refine Nestrov’s theorem by showing that the quantity of the upper bound placed by semidefinite relaxation on ||A||p,r in the case of

1≤ r ≤ 2 ≤ p ≤ ∞, is much less conservative in a wide range of values of p,r than the 2.29 factor suggested by Nestrov. Finally we develop a simple interpolation technique allowing to extend the efficiently upper bound on ||A||p,r from its original domain to the entire range of  p ≥ 1, r ≥ 1 and we showed that the extended bound is tight within a factor depending on p,n,r,m and never exceeding O(1)(max(m,n))25/128. Our analysis demonstrates that this factor does not exceed 9.48 for all p,r, provided that m,n≤100,000.