In this paper we show that the diameter of a d-dimensional lattice polytope in [0,k]^n is at most (k – 1/2) d. This result implies that the diameter of a d-dimensional half-integral polytope is at most 3/2 d. We also show that for half-integral polytopes the latter bound is tight for any d. Citation University … Read more
A framework is developed for applying accelerated methods to general hyperbolic programming, including linear, second-order cone, and semidefinite programming as special cases. The approach replaces a hyperbolic program with a convex optimization problem whose smooth objective function is explicit, and for which the only constraints are linear equations (one more linear equation than for the … Read more
We study large scale extended trust region subproblems (eTRS) i.e., the minimization of a general quadratic function subject to a norm constraint, known as the trust region subproblem (TRS) but with an additional linear inequality constraint. It is well known that strong duality holds for the TRS and that there are efficient algorithms for solving … Read more
The Barzilai-Borwein method, an effective gradient descent method with clever choice of the step-length, is adapted from nonlinear optimization to Riemannian manifold optimization. More generally, global convergence of a nonmonotone line-search strategy for Riemannian optimization algorithms is proved under some standard assumptions. By a set of numerical tests, the Riemannian Barzilai-Borwein method with nonmonotone line-search … Read more
Stochastic mixed-integer programs (SMIPs) deal with optimization under uncertainty at many levels of the decision-making process. When solved as extensive formulation mixed- integer programs, problem instances can exceed available memory on a single workstation. To overcome this limitation, we present PIPS-SBB: a distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels … Read more
In a common formulation of semi-infinite programs, the infinite constraint set is a requirement that a function parametrized by the decision variables is nonnegative over an interval. If this function is sufficiently closely approximable by a polynomial or a rational function, then the semi-infinite program can be reformulated as an equivalent semidefinite program. Solving this … Read more
We study a maritime fleet renewal and deployment problem under demand and charter cost uncertainty. A decision-maker for an industrial bulk shipping company must determine a suitable fleet size, mix, and deployment strategy to satisfy stochastic demand over a given planning horizon. She may acquire vessels in two ways: time chartering and voyage chartering. Time … Read more
We propose a simple {\em projection and algorithm} to solve the feasibility problem \[ \text{ find } x \in L \cap \Omega, \] where $L$ and $\Omega$ are respectively a linear subspace and the interior of a symmetric cone in a finite-dimensional vector space $V$. This projection and rescaling algorithm is inspired by previous work … Read more
It is known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case the algorithm’s rate of convergence is determined by condition number of the function. In a similar vein, it has been shown that a variant of the Frank-Wolfe algorithm with away steps converges … Read more
In radiation therapy planning, uncertainties in target volume definition yield a risk of underdosing the tumor. The classical way to prevent this in the context of external beam radiotherapy (EBRT) has been to expand the clinical target volume (CTV) with an isotropic margin to obtain the planning target volume (PTV). However, the EBRT-based PTV concept … Read more