Source author record

Emily Speakman

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC Other Computer Science

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Constructing lattice-free gradient polyhedra in dimension two

Lattice-free gradient polyhedra can be used to certify optimality for mixed-integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables under the assumption that all level sets are bounded. A classic result of Bell, Doignon, and Scarf states that a lattice-free gradient polyhedron with at most four facets exists in this setting. We present an algorithm for creating a sequence of gradient polyhedra, each of which has at most four facets, that finitely converges to a lattice-free gradient polyhedron. Each update requires constantly many gradient evaluations. Our updates imitate the gradient descent algorithm, and consequently, it yields a gradient descent type of algorithm for problems with two integer variables.

preprint2020arXiv

Gaining or losing perspective

We study MINLO (mixed-integer nonlinear optimization) formulations of the disjunction $x\in\{0\}\cup[l,u]$ , where $z$ is a binary indicatorof $x\in[l,u]$ ( $u> \ell > 0$ ), and $y$ "captures" $f(x)$ , which is assumed to be convex on its domain $[l,u]$ , but otherwise $y=0$ when $x=0$ . This model is useful when activities have operating ranges, we pay a fixed cost for carrying out each activity, and costs on the levels of activities are convex. Using volume as a measure to compare convex bodies, we investigate a variety of continuous relaxations of this model, one of which is the convex-hull, achieved via the "perspective reformulation" inequality $y \geq zf(x/z)$ . We compare this to various weaker relaxations, studying when they may be considered as viable alternatives. In the important special case when $f(x) := x^p$ , for $p>1$ , relaxations utilizing the inequality $yz^q \geq x^p$ , for $q \in [0,p-1]$ , are higher-dimensional power-cone representable, and hence tractable in theory. One well-known concrete application (with $f(x) := x^2$ ) is mean-variance optimization (in the style of Markowitz), and we carry out some experiments to illustrate our theory on this application.

preprint2020arXiv

Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions

We study MINLO (mixed-integer nonlinear optimization) formulations of the disjunction $x\in\{0\}\cup[\ell,u]$ , where $z$ is a binary indicator of $x\in[\ell,u]$ ( $0 \leq \ell <u$ ), and $y$ "captures" $f(x)$ , which is assumed to be convex and positive on its domain $[\ell,u]$ , but otherwise $y=0$ when $x=0$ . This model is very useful in nonlinear combinatorial optimization, where there is a fixed cost of operating an activity at level $x$ in the operating range $[\ell,u]$ , and then there is a further (convex) variable cost $f(x)$ . In particular, we study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of $f$ , obtained by choosing linearization points for $f$ . Using 3-d volume (in $(x,y,z)$ ) as a measure of the tightness of a convex relaxation, we investigate relaxation quality as a function of $f$ , $\ell$ , $u$ , and the linearization points chosen. We make a detailed investigation for convex power functions $f(x):=x^p$ , $p>1$ .

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.

Emily Speakman

Research overview

Is this your work?

3 publications

Constructing lattice-free gradient polyhedra in dimension two

Gaining or losing perspective

Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions

See the researcher in context

Building this map preview