Benders,metric and cutset inequalities for multicommodity capacitated network design

Solving multicommodity capacitated network design problems is a hard task that requires the use of several strategies like relaxing some constraints and strengthening the model with valid inequalities. In this paper, we compare three sets of inequalities that have been widely used in this context: Benders, metric and cutset inequalities. We show that Benders inequalities associated to extreme rays are metric inequalities. We also show how to strengthen Benders inequalities associated to non-extreme rays to obtain metric inequalities. We show that cutset inequalities are Benders inequalities, but not necessarily metric inequalities. We give a necessary and sufficient condition for a cutset inequality to be a metric inequality. Computational experiments show the effectiveness of strengthening Benders and cutset inequalities to obtain metric inequalities.     

Regularization of quasi-variational inequalities

An ill-posed quasi-variational inequality with contaminated data can be stabilized by employing the elliptic regularization. Under suitable conditions, a sequence of bounded regularized solutions converges strongly to a solution of the original quasi-variational inequality. Moreover, the conditions that ensure the boundedness of regularized solutions, become sufficient solvability conditions. It turns out that the regularization theory is quite strong for quasi-variational inequalities with set-valued monotone maps but restrictive for generalized pseudo-monotone maps. The results are quite general and are applicable to ill-posed variational inequalities, hemi-variational inequalities, inverse problems, and split feasibility problem, among others.     

Faces for a linear inequality in 0–1 variables

Given a linear inequality in 0–1 variables we attempt to obtain the faces of the integer hull of 0–1 feasible solutions. For the given inequality we specify how faces of a variety of lower-dimensional inequalities can be raised to give full-dimensional faces. In terms of a set, called a “strong cover”, we obtain necessary and sufficient conditions for any inequality with 0–1 coefficients to be a face, and characterize different forms that the integer hull must take. In general the suggested procedures fail to produce the complete integer hull. Special subclasses of inequalities for which all faces can be generated are demonstrated. These include the “matroidal” and “graphic” inequalities, where a count on the number of such inequalities is obtained, and inequalities where all faces can be derived from lower dimensional faces.     

Modified Logarithmic Sobolev Inequalities on $\mathbb{R}$

We provide a sufficient condition for a measure on the real line to satisfy a modified logarithmic Sobolev inequality, thus extending the criterion of Bobkov and Götze. Under mild assumptions the condition is also necessary. Concentration inequalities are derived. This completes the picture given in recent contributions by Gentil, Guillin and Miclo.     

Finite convergence of algorithms for nonlinear programs and variational inequalities

Algorithms for nonlinear programming and variational inequality problems are, in general, only guaranteed to converge in the limit to a Karush-Kuhn-Tucker point, in the case of nonlinear programs, or to a solution in the case of variational inequalities. In this paper, we derive sufficient conditions for nonlinear programs with convex feasible sets such that any convergent algorithm can be modified, by adding a convex subproblem with a linear objective function, to guarantee finite convergence in a generalized sense. When the feasible set is polyhedral, the subproblem is a linear program and finite convergence is obtained. Similar results are also developed for variational inequalities.The research of the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173.The authors are indebted to Professors Olvi Mangasarian, Garth McCormick, Jong-Shi Pang, Hanif Sherali, and Hoang Tuy for helpful comments and suggestions and to two anonymous referees for constructive remarks and for bringing to their attention the results in Refs. 13 and 14.     

A Unified Approach to Several Inequalities Involving Functions and Derivatives

There are many inequalities measuring the deviation of the average of a function over an interval from a linear combination of values of the function and some of its derivatives. A general setting is given from which the desired inequalities are obtained using Holder's inequality. Moreover, sharpness of the constants is usually easy to prove by studying the equality cases of Holder's inequality. Comparison of averages, extension to weighted integrals and n-dimensional results are also given.     

Convergence analysis of a modified inexact implicit method for general mixed monotone variational inequalities

We consider a useful modification of the inexact implicit method with a variable parameter in Wang et al. J Optim Theory 111: 431–443 (2001) for generalized mixed monotone variational inequalities. One of the contributions of the proposed method in this paper is that the restrictions imposed on the variable parameter are weaker than the ones in Wang et al. J Optim Theory 111: 431–443 (2001). Another contribution is that we establish a sufficient and necessary condition for the convergence of the proposed method to a solution of the general mixed monotone variational inequality.     

Redundante Ungleichungen bei linearen Ungleichungssystemen

Zusammenfassung Es wird ein allgemeines Kriterium für die Identifikation redundanter Ungleichungen bei linearen Ungleichungssystemen angegeben. Das Kriterium wird mit bekannten Kriterien verglichen, und es wird gezeigt, wie man es in einem Spezialfall auf einfache Weise anwenden kann.

---

Summary A general criterion for identification of redundant inequalities of linear inequality systems is given. The criterion is compared with other well-known criteria and it is shown by an example how it can be applied practically in a special case.

     

On the Gap Functions of Prevariational Inequalities

Gap functions play a crucial role in transforming a variational inequality problem into an optimization problem. Then, methods solving an optimization problem can be exploited for finding a solution of a variational inequality problem. It is known that the so-called prevariational inequality is closely related to some generalized convex functions, such as linear fractional functions. In this paper, gap functions for several kinds of prevariational inequalities are investigated. More specifically, prevariational inequalities, extended prevariational inequalities, and extended weak vector prevariational inequalities are considered. Furthermore, a class of gap functions for inequality constrained prevariational inequalities is investigated via a nonlinear Lagrangian.     

Exceptional Families and Existence Theorems for Variational Inequality Problems

This paper introduces the concept of exceptional family for nonlinear variational inequality problems. Among other things, we show that the nonexistence of an exceptional family is a sufficient condition for the existence of a solution to variational inequalities. This sufficient condition is weaker than many known solution conditions and it is also necessary for pseudomonotone variational inequalities. From the results in this paper, we believe that the concept of exceptional families of variational inequalities provides a new powerful tool for the study of the existence theory for variational inequalities.     

Weak logarithmic Sobolev inequalities and entropic convergence

In this paper we introduce and study a weakened form of logarithmic Sobolev inequalities in connection with various others functional inequalities (weak Poincaré inequalities, general Beckner inequalities, etc.). We also discuss the quantitative behaviour of relative entropy along a symmetric diffusion semi-group. In particular, we exhibit an example where Poincaré inequality can not be used for deriving entropic convergence whence weak logarithmic Sobolev inequality ensures the result.      

Wiener-hopf equations and variational inequalities

In this paper, we show that the general variational inequality problem is equivalent to solving the Wiener-Hopf equations. We use this equivalence to suggest and analyze a number of iterative algorithms for solving general variational inequalities. We also discuss the convergence criteria for these algorithms.     

Orlicz-Sobolev inequalities for sub-Gaussian measures and ergodicity of Markov semi-groups

We study coercive inequalities in Orlicz spaces associated to the probability measures on finite- and infinite-dimensional spaces which tails decay slower than the Gaussian ones. We provide necessary and sufficient criteria for such inequalities to hold and discuss relations between various classes of inequalities.     

Image Space Analysis for Vector Variational Inequalities with Matrix Inequality Constraints and Applications

In this paper, vector variational inequalities (VVI) with matrix inequality constraints are investigated by using the image space analysis. Linear separation for VVI with matrix inequality constraints is characterized by using the saddle-point conditions of the Lagrangian function. Lagrangian-type necessary and sufficient optimality conditions for VVI with matrix inequality constraints are derived by utilizing the separation theorem. Gap functions for VVI with matrix inequality constraints and weak sharp minimum property for the solutions set of VVI with matrix inequality constraints are also considered. The results obtained above are applied to investigate the Lagrangian-type necessary and sufficient optimality conditions for vector linear semidefinite programming problems as well as VVI with convex quadratic inequality constraints.     

A constructive algorithm for folding large-scale systems of linear inequalities

The conventional procedure for folding a system of linear inequalities based on the Fourier-Chernikov algorithm is supplemented with techniques for eliminating redundant inequalities, which considerably counteracts the increase in the system dimension. Exact and approximate methods are proposed, which are brought to algorithmic form and software implementation. Numerical results are discussed.     

Generalized Differential Properties of the Auslender Gap Function for Variational Inequalities

In this note, the Auslender gap function, which is used to formulate a variational inequality into an equivalent minimization problem, is shown to be differentiable in the generalized sense and has a lower contingent derivative under suitable conditions. This enables us to establish necessary and sufficient conditions for the existence of a solution to problems of variational inequalities.This research was partially supported by the National Natural Science Foundation of China and the Research Committee of Hong Kong Polytechnic University. Communicated by F. Giannessi     

Some complements to the Jensen and Chebyshev inequalities and a problem of W. Walter

Motivated by an integral inequality conjectured by W. Walter, we prove some general integral inequalities on finite intervals of the real line. In addition to supplying new proofs of Walter's conjecture, the general inequalities furnish a reverse Jensen inequality under appropriate conditions and provide generalizations of Chebyshev's integral inequality.     

Existence of Solutions and an Algorithm for Mixed Variational-Like Inequalities in Banach Spaces

In this paper, we study the class of mixed variational-like inequalities in reflexive Banach spaces. By applying a minimax inequality due to the author, some existence and uniqueness theorems for solutions of mixed variational-like inequalities are proved. Next, by applying the auxiliary problem technique, we suggest an innovative iterative algorithm to compute approximate solutions of the mixed variational-like inequality. Finally, convergence criteria are also discussed. This research was supported by NSF, Sichman Education Department of China, Projects 2003A081 and SZD0406. The author expresses his sincere thanks to Professor H.P. Benson and the anonymous referees for careful comments leading to the present version of this paper.     

基于LMIs的一类不确定线性切换系统的鲁棒控制

基于LMIs处理方法,研究了一类不确定线性切换系统在任意切换下的鲁棒控制问题.利用矩阵Schur补引理构造线性矩阵不等式,得到该系统的鲁棒稳定性的充要条件,同时也给出了在状态反馈下的鲁棒稳定性充要条件和在输出反馈下的充分条件.最后用数值例子对所得结果加以验证,说明了文中结果的正确性.     

Improved Hölder and reverse Hölder inequalities for Gaussian random vectors

We propose algebraic criteria that yield sharp Hölder types of inequalities for the product of functions of Gaussian random vectors with arbitrary covariance structure. While our lower inequality appears to be new, we prove that the upper inequality gives an equivalent formulation for the geometric Brascamp–Lieb inequality for Gaussian measures. As an application, we retrieve the Gaussian hypercontractivity as well as its reverse and we present a generalization of the sharp Young and reverse Young inequalities. From the latter, we recover several known inequalities in the literature including the Prékopa–Leindler and Barthe inequalities.