Largest dual ellipsoids inscribed in dual cones

• 成果类型: Article
• 署名作者: Todd, M. J.
• 署名单位: Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0171-z
• 发表日期: 2009
• 页码: 425-434
• 关键词: interior-point methods; optimization; complexity; geometry

摘要

Suppose (x) over bar and (s) over bar lie in the interiors of a cone K and its dual K*, respectively. We seek dual ellipsoidal norms such that the product of the radii of the largest inscribed balls centered at (x) over bar and (s) over bar and inscribed in K and K *, respectively, is maximized. Here the balls are defined using the two dual norms. When the cones are symmetric, that is self-dual and homogeneous, the solution arises directly from the Nesterov-Todd primal-dual scaling. This shows a desirable geometric property of this scaling in symmetric cone programming, namely that it induces primal/dual norms that maximize the product of the distances to the boundaries of the cones.