Improving the constant in Nesterov's \frac{\pi}{2}-theorem
From MaRDI portal
Publication:6370864
arXiv2106.11290MaRDI QIDQ6370864FDOQ6370864
Authors: Roland Hildebrand 
Publication date: 21 June 2021
Abstract: One of the hard optimization problems that has a semi-definite relaxation with quantitative bound on the approximation error is the maximization of a convex quadratic form on the hypercube. The relaxation not only yields an upper bound on the optimal value, but its solution can be used to construct random sub-optimal solutions of the original problem whose expected value is not less than times the value of the relaxation. This constant cannot be improved globally. More precisely, for every there exists a problem instance for which the ratio of the two values in question is larger than . However, if a given problem instance is considered, then the relaxation yields a concrete solution which may result in a much better ratio. In this contribution we present an improved, explicit bound depending on the rank of the solution. We consider also the problem of maximization of a convex hermitian quadratic form on the complex poly-disc. In this case a bound on the approximation error is given by the -theorem of Ben-Tal, Nemirovski, and Roos. The derivation of a rank-dependent improved bound is similar to the real case. In the complex case we provide explicit expressions in the form of an infinite series and conjecture a closed-form expression.
This page was built for publication: Improving the constant in Nesterov's $\frac{\pi}{2}$-theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370864)
