Main Article Content

Abstract

After a brief introduction to the field of Conic Optimization we present an application to the (robust) resistor network topology design problem, where the goal is to design an electrical network containing resistors, such that the dissipation is minimal, given the external current values at the nodes of the network and assuming that the conductance values satisfy some normalizing constraint. We present a linear model for the single-current case and semidefinite models for multi-current cases. All models are illustrated by examples.

 

 

Keywords

Conic optimization Network topology design Conic quadratic optimization Semidefinite optimization Robust optimization.

Article Details

References

  1. AITCHISON, R.E. 1964. Resistance between adjacent points of Liebman mesh. Am. J. Phys., 32: 566-566.
  2. BELEVITCH, V. 1968. Classical Network Theory. Holden-Day, San Francisco, California, USA.
  3. BEN-TAL, A., EL GHAOUI, L. and NEMIROVSKI, A. 2000. Robustness. In Handbook of Semidefinite Programming, Internat. Ser. Oper. Res. Management Sci., 27: 139–162.
  4. BEN-TAL, A., EL GHAOUI, L. and NEMIROVSKI, A. 2009. Robust Optimization. Princeton Series in Applied Optimization. Princeton University Press, Princeton, USA.
  5. BEN-TAL, A., MARGALIT, T. AND NEMIROVSKI, A. 1999. Robust modeling of multi-stage portfolio problems. In S. ZHANG, H. FRENK, C. ROOS, and T. TERLAKY (eds.), High Performence Optimization Techniques, pp. 303–328. Kluwer Academic Publishers, Dordrecht, The Netherlands.
  6. BEN-TAL, A. and NEMIROVSKI, A. 1997. Robust truss topology design via semidefinite programming. SIAM Journal on Optimization, 7(4): 991–1016.
  7. BEN-TAL, A. and NEMIROVSKI, A. 1998. Robust convex optimization. Math. Oper. Res., 23(4): 769–805.
  8. BEN-TAL, A. and NEMIROVSKI, A. 1999. Robust solutions of uncertain linear programs. Oper. Res. Lett., 25(1): 1–13.
  9. BEN-TAL, A. and NEMIROVSKI, A. 2000. Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, 88(3, Ser. A): 411–424.
  10. BEN-TAL, A. and NEMIROVSKI, A. 2001. Lectures on Modern Convex Optimization. Analysis, Algorithms and Engineering Applications, volume 2 of MPS-SIAM Series on Optimization. SIAM, Philadelphia, USA.
  11. BEN-TAL, A. and NEMIROVSKI, A. 2002. On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM Journal on Optimization, 12(3): 811–833 (electronic).
  12. BEN-TAL, A. and NEMIROVSKI, A. 2002. Robust optimization—methodology and applications. Mathematical Programming, 92(3, Ser. B): 453–480.
  13. EL GHAOUI, L. AND LEBRET, H. 1997. Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications, 18(4): 1035–1064.
  14. EL GHAOUI, L., OUSTRY, F. and LEBRET, H. 1999. Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9(1): 33–52 (electronic).
  15. GHOSH, A., BOYD, S. and SABERI, A. 2008. Minimizing effective resistance of a graph. SIAM Review, 50: 37–66.
  16. NESTEROV, Y. and NEMIROVSKI, A. 1994. Interior-Point Polynomial Algorithms in Convex Programming, volume 13 of SIAM Studies in Applied Mathematics. SIAM, Philadelphia, USA.
  17. ROOS, C., TERLAKY, T. and VIAL, J.-PH. 2005. Theory and Algorithms for Linear Optimization. Springer, Chichester, UK (1st Edition, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, 1997).
  18. SOYSTER, A.L. 1973. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21(5): 1154–1157.
  19. TERLAKY, T. (Ed.) 1996. Interior Point Methods of Mathematical Programming, volume 5 of Applied Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands.
  20. WRIGHT, S.J. 1997. Primal-Dual Interior-Point Methods. SIAM, Philadelphia, USA.
  21. YE, Y. 1997. Interior Point Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York, USA.