Optimization Online


An Algorithm for Stochastic Convex-Concave Fractional Programs with Applications to Production Efficiency and Equitable Resource Allocation

Cheolmin Kim(cheolminkim2019***at***u.northwestern.edu)
Sanjay Mehrotra(mehrotra***at***northwestern.edu )

Abstract: We propose an algorithm to solve convex and concave fractional programs and their stochastic counterparts in a common framework. Our approach is based on a novel reformulation that involves differences of square terms in the constraints, and subsequent employment of piecewise-linear approximations of the concave terms. Using the branch-and-bound framework, our algorithm adaptively refines the piecewise-linear approximations and iteratively solves convex approximation problems. The convergence analysis provides a bound on the optimality gap as a function of approximation errors. Based on this bound, we prove that the proposed branch-and-bound algorithm terminates in a finite number of iterations and the worst-case bound to obtain an $\epsilon$-optimal solution reciprocally depends on the square root of $\epsilon$. Numerical experiments on Cob-Douglas production efficiency and equitable resource allocation problems support that the algorithm efficiently finds a highly accurate solution. Specifically, it achieves five-digit accuracy for small size problem instances in reasonable amounts of time while benchmark algorithms only attain two or three digits of accuracy even after running for 12 hours. Moreover, our approaches based on a dual reformulation and a cutting surface algorithm solve the same size of distributionally robust Cob-Douglas production efficiency programs with a little extra computational effort.

Keywords: Fractional programming, Second order cone approximation, Branch and bound algorithm, Stochastic production efficiency problem, Equitable resource allocation

Category 1: Global Optimization

Category 2: Global Optimization (Stochastic Approaches )

Category 3: Global Optimization (Applications )


Download: [PDF]

Entry Submitted: 12/27/2021
Entry Accepted: 01/01/2022
Entry Last Modified: 12/27/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