[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v44y2019i1p1319-1348.html
   My bibliography  Save this article

Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm

Author

Listed:
  • Jan Ossenbrink

    (Department of Management, Technology, and Economics, ETH Zurich, 8092 Zurich, Switzerland; Stanford Graduate School of Business, Stanford University, Stanford, California 94305)

  • Joern Hoppmann

    (Department of Management, Technology, and Economics, ETH Zurich, 8092 Zurich, Switzerland; Department of Business Administration, Economics, and Law, University of Oldenburg, 26129 Oldenburg, Germany)

Abstract
It is well known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case, the algorithm’s rate of convergence is determined by the condition number of the function. In a similar vein, it has been shown that a variant of the Frank–Wolfe algorithm with away steps converges linearly when applied to a strongly convex function with Lipschitz gradient over a polytope. In a nice extension of the unconstrained case, the algorithm’s rate of convergence is determined by the product of the condition number of the function and a certain condition number of the polytope. We shed new light on the latter type of polytope conditioning. In particular, we show that previous and seemingly different approaches to define a suitable condition measure for the polytope are essentially equivalent to each other. Perhaps more interesting, they can all be unified via a parameter of the polytope that formalizes a key premise linked to the algorithm’s linear convergence. We also give new insight into the linear convergence property. For a convex quadratic objective, we show that the rate of convergence is determined by a condition number of a suitably scaled polytope.

Suggested Citation

  • Jan Ossenbrink & Joern Hoppmann, 2019. "Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 1319-1348, February.
    • Handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:1319-1348
    DOI: 10.1287/moor.2017.0910
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0910
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2017.0910?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Mary Tripsas & Giovanni Gavetti, 2000. "Capabilities, cognition, and inertia: evidence from digital imaging," Strategic Management Journal, Wiley Blackwell, vol. 21(10‐11), pages 1147-1161, October.
    2. James G. March, 1991. "Exploration and Exploitation in Organizational Learning," Organization Science, INFORMS, vol. 2(1), pages 71-87, February.
    3. Michael Tushman & Wendy K. Smith & Robert Chapman Wood & George Westerman & Charles O'Reilly, 2010. "Organizational designs and innovation streams," Industrial and Corporate Change, Oxford University Press and the Associazione ICC, vol. 19(5), pages 1331-1366, October.
    4. Sumantra Ghoshal & Christopher A. Bartlett, 1994. "Linking organizational context and managerial action: The dimensions of quality of management," Strategic Management Journal, Wiley Blackwell, vol. 15(S2), pages 91-112, June.
    5. Jack A. Nickerson & Todd R. Zenger, 2002. "Being Efficiently Fickle: A Dynamic Theory of Organizational Choice," Organization Science, INFORMS, vol. 13(5), pages 547-566, October.
    6. Tom J. M. Mom & Frans A. J. Van Den Bosch & Henk W. Volberda, 2007. "Investigating Managers' Exploration and Exploitation Activities: The Influence of Top‐Down, Bottom‐Up, and Horizontal Knowledge Inflows," Journal of Management Studies, Wiley Blackwell, vol. 44(6), pages 910-931, September.
    7. Justin J. P. Jansen & Frans A. J. Van Den Bosch & Henk W. Volberda, 2006. "Exploratory Innovation, Exploitative Innovation, and Performance: Effects of Organizational Antecedents and Environmental Moderators," Management Science, INFORMS, vol. 52(11), pages 1661-1674, November.
    8. Chang, Yi-Ying & Hughes, Mathew, 2012. "Drivers of innovation ambidexterity in small- to medium-sized firms," European Management Journal, Elsevier, vol. 30(1), pages 1-17.
    9. Justin J.P. Jansen & Zeki Simsek & Qing Cao, 2012. "Ambidexterity and performance in multiunit contexts: Cross‐level moderating effects of structural and resource attributes," Strategic Management Journal, Wiley Blackwell, vol. 33(11), pages 1286-1303, November.
    10. Burgers, J. Henri & Jansen, Justin J.P. & Van den Bosch, Frans A.J. & Volberda, Henk W., 2009. "Structural differentiation and corporate venturing: The moderating role of formal and informal integration mechanisms," Journal of Business Venturing, Elsevier, vol. 24(3), pages 206-220, May.
    11. Burgelman, Robert A. & Grove, Andrew S., 2007. "Let Chaos Reign, Then Rein In Chaos--Repeatedly: Managing Strategic Dynamics For Corporate Longevity," Research Papers 1954, Stanford University, Graduate School of Business.
    12. Paul S. Adler & Barbara Goldoftas & David I. Levine, 1999. "Flexibility Versus Efficiency? A Case Study of Model Changeovers in the Toyota Production System," Organization Science, INFORMS, vol. 10(1), pages 43-68, February.
    13. O'Reilly, Charles A., III & Tushman, Michael L., 2013. "Organizational Ambidexterity: Past, Present and Future," Research Papers 2130, Stanford University, Graduate School of Business.
    14. Will Mitchell & Kulwant Singh, 1993. "Death of the Lethargic: Effects of Expansion into New Technical Subfields on Performance in a Firm's Base Business," Organization Science, INFORMS, vol. 4(2), pages 152-180, May.
    15. Mary Tripsas, 1997. "Unraveling The Process Of Creative Destruction: Complementary Assets And Incumbent Survival In The Typesetter Industry," Strategic Management Journal, Wiley Blackwell, vol. 18(S1), pages 119-142, July.
    16. Wendy K. Smith & Michael L. Tushman, 2005. "Managing Strategic Contradictions: A Top Management Model for Managing Innovation Streams," Organization Science, INFORMS, vol. 16(5), pages 522-536, October.
    17. Alexander Zimmermann & Sebastian Raisch & Julian Birkinshaw, 2015. "How Is Ambidexterity Initiated? The Emergent Charter Definition Process," Organization Science, INFORMS, vol. 26(4), pages 1119-1139, August.
    18. Jatinder S. Sidhu & Henk W. Volberda & Harry R. Commandeur, 2004. "Exploring Exploration Orientation and its Determinants: Some Empirical Evidence," Journal of Management Studies, Wiley Blackwell, vol. 41(6), pages 913-932, September.
    19. Michael Lubatkin & Zeki Simsek & Yan Ling & John F. Veiga, 2006. "Ambidexterity and Performance in Small-to Medium-Sized Firms : The Pivotal Role of Top Management Team Behavioral Integration," Post-Print hal-02311781, HAL.
    20. Constantine Andriopoulos & Marianne W. Lewis, 2009. "Exploitation-Exploration Tensions and Organizational Ambidexterity: Managing Paradoxes of Innovation," Organization Science, INFORMS, vol. 20(4), pages 696-717, August.
    21. Christina Fang & Jeho Lee & Melissa A. Schilling, 2010. "Balancing Exploration and Exploitation Through Structural Design: The Isolation of Subgroups and Organizational Learning," Organization Science, INFORMS, vol. 21(3), pages 625-642, June.
    22. Michael L. Tushman & Lori Rosenkopf, 1996. "Executive Succession, Strategic Reorientation and Performance Growth: A Longitudinal Study in the U.S. Cement Industry," Management Science, INFORMS, vol. 42(7), pages 939-953, July.
    23. Clark G. Gilbert, 2006. "Change in the Presence of Residual Fit: Can Competing Frames Coexist?," Organization Science, INFORMS, vol. 17(1), pages 150-167, February.
    24. Robert A. Burgelman & Andrew S. Grove, 2007. "Let chaos reign, then rein in chaos—repeatedly: managing strategic dynamics for corporate longevity," Strategic Management Journal, Wiley Blackwell, vol. 28(10), pages 965-979, October.
    25. Brian Wu & Zhixi Wan & Daniel A. Levinthal, 2014. "Complementary assets as pipes and prisms: Innovation incentives and trajectory choices," Strategic Management Journal, Wiley Blackwell, vol. 35(9), pages 1257-1278, September.
    26. Mikael Holmqvist, 2004. "Experiential Learning Processes of Exploitation and Exploration Within and Between Organizations: An Empirical Study of Product Development," Organization Science, INFORMS, vol. 15(1), pages 70-81, February.
    27. Peter Boumgarden & Jackson Nickerson & Todd R. Zenger, 2012. "Sailing into the wind: Exploring the relationships among ambidexterity, vacillation, and organizational performance," Strategic Management Journal, Wiley Blackwell, vol. 33(6), pages 587-610, June.
    28. Mary Tripsas, 2009. "Technology, Identity, and Inertia Through the Lens of “The Digital Photography Company”," Organization Science, INFORMS, vol. 20(2), pages 441-460, April.
    29. Zeki Simsek, 2009. "Organizational Ambidexterity: Towards a Multilevel Understanding," Journal of Management Studies, Wiley Blackwell, vol. 46(4), pages 597-624, June.
    30. Sebastian Raisch & Julian Birkinshaw & Gilbert Probst & Michael L. Tushman, 2009. "Organizational Ambidexterity: Balancing Exploitation and Exploration for Sustained Performance," Organization Science, INFORMS, vol. 20(4), pages 685-695, August.
    31. Qing Cao & Eric Gedajlovic & Hongping Zhang, 2009. "Unpacking Organizational Ambidexterity: Dimensions, Contingencies, and Synergistic Effects," Organization Science, INFORMS, vol. 20(4), pages 781-796, August.
    32. Jatinder S. Sidhu & Harry R. Commandeur & Henk W. Volberda, 2007. "The Multifaceted Nature of Exploration and Exploitation: Value of Supply, Demand, and Spatial Search for Innovation," Organization Science, INFORMS, vol. 18(1), pages 20-38, February.
    33. Nicolaj Siggelkow & Daniel A. Levinthal, 2003. "Temporarily Divide to Conquer: Centralized, Decentralized, and Reintegrated Organizational Approaches to Exploration and Adaptation," Organization Science, INFORMS, vol. 14(6), pages 650-669, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jan Ossenbrink & Joern Hoppmann & Volker H. Hoffmann, 2019. "Hybrid Ambidexterity: How the Environment Shapes Incumbents’ Use of Structural and Contextual Approaches," Organization Science, INFORMS, vol. 30(6), pages 1319-1348, November.
    2. Olga Kassotaki, 2022. "Review of Organizational Ambidexterity Research," SAGE Open, , vol. 12(1), pages 21582440221, March.
    3. O'Reilly, Charles A., III & Tushman, Michael L., 2013. "Organizational Ambidexterity: Past, Present and Future," Research Papers 2130, Stanford University, Graduate School of Business.
    4. Alexander Zimmermann & Sebastian Raisch & Julian Birkinshaw, 2015. "How Is Ambidexterity Initiated? The Emergent Charter Definition Process," Organization Science, INFORMS, vol. 26(4), pages 1119-1139, August.
    5. Úbeda-García, Mercedes & Claver-Cortés, Enrique & Marco-Lajara, Bartolomé & Zaragoza-Sáez, Patrocinio, 2020. "Toward a dynamic construction of organizational ambidexterity: Exploring the synergies between structural differentiation, organizational context, and interorganizational relations," Journal of Business Research, Elsevier, vol. 112(C), pages 363-372.
    6. Christine Chou & Steven O. Kimbrough, 2016. "An agent-based model of organizational ambidexterity decisions and strategies in new product development," Computational and Mathematical Organization Theory, Springer, vol. 22(1), pages 4-46, March.
    7. Yasser Alizadeh & Antonie J. Jetter, 2019. "Pathways for Balancing Exploration and Exploitation in Innovations: A Review and Expansion of Ambidexterity Theory," International Journal of Innovation and Technology Management (IJITM), World Scientific Publishing Co. Pte. Ltd., vol. 16(05), pages 1-33, August.
    8. Sebastian Raisch & Michael L. Tushman, 2016. "Growing New Corporate Businesses: From Initiation to Graduation," Organization Science, INFORMS, vol. 27(5), pages 1237-1257, October.
    9. Sebastian Raisch & Julian Birkinshaw & Gilbert Probst & Michael L. Tushman, 2009. "Organizational Ambidexterity: Balancing Exploitation and Exploration for Sustained Performance," Organization Science, INFORMS, vol. 20(4), pages 685-695, August.
    10. Martin Owusu Ansah & Nicholas Addai-Boamah & Abeeku Bylon Bamfo & Lucy Afeafa Ry-Kottoh, 2022. "Organizational ambidexterity and financial performance in the banking industry: evidence from a developing economy," Journal of Financial Services Marketing, Palgrave Macmillan, vol. 27(3), pages 250-263, September.
    11. Carolina Rojas-Córdova & Amanda J. Williamson & Julio A. Pertuze & Gustavo Calvo, 2023. "Why one strategy does not fit all: a systematic review on exploration–exploitation in different organizational archetypes," Review of Managerial Science, Springer, vol. 17(7), pages 2251-2295, October.
    12. Karl Aschenbrücker & Tobias Kretschmer, 2022. "Performance-based incentives and innovative activity in small firms: evidence from German manufacturing," Journal of Organization Design, Springer;Organizational Design Community, vol. 11(2), pages 47-64, June.
    13. François Constant & Richard Calvi & Thomas Johnsen, 2020. "Managing tensions between exploitative and exploratory innovation through purchasing function ambidexterity Managing tensions between exploitative and exploratory innovation through purchasing functio," Post-Print hal-02891790, HAL.
    14. Schnellbächer, Benedikt & Heidenreich, Sven & Wald, Andreas, 2019. "Antecedents and effects of individual ambidexterity – A cross-level investigation of exploration and exploitation activities at the employee level," European Management Journal, Elsevier, vol. 37(4), pages 442-454.
    15. Marina Estrada-Cruz & Noelia Rodriguez-Hernández & Antonio J. Verdú-Jover & Jose Maria Gómez-Gras, 2022. "The effect of competitive intensity on the relationship between strategic entrepreneurship and organizational results," International Entrepreneurship and Management Journal, Springer, vol. 18(1), pages 1-24, March.
    16. Zhi Yang & Xuemin Zhou & Pengcheng Zhang, 2015. "Discipline versus passion: Collectivism, centralization, and ambidextrous innovation," Asia Pacific Journal of Management, Springer, vol. 32(3), pages 745-769, September.
    17. Gayoung Kim & Woo Jin Lee & Hoshik Shim, 2022. "Managerial Dilemmas and Entrepreneurial Challenges in the Ambidexterity of SMEs: A Systematic Review for Execution System," Sustainability, MDPI, vol. 14(24), pages 1-22, December.
    18. Fourné, Sebastian P.L. & Rosenbusch, Nina & Heyden, Mariano L.M. & Jansen, Justin J.P., 2019. "Structural and contextual approaches to ambidexterity: A meta-analysis of organizational and environmental contingencies," European Management Journal, Elsevier, vol. 37(5), pages 564-576.
    19. Jürgen Weibler & Tobias Keller, 2011. "Ambidextrie in Abhängigkeit von Führungsverantwortung und Marktwahrnehmung: Eine empirische Analyse des individuellen Arbeitsverhaltens in Unternehmen," Schmalenbach Journal of Business Research, Springer, vol. 63(2), pages 155-188, March.
    20. Marina Estrada-Cruz & Noelia Rodriguez-Hernández & Antonio J. Verdú-Jover & Jose Maria Gómez-Gras, 0. "The effect of competitive intensity on the relationship between strategic entrepreneurship and organizational results," International Entrepreneurship and Management Journal, Springer, vol. 0, pages 1-24.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:1319-1348. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.