Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

An algorithm for the construction of convex hulls in simple integer recourse programming

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.     

On the convex hull of the simple integer recourse objective function

We consider the objective function of a simple integer recourse problem with fixed technology matrix.Using properties of the expected value function, we prove a relation between the convex hull of this function and the expected value function of a continuous simple recourse program.We present an algorithm to compute the convex hull of the expected value function in case of discrete right-hand side random variables. Allowing for restrictions on the first stage decision variables, this result is then extended to the convex hull of the objective function.Supported by the National Operations Research Network in the Netherlands (LNMB).     

Parametric error bounds for convex approximations of two-stage mixed-integer recourse models with a random second-stage cost vector

We consider two-stage recourse models with integer restrictions in the second stage. These models are typically non-convex and hence, hard to solve. There exist convex approximations of these models with accompanying error bounds. However, it is unclear how these error bounds depend on the distributions of the second-stage cost vector q. In this paper, we derive parametric error bounds whose dependence on the distribution of q is explicit: they scale linearly in the expected value of the ${?}_1$-norm of q.     

Widths and best approximations for classes of convolutions of periodic functions

We establish exact lower bounds for the Kolmogorov widths in the metrics ofC andL for classes of functions with high smoothness; the elements of these classes are sourcewise-representable as convolutions with generating kernels that can increase oscillations. We calculate the exact values of the best approximations of such classes by trigonometric polynomials. Institute of Mathematics, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 5, pp. 674–687, May, 1999.     

Convex approximations for a class of mixed-integer recourse models

We consider mixed-integer recourse (MIR) models with a single recourse constraint. We relate the second-stage value function of such problems to the expected simple integer recourse (SIR) shortage function. This allows to construct convex approximations for MIR problems by the same approach used for SIR models.     

Exact bounds for norms of differentiable periodic functions in L metric

Exact values are obtained for the upper bounds on the norms,fL, on the classes W ^(r) H(r =0, 1, 2,...) of r-fold differentiable functions f(x), of periodicity2, for which (f^(r);t)(t),where (t) is a given convex modulus of continuity.Translated from Matematicheskie Zametki, Vol. 2, No. 6, pp. 569–576, December, 1967.     

Certain exact bounds for seminorms given on spaces of periodic functions

Certain new bounds are established for the values of seminorms given on the spaces C and L^p (1p<) of periodic functions by means of the norm of the function itself and its finite differences, as well as of the moduli of continuity. These bounds are applied to concrete seminorms; in particular, to the best approximation, which yields a refinement of the direct theorems in approximation theory. The results obtained for spaces C and L¹ are exact.Translated from Matematicheskie Zametki, Vol. 21, No. 6, pp. 789–798, June, 1977.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

Nonlinear approximations of classes of periodic functions of many variables

Order-sharp estimates are established for the best N-term approximations of functions in the classes $B_{pq}^{sm} (\mathbb{T}^k )$ and $L_{pq}^{sm} (\mathbb{T}^k )$ of Nikol’skii-Besov and Lizorkin-Triebel types with respect to the multiple system of Meyer wavelets in the metric of $L_r (\mathbb{T}^k )$ for various relations between the parameters s, p, q, r, and m (s = (s ₁, ..., s _n ) ∈ ? ₊ ⁿ , 1 ≤ p, q, r ≤ ∞, m = (m ₁, ..., m _n ) ∈ ? ⁿ , and k = m ₁ + ... + m _n ). The proof of upper estimates is based on variants of the so-called greedy algorithms.     

On uniform approximations of almost periodic functions by entire functions of finite degree

We give a new proof of the well-known Bernshtein statement that, among entire functions of degree which realize the best uniform approximation (of degree ) of a periodic function on (–,), there is a trigonometric polynomial of degree . We prove an analog of the mentioned Bernshtein statement and the Jackson theorem for uniform almost periodic functions with arbitrary spectrum.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 9, pp. 1274–1279, September, 1995.