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
    ---><---

    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. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. O'Reilly, Charles A., III & Tushman, Michael L., 2013. "Organizational Ambidexterity: Past, Present and Future," Research Papers 2130, Stanford University, Graduate School of Business.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. 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.
    20. 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.
    21. 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.
    22. 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.
    23. 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.
    24. 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.
    25. 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.
    26. Zeki Simsek, 2009. "Organizational Ambidexterity: Towards a Multilevel Understanding," Journal of Management Studies, Wiley Blackwell, vol. 46(4), pages 597-624, June.
    27. 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.
    28. 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.
    29. 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.
    30. 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. Ú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.
    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. 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.
    5. 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.
    6. 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.
    7. Sunkee Lee & Philipp Meyer-Doyle, 2017. "How Performance Incentives Shape Individual Exploration and Exploitation: Evidence from Microdata," Organization Science, INFORMS, vol. 28(1), pages 19-38, February.
    8. Johannes Luger & Sebastian Raisch & Markus Schimmer, 2018. "Dynamic Balancing of Exploration and Exploitation: The Contingent Benefits of Ambidexterity," Organization Science, INFORMS, vol. 29(3), pages 449-470, June.
    9. Sebastian Raisch & Michael L. Tushman, 2016. "Growing New Corporate Businesses: From Initiation to Graduation," Organization Science, INFORMS, vol. 27(5), pages 1237-1257, October.
    10. Hughes, Paul & Hughes, Matthew & Stokes, Peter & Lee, Hanna & Rodgers, Peter & Degbey, William Y., 2020. "Micro-foundations of organizational ambidexterity in the context of cross-border mergers and acquisitions," Technological Forecasting and Social Change, Elsevier, vol. 153(C).
    11. Wai Chuen Poon & Osman Mohamad & Wan Fadzilah Wan Yusoff , 2020. "Examining the Antecedents of Ambidextrous Behaviours in Promoting Creativity among SMEs in Malaysia," Global Business Review, International Management Institute, vol. 21(3), pages 645-662, June.
    12. Al-Atwi, Amer Ali & Amankwah-Amoah, Joseph & Khan, Zaheer, 2021. "Micro-foundations of organizational design and sustainability: The mediating role of learning ambidexterity," International Business Review, Elsevier, vol. 30(1).
    13. Koryak, Oksana & Lockett, Andy & Hayton, James & Nicolaou, Nicos & Mole, Kevin, 2018. "Disentangling the antecedents of ambidexterity: Exploration and exploitation," Research Policy, Elsevier, vol. 47(2), pages 413-427.
    14. Andreea N. Kiss & Dirk Libaers & Pamela S. Barr & Tang Wang & Miles A. Zachary, 2020. "CEO cognitive flexibility, information search, and organizational ambidexterity," Strategic Management Journal, Wiley Blackwell, vol. 41(12), pages 2200-2233, December.
    15. 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.
    16. 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.
    17. Katsuki Aoki & Miriam Wilhelm, 2017. "The Role of Ambidexterity in Managing Buyer–Supplier Relationships: The Toyota Case," Organization Science, INFORMS, vol. 28(6), pages 1080-1097, December.
    18. Jingoo Kang & Sang‐Joon Kim, 2020. "Performance implications of incremental transition and discontinuous jump between exploration and exploitation," Strategic Management Journal, Wiley Blackwell, vol. 41(6), pages 1083-1111, June.
    19. Sahi, Gurjeet Kaur & Gupta, Mahesh C. & Cheng, T.C.E., 2020. "The effects of strategic orientation on operational ambidexterity: A study of indian SMEs in the industry 4.0 era," International Journal of Production Economics, Elsevier, vol. 220(C).
    20. Katharina Stelzl & Maximilian Röglinger & Katrin Wyrtki, 0. "Building an ambidextrous organization: a maturity model for organizational ambidexterity," Business Research, Springer;German Academic Association for Business Research, vol. 0, pages 1-28.

    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.

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

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.