An oracle-based projection and rescaling algorithm for linear semi-infinite feasibility problems and its application to SDP and SOCP

We point out that Chubanov’s oracle-based algorithm for linear programming [5] can be applied almost as it is to linear semi-infinite programming (LSIP). In this note, we describe the details and prove the polynomial complexity of the algorithm based on the real computation model proposed by Blum, Shub and Smale (the BSS model) which is … Read more

Robust-to-Dynamics Optimization

A robust-to-dynamics optimization (RDO) problem} is an optimization problem specified by two pieces of input: (i) a mathematical program (an objective function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ and a feasible set $\Omega\subseteq\mathbb{R}^n$), and (ii) a dynamical system (a map $g:\mathbb{R}^n\rightarrow\mathbb{R}^n$). Its goal is to minimize $f$ over the set $\mathcal{S}\subseteq\Omega$ of initial conditions that forever remain in $\Omega$ under … Read more

Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints

Discretization-based algorithms are proposed for the global solution of mixed-integer nonlinear generalized semi-infinite (GSIP) and bilevel (BLP) programs with lower-level equality constraints coupling the lower and upper level. The algorithms are extensions, respectively, of the algorithm proposed by Mitsos and Tsoukalas (J Glob Optim 61(1):1–17, 2015. and by Mitsos (J Glob Optim 47(4):557–582, 2010. … Read more

A transformation-based discretization method for solving general semi-infinite optimization problems

Discretization methods are commonly used for solving standard semi-infinite optimization (SIP) problems. The transfer of these methods to the case of general semi-infinite optimization (GSIP) problems is difficult due to the $x$-dependence of the infinite index set. On the other hand, under suitable conditions, a GSIP problem can be transformed into a SIP problem. In … Read more

Revisiting Approximate Linear Programming Using a Saddle Point Approach

Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs) arising in applications. VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost, which can be used to assess the suboptimality of heuristic policies. However, … Read more

Decomposition Algorithms for Distributionally Robust Optimization using Wasserstein Metric

We study distributionally robust optimization (DRO) problems where the ambiguity set is de ned using the Wasserstein metric. We show that this class of DRO problems can be reformulated as semi-in nite programs. We give an exchange method to solve the reformulated problem for the general nonlinear model, and a central cutting-surface method for the convex case, … Read more

Optimal scenario generation and reduction in stochastic programming

Scenarios are indispensable ingredients for the numerical solution of stochastic optimization problems. Earlier approaches for optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based on distances containing minimal information, i.e., on data appearing … Read more

The structure of the infinite models in integer programming

The infinite models in integer programming can be described as the convex hull of some points or as the intersection of half-spaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to … Read more

Moment methods in energy minimization: New bounds for Riesz minimal energy problems

We use moment methods to construct a converging hierarchy of optimization problems to lower bound the ground state energy of interacting particle systems. We approximate the infinite dimensional optimization problems in this hierarchy by block diagonal semidefinite programs. For this we develop the necessary harmonic analysis for spaces consisting of subsets of another space, and … Read more

A Hybrid Discretization Algorithm with Guaranteed Feasibility for the Global Solution of Semi-Infinite Programs

A discretization-based algorithm for the global solution of semi-infinite programs (SIPs) is proposed, which is guaranteed to converge to a feasible, ε-optimal solution finitely under mild assumptions. The algorithm is based on the hybridization of two existing algorithms. The first algorithm (Mitsos in Optimization 60(10–11):1291–1308, 2011) is based on a restriction of the right-hand side … Read more