The facets of the polyhedral set determined by the Gale—Hoffman inequalities

The Gale—Hoffman inequalities characterize feasible external flow in a (capacitated) network. Among these inequalities, those that are redundant can be identified through a simple arc-connectedness criterion.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by NATO Collaborative Research Grant 0785/87.Supported in part by a grant of the Air Force Office of Scientific Research.     

Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

The aggregation closure is polyhedral for packing and covering integer programs

Mathematical Programming - Recently, Bodur, Del Pia, Dey, Molinaro and Pokutta studied the concept of aggregation cuts for packing and covering integer programs. The aggregation closure is the...     

On the continuity of the minimum in parametric quadratic programs

This paper establishes results on the lower semicontinuity and continuity of the optimal objective value of a parametric quadratic program with continuous dependence of the coefficients on parameters. The results established herein generalize directly well-known results on parametric linear programs.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.     

Lipschitzian stability of parametric variational inequalities over perturbed polyhedral convex sets

In this paper we investigate the Lipschitz-like property of the solution mapping of parametric variational inequalities over perturbed polyhedral convex sets. By establishing some lower and upper estimates for the coderivatives of the solution mapping, among other things, we prove that the solution mapping could not be Lipschitz-like around points where the positive linear independence condition is invalid. Our analysis is based heavily on the Mordukhovich criterion (Mordukhovich in Variational Analysis and Generalized Differentiation. vol. I: Basic Theory, vol. II: Applications. Springer, Berlin, 2006) of the Lipschitz-like property for set-valued mappings between Banach spaces and recent advances in variational analysis. The obtained result complements the corresponding ones of Nam (Nonlinear Anal 73:2271–2282, 2010) and Qui (Nonlinear Anal 74:1674–1689, 2011).     

A polyhedral study of nonconvex quadratic programs with box constraints

By reformulating quadratic programs using necessary optimality conditions, we obtain a linear program with complementarity constraints. For the case where the only constraints are bounds on the variables, we study a relaxation based on a subset of the optimality conditions. By characterizing its convex hull, we obtain a large class of valid inequalities. These inequalities are used in a branch-and-cut scheme, see [13].Mathematics Subject Classification (2000): 90C26, 90C27, 90C20     

Sub-Riemannian constant mean curvature surfaces in the Heisenberg group as limits

The 3-dimensional Heisenberg group H together with its standard sub-Riemannian metric g₀ is viewed as the limit of a family of Riemannian manifolds, (H,g_u), u>0. For each u>0, we consider some invariant surfaces with constant mean curvature in (H,g_u). These surfaces of (H,g_u) have very nice limits as u0. We then define the mean curvature of a hypersurface in (H,g₀) to be the limit of its mean curvature in (H,g_u). We show that in a more general case, this definition is appropriate. Mathematics Subject Classification (2000) Principal 53C17; Secondary 22E25     

Smooth representation of a parametric polyhedral convex set with application to sensitivity in optimization

We show in this paper that if a polyhedral convex set is defined by a parametric linear system with smooth entries, then it possesses local smooth representation almost everywhere. This result is then applied to study the differentiability of the solutions and the marginal functions of several classes of parametric optimization problems.

     

The Hoffman number of a graph

For a connected graph G with n vertices, let {λ₁,λ₂,…,λ_r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ₁λ₂…λ_r/n. In this paper, we study some properties and applications of the Hoffman number.     

Upper and lower bounds for the Voronoi-Minkowski constant

We study the behavior of the constant C(s) as s → ∞ arising in the estimate of the number of relative minima of s-dimensional integer lattices Γ via the logarithm log₂ N raised to the s ? 1th power, where N = D(Γ) is the determinant of Γ.     

常维码的一个构造性下界

推广了Etzion和Vardy关于常维码的结论（Etzion T,Vardy A.Error-correcting codes in projective space.IEEE Transactions on Information Theory,2011,57（2）：1165-1173）,给出了一般情况下常维码的一个构造性下界.     

Distribution functions in stochastic programs with recourse: A parametric analysis

This paper studies the behavior of the optimum value of a two-stage stochastic program with recourse (random right-hand sides) as the mean and covariance matrices defining the random variables in the program are perturbed. Several results for convex programs are developed and are used to study the effect such perturbations have on the regularity properties of the stochastic programs. Cost associated with incorrectly specifying the mean and covariance matrices are discussed and estimated. A stochastic programming model in which the random variable is dependent on the first-stage decision is presented.     

A new lower bound for the de Bruijn-Newman constant

Summary Strong numerical evidence is presented for a new lower bound for the so-called de Bruijn-Newman constant. This constant is related to the Riemann hypothesis. The new bound, –5, is suggested by high-precision floatingpoint computations, with a mantissa of 250 decimal digits, of i) the coefficients of a so-called Jensen polynomial of degree 406, ii) the so-called Sturm sequence corresponding to this polynomial which implies that it has two complex zeros, and iii) the two complex zoros of this polynomial. Aproof of the new bound could be given if one would repeat the computations i) and iii) with a floatingpoint accuracy of at least 2600 decimal digits.     

On positiveness of the fundamental solution of a difference equation

We obtain sharp and effective conditions of positiveness of the fundamental solution for linear scalar difference equations. Two approaches are realized, namely, an analytic one (in terms of properties of the characteristic equation) and a geometric one (in terms of a domain in the parameter space of the problem).