Dynamic Discretisation Discovery (DDD) is a framework for solving a problem by iteratively solving and refining a relaxed version of the problem. DDD is the basis for state-of-the-art algorithms for various problems, including the continuous-time service network design problem (CTSNDP), which we study here. In the refinement step, such algorithms must identify conflicts in the … Read more
Distributionally robust optimization (DRO) provides a principled framework for learning under distribution shift, but its practical use is hindered by the difficulty of evaluating worst-case risks for nonconvex loss functions. We study a penalized DRO formulation in which the adversary may choose any distribution but incurs a Wasserstein penalty for deviating from the empirical distribution. … Read more
We propose an algorithmic framework for solving adaptive robust optimization with provable guarantees on both tractability and solution accuracy. The framework introduces soft separation, a probabilistic mechanism for identifying worst-case uncertainty realizations via a time-inhomogeneous Markov chain. Rather than solving an exact separation problem in each iteration, which is intractable in general, the chain carries … Read more
We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central parameter for tractability: bounded treewidth yields polynomial-time solvability. Motivated by this fact, we investigate whether treewidth plays a similar role when the binary domain is replaced by the unit … Read more
This work studies how a generalized error bound (GEB) property in the ambient Euclidean space transfers to the active manifold under \(\mathcal{C}^1\) partial smoothness. The GEB generalizes the standard error bound, which upper bounds the distance to a subset of critical points using first-order stationarity residuals, by allowing the distance to be composed with a … Read more
Multistage stochastic programs model decisions under uncertainty where earlier decisions change later feasible sets. We propose a feasible pathwise gradient method (FeasPG) that can update the policy as new sample paths arrive. The policy proposes a decision and projects it onto the current feasible set, so every decision is feasible. We derive the full trajectory … Read more
We show that every polytope $P\subseteq[0,1]^n$, and more generally every compact convex set, has Chv\’atal rank at most $12.22n^2+n\log_2 n+2n+4$. This improves the $O(n^2\log n)$ bound of Eisenbrand and Schulz and, together with the $\Omega(n^2)$ lower bound of Rothvo{\ss} and Sanit\`a, shows that the maximum Chv\’atal rank of a polytope in $[0,1]^n$ is $\Theta(n^2)$. More … Read more
We consider the Lorentz positive cone of \(n \times m\) matrices that map the Lorentz cone in \(R^m\) into the Lorentz cone in \(R^n\). The Lorentz positive cone and its dual, the cone of Lorentz separable matrices, are shown to provide polynomial-time algorithms for the problem of minimizing a bilinear objective over variables contained in … Read more
In this paper, we propose and analyze an augmented Lagrangian framework for solving stochastic nonconvex optimization problems with expectation-based equality constraints over a closed and convex constraint set. The framework generates a sequence of nonconvex primal subproblems, which are solved inexactly using stochastic second-order methods. We establish iteration complexity results for obtaining approximate second-order stationary … Read more
This work examines three different concepts of objective redundancy in multiobjective optimization. Multiobjective optimization is known to suffer from the curse of dimensionality and we aim at reducing the number of objective functions which need to be considered. In this context, a set of objectives is called redundant if the sets of weakly efficient, efficient, … Read more