Optimization Online


Robust Concave Utility Maximization over a Chance-Constraint

Shanshan Wang(shanshan.wang***at***hec.ca)
Sanjay Mehrotra(mehrotra***at***iems.northwestern.edu)

Abstract: This paper, for the first time, studies an expected utility problem with a chance constraint with incomplete information on a decision maker's utility function. The model maximizes the worst-case expected utility of random outcome over a set of concave functions within a novel ambiguity set while satisfying a chance constraint with a given probability. To obtain computationally tractable formulations, we employ a discretization approach to derive a max-min chance-constrained approximation of this problem. This approximation is further reformulated as a mixed-integer second-order cone program (MISOCP). We show that the discrete approximation asymptotically converges to the true counterpart under mild assumptions. We also present a row generation algorithm for optimizing the max-min program. In particular, the algorithm considers a master problem as a chance-constrained problem and a second-order cone program (SOCP) as subproblems. A computational study for a bin-packing problem and a multi-item newsvendor problem is conducted to demonstrate the performance of the proposed framework and the computational efficiency of our algorithm. We find that the row generation algorithm can significantly reduce the computational time.

Keywords: Robust expected utility, robust optimization, mixed-integer second-order cone program, chance constraint, row generation, bin packing, multi-item newsvendor

Category 1: Robust Optimization

Category 2: Stochastic Programming

Category 3: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 12/08/2021
Entry Accepted: 12/08/2021
Entry Last Modified: 12/08/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society