An interior point method for growing connected resistive networks

摘要

We consider the problem of growing connected networks of resistors where effective resistance is used as a performance metric. This problem can be cast as a semidefinite program by introducing an ℓ regularization into the optimal control formulation. For small networks this problem can be solved via standard interior point method solvers (e.g., SeDuMi or SDPT3). In this paper, we develop a primal-dual interior point algorithm that is well-suited for large-scale problems. The search direction is obtained using the direct method based on Cholesky factorization and iterative method based on the preconditioned conjugate gradient. We illustrate that both of these significantly outperform general-purpose solvers.