Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective

Jianzhe Zhen (), Ahmadreza Marandi (), Danique de Moor (), Dick den Hertog () and Lieven Vandenberghe ()
Additional contact information
Jianzhe Zhen: Department of Information Technology and Electrical Engineering, Eidgenössische Technische Hochschule Zürich, 8092 Zürich, Switzerland
Ahmadreza Marandi: Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, 5600 MB Eindhoven, North Brabant, Netherlands
Danique de Moor: Faculty of Economics and Business, Section Business Analytics, University of Amsterdam, 1012 WX Amsterdam, Netherlands
Dick den Hertog: Faculty of Economics and Business, Section Business Analytics, University of Amsterdam, 1012 WX Amsterdam, Netherlands
Lieven Vandenberghe: Electrical and Computer Engineering Department, University of California, Los Angeles, Los Angeles, California 90095

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2410-2427

Abstract: In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme. Summary of Contribution: Computing solutions for disjoint bilinear optimization problems are of much interest in real-life applications, yet they are, in general, computationally intractable. This paper proposes a computationally tractable approximation as well as a convergent algorithm to the optimal values of such problems. Extensive computational experiments on (i) (constrained) bimatrix games, (ii) synthetic disjoint bilinear problems, and (iii) convex maximization problems are conducted to demonstrate the effectiveness and efficiency of the proposed approach.

Keywords: bilinear optimization; linear decision rules; reformulation-linearization technique; mixed integer convex optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1163 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:5:p:2410-2427

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().