论文标题
无约束几何编程和缩放问题的内点方法
Interior-point methods for unconstrained geometric programming and scaling problems
论文作者
论文摘要
我们为未约束的几何程序提供了两种内点方法，这是基于条件的分析，即在包括矩阵缩放，矩阵平衡和熵最大化的应用中自然出现的一类凸线程序。我们的状况数量是与几何程序的牛顿多层人士相关的自然几何量，并导致近似最小化器的直径界限。我们还提供了一般情况下和牛顿多层的组合假设的有效界限。通过这种方式，我们概括了矩阵缩放和矩阵平衡的最新内点方法的迭代复杂性。最近，关于谎言组的某些优化问题（称为容量和缩放问题）的算法已有很多工作。对于交换群体，这些问题减少了无约束的几何计划，这是我们工作的特定动机来源。
We provide a condition-based analysis of two interior-point methods for unconstrained geometric programs, a class of convex programs that arise naturally in applications including matrix scaling, matrix balancing, and entropy maximization. Our condition numbers are natural geometric quantities associated with the Newton polytope of the geometric program, and lead to diameter bounds on approximate minimizers. We also provide effective bounds on the condition numbers both in general and under combinatorial assumptions on the Newton polytope. In this way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing. Recently, there has been much work on algorithms for certain optimization problems on Lie groups, known as capacity and scaling problems. For commutative groups, these problems reduce to unconstrained geometric programs, which serves as a particular source of motivation for our work.
