Fatma Kılınç-Karzan

Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens

  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we … Read more

    The Generalized Trust Region Subproblem: solution complexity and convex hull results

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Constrained Nonlinear Optimization, Quadratic Programming

    We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this … Read more

    Risk Guarantees for End-to-End Prediction and Optimization Processes

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Robust Optimization, Stochastic Programming

    Prediction models are often employed in estimating parameters of optimization models. Despite the fact that in an \emph{end-to-end} view, the real goal is to achieve good optimization performance, the prediction performance is measured on its own. While it is usually believed that good prediction performance in estimating the parameters will result in good subsequent optimization … Read more

    Dynamic Data-Driven Estimation of Non-Parametric Choice Models

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Convex Optimization, Marketing Tags , , ,

    We study non-parametric estimation of choice models, which was introduced to alleviate unreasonable assumptions in traditional parametric models, and are prevalent in several application areas. Existing literature focuses only on the static observational setting where all of the observations are given upfront, and lacks algorithms that provide explicit convergence rate guarantees or an a priori … Read more

    On Intersection of Two Mixing Sets with Applications to Joint Chance-Constrained Programs

  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Xiao Liu
    • Categories Integer Programming, Stochastic Programming

    We study the polyhedral structure of a generalization of a mixing set described by the intersection of two mixing sets with two shared continuous variables, where one continuous variable has a positive coefficient in one mixing set, and a negative coefficient in the other. Our developments are motivated from a key substructure of linear joint … Read more

    Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). … Read more

    Online First-Order Framework for Robust Convex Optimization

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Constrained Nonlinear Optimization, Robust Optimization Tags , , ,

    Robust optimization (RO) has emerged as one of the leading paradigms to efficiently model parameter uncertainty. The recent connections between RO and problems in statistics and machine learning domains demand for solving RO problems in ever more larger scale. However, the traditional approaches for solving RO formulations based on building and solving robust counterparts or … Read more

    Low-Complexity Relaxations and Convex Hulls of Disjunctions on the Positive Semidefinite Cone and General Regular Cones

  • Fatma Kılınç-Karzan
  • Sercan Yildiz
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    In this paper we analyze general two-term disjunctions on a regular cone $\K$ and derive a general form for a family of convex inequalities which are valid for the resulting nonconvex sets. Under mild technical assumptions, these inequalities collectively describe the closed convex hulls of these disjunctions, and if additional conditions are satisfied, a single … Read more

    A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Second-Order Cone Programming Tags , , , ,

    We study the trust region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective, it is known that the TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone based approach to derive an exact … Read more

    On Sublinear Inequalities for Mixed Integer Conic Programs

  • Fatma Kılınç-Karzan
  • Daniel E. Steffy
    • Categories (Mixed) Integer Linear Programming

    This paper studies $K$-sublinear inequalities, a class of inequalities with strong relations to K-minimal inequalities for disjunctive conic sets. We establish a stronger result on the sufficiency of $K$-sublinear inequalities. That is, we show that when $K$ is the nonnegative orthant or the second-order cone, $K$-sublinear inequalities together with the original conic constraint are always … Read more