Rooting Out Self-Intersection: An Algebraic Shape-Optimization Barrier

Categories Applications - Science and Engineering, Multidisciplinary Design Optimization, Nonlinear Optimization Tags , , ,

Self-intersection is a fundamental feasibility constraint in shape optimization: a self-crossing boundary leaves its interior, normal field, and finite-element mesh ill-defined, yet most existing barriers rely on heuristic geometric-proximity measures rather than certifying self-intersection directly. We propose a self-intersection barrier grounded in algebraic detection. We derived two bivariate polynomials from a curve’s Fourier coefficients whose … Read more

Nonconvex stochastic zeroth-order optimization with decision-dependent distributions: from momentum tracking to coupled sampling

Categories Nonlinear Optimization, Stochastic Programming, Unconstrained Optimization

In this paper, we study nonconvex stochastic optimization with {decision-dependent distributions}, where the decision variable influences the underlying sampling distribution and only stochastic function-value feedback is available. We address two challenges {induced by decision-dependent distributions}: transport error in momentum-based gradient tracking and variance inflation in zeroth-order estimation. We first develop a Polyak-momentum zeroth-order method that … Read more

Dantzig-Wolfe Decomposition for Monotone Two-Stage Stochastic Mixed-Integer Programs Applied to a Power Distribution System Resilience Problem

Categories Stochastic Programming Tags , , , , ,

We develop a novel Dantzig-Wolfe (DW) decomposition algorithm for monotone two-stage stochastic mixed-integer programs (SMIPs). The key novelty in this algorithm is to relax the non-anticipativity constraints (NACs) in line with the monotonicity in the problem. We prove (i) that the relaxed restricted master problem (RMP) faster identifies dominated columns that cannot improve the RMP … Read more

An optimal orbit design for LISA

Categories Constrained Nonlinear Optimization, Multidisciplinary Design Optimization, Optimization of Systems modeled by PDEs Tags , ,

The ESA/NASA joint LISA (laser interferometer space antenna) mission is designed to detect gravitational waves to perform gravitational astronomy. A key mission requirement is the maintenance of a three-spacecraft constellation in a near-equilateral triangular configuration with a prescribed inter-spacecraft separation. Existing approaches have addressed this problem using simplified dynamical models to enhance tractability; however, the … Read more

Calculus of the facial distance

Categories Convex and Nonsmooth Optimization, Polyhedra Tags , ,

We develop a few calculus rules to compute or lower bound the facial distance of a polytope. We illustrate our calculus rules on various popular polytopes. In particular, we provide a lower bound on the facial distance of the Birkhoff polytope. CitationWorking paper. Tepper School of Business. Carnegie Mellon UniversityArticleDownload View PDF

Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization

Categories Global Optimization Theory, Semi-definite Programming Tags

We study the convergence rate of the moment-SOS (sum-of-squares) hierarchy for polynomial optimization problems (POPs) on a bounded subset of the real line described by arbitrary polynomial inequalities. We prove that, for every fixed univariate POP, the relaxation error is bounded by $O(1/r^2)$, where $r$ is the relaxation order. In particular, boundary degeneracies in the … Read more

On the Equivalence of Monge and Kantarovich Problems in Discrete Optimal Transport

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization of Systems modeled by PDEs

Consider a discrete optimal transport problem that has at least two consumers. We show that the Monge and Kantorovich versions of such a discrete optimal transport problem are equivalent for all cost functions if and only if the supply from all the suppliers are equal, and the demand from every consumer is an integral multiple … Read more

Fixed charges of arbitrary sign: what survives and what fails

Categories (Mixed) Integer Linear Programming, Polyhedra, Production and Logistics Tags , , , ,

For integer activities, conditioning on the support makes a fixed-charge objective affine. If every support-conditioned cell is integral, an optimal solution is a vertex of its cell for arbitrary fixed charges and marginal rates. A totally unimodular constraint matrix with integral data guarantees this condition. This surviving property is weaker than the classical conclusions. A … Read more

Symmetry-dependence in Rounding of a Convex Body

Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Polyhedra Tags , , , ,

The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \[ \mathrm{sym}(S):=\max\{\alpha\ge0:\text{ there exists }x\in S\text{ such that } -\alpha(S-x)\subseteq S-x\}\,, \]where such an \(x\) is called a Minkowski center. We prove that every convex body \(S\) admits a \(\sqrt{\frac{n}{\mathrm{sym}(S)}}\)-rounding of \(S\), namely, there exists an origin-centered ellipsoid \(E\) and a center \(c\) such … Read more

Radial-type error bounds for semidefinite feasibility problems without strict feasibility: qualitative estimates and asymptotic tightness

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

In this paper, we develop a systematic framework for deriving explicit error bounds for semidefinite feasibility problems without assuming strict feasibility (Slater’s condition), a setting in which existing results are limited. Our main technical contribution is the introduction of radial-type H\”{o}lder error bounds, where the error bound constant depends explicitly on the norm of the … Read more