Source author record

Fatma Kilinc-Karzan

Fatma Kilinc-Karzan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.OC

Catalog footprint

What is connected

4works

1topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Dynamic Data-Driven Estimation of Non-Parametric Choice Models

We study non-parametric estimation of choice models, which were 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, they are not equipped with explicit convergence rate guarantees, and consequently they cannot provide an a priori analysis for the model accuracy vs sparsity trade-off on the actual estimated model returned by their algorithms. As opposed to this, we focus on estimating a non-parametric choice model from observational data in a \emph{dynamic} setting, where observations are obtained over time. We show that choice model estimation can be cast as a convex-concave saddle-point (SP) joint estimation and optimization (JEO) problem, and we provide a primal-dual framework for deriving algorithms to solve this based on online convex optimization. By tailoring our framework carefully to the choice model estimation problem, we obtain tractable algorithms with provable convergence guarantees and explicit bounds on the sparsity of the estimated model. Our numerical experiments confirm the effectiveness of the algorithms derived from our framework.

preprint2020arXiv

On convex hulls of epigraphs of QCQPs

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditions for a convex hull result that immediately implies that the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the convex hull result holds whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. Our results also imply new sufficient conditions for the tightness (as well as convex hull exactness) of a second order cone program relaxation of simultaneously diagonalizable QCQPs.

preprint2016arXiv

How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic

A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown---by several authors using different techniques---that the convex hull of the intersection of an ellipsoid, $E$, and a split disjunction, $(l - x_j)(x_j - u) \le 0$ with $l < u$, equals the intersection of $E$ with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form $K \cap Q$ and $K \cap Q \cap H$, where $K$ is a SOCr cone, $Q$ is a nonconvex cone defined by a single homogeneous quadratic, and $H$ is an affine hyperplane. Under several easy-to-verify conditions, we derive simple, computable convex relaxations $K \cap S$ and $K \cap S \cap H$, where $S$ is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.

preprint2014arXiv

Two-Term Disjunctions on the Second-Order Cone

Balas introduced disjunctive cuts in the 1970s for mixed-integer linear programs. Several recent papers have attempted to extend this work to mixed-integer conic programs. In this paper we study the structure of the convex hull of a two-term disjunction applied to the second-order cone, and develop a methodology to derive closed-form expressions for convex inequalities describing the resulting convex hull. Our approach is based on first characterizing the structure of undominated valid linear inequalities for the disjunction and then using conic duality to derive a family of convex, possibly nonlinear, valid inequalities that correspond to these linear inequalities. We identify and study the cases where these valid inequalities can equivalently be expressed in conic quadratic form and where a single inequality from this family is sufficient to describe the convex hull. In particular, our results on two-term disjunctions on the second-order cone generalize related results on split cuts by Modaresi, Kilinc, and Vielma, and by Andersen and Jensen.