Lagrange Multipliers and mixed formulations for some inequality constrained variational inequalities and some nonsmooth unilateral problems

Abstract

This paper addresses a class of inequality constrained variational inequalities and nonsmooth unilateral variational problems. We present mixed formulations arising from Lagrange multipliers. First we treat in a reflexive Banach space setting the canonical case of a variational inequality that has as essential ingredients a bilinear form and a non-differentiable sublinear, hence convex functional and linear inequality constraints defined by a convex cone. We extend the famous Brezzi splitting theorem that originally covers saddle point problems with equality constraints, only, to these nonsmooth problems and obtain independent Lagrange multipliers in the subdifferential of the convex functional and in the ordering cone of the inequality constraints. For illustration of the theory we provide and investigate an example of a scalar nonsmooth boundary value problem that models frictional unilateral contact problems in linear elastostatics. Finally we discuss how this approach to mixed formulations can be further extended to variational problems with nonlinear operators and equilibrium problems, and moreover, to hemivariational inequalities.     

Dynamical systems and variational inequalities

The variational inequality problem has been utilized to formulate and study a plethora of competitive equilibrium problems in different disciplines, ranging from oligopolistic market equilibrium problems to traffic network equilibrium problems. In this paper we consider for a given variational inequality a naturally related ordinary differential equation. The ordinary differential equations that arise are nonstandard because of discontinuities that appear in the dynamics. These discontinuities are due to the constraints associated with the feasible region of the variational inequality problem. The goals of the paper are two-fold. The first goal is to demonstrate that although non-standard, many of the important quantitative and qualitative properties of ordinary differential equations that hold under the standard conditions, such as Lipschitz continuity type conditions, apply here as well. This is important from the point of view of modeling, since it suggests (at least under some appropriate conditions) that these ordinary differential equations may serve as dynamical models. The second goal is to prove convergence for a class of numerical schemes designed to approximate solutions to a given variational inequality. This is done by exploiting the equivalence between the stationary points of the associated ordinary differential equation and the solutions of the variational inequality problem. It can be expected that the techniques described in this paper will be useful for more elaborate dynamical models, such as stochastic models, and that the connection between such dynamical models and the solutions to the variational inequalities will provide a deeper understanding of equilibrium problems.     

Formulation and analysis of horizontal mergers among oligopolistic firms with insights into the merger paradox: a supply chain network perspective

In this paper, we consider oligopolistic firms with supply chain networks who are involved in the production, storage, and distribution of a homogeneous product to demand markets and explore what has become known in the literature as the “merger paradox.” We present the oligopolistic supply chain network equilibrium model associated with the competing firms before the horizontal mergers and also develop the supply chain network optimization model post the complete merger. In addition, we develop the model in which only a subset of the firms in the industry merge. The governing concept of the competing firms is that of Cournot–Nash equilibrium. We utilize finite-dimensional variational inequality theory for the formulation, analysis, and solution of both the pre and the post-merger supply chain network problems. We provide numerical examples for which we compute the total costs, the total revenues, as well as the profits obtained for the firms pre and post the mergers for a variety of distinct oligopoly problems. The generality of the network models and the flexibility of the computational approach, which yields closed form expressions for the product flows at each iteration, allows us to obtain deeper insights into the merger paradox.     

Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints

In this paper we consider heuristic algorithms for a special case of the generalized bilevel mathematical programming problem in which one of the levels is represented as a variational inequality problem. Such problems arise in network design and economic planning. We obtain derivative information needed to implement these algorithms for such bilevel problems from the theory of sensitivity analysis for variational inequalities. We provide computational results for several numerical examples.     

A path-based double projection method for solving the asymmetric traffic network equilibrium problem

In this paper we propose a new iterative method for solving the asymmetric traffic equilibrium problem when formulated as a variational inequality whose variables are the path flows. The path formulation leads to a decomposable structure of the constraints set and allows us to obtain highly accurate solutions. The proposed method is a column generation scheme based on a variant of the Khobotov’s extragradient method for solving variational inequalities. Computational experiments have been carried out on several networks of a medium-large scale. The results obtained are promising and show the applicability of the method for solving large-scale equilibrium problems. This work has been supported by the National Research Program FIRB/RBNE01WBBBB on Large Scale Nonlinear Optimization.     

Noncompliant oligopolistic firms and marketable pollution permits: Statics and dynamics

In this paper, we consider the modeling, analysis, and computation of solutions to both static and dynamic models of multiproduct, multipollutant noncompliant oligopolistic firms who engage in a market for pollution permits. In the case of the static model, we utilize variational inequality theory for the formulation of the governing equilibrium conditions as well as the qualitative analysis of the equilibrium pattern, including sensitivity analysis. We then propose a dynamic model, using the theory of projected dynamical systems, whose set of stationary points coincides with the set of solutions to the variational inequality problem. We propose an algorithm, which is a discretization in time of the dynamic adjustment process, and provide convergence results using the stability analysis results that are also provided herein. Finally, we apply the algorithm to several numerical examples to compute the profit-maximized quantities of the oligopolistic firms' products and the quantities of emissions, along with the equilibrium allocation of licenses and their prices, as well as the possible noncompliant overflows and underflows. This is the first time that these methodologies have been utilized in conjunction to study a problem drawn from environmental policy modeling and analysis.     

Implementation of the Nitsche approach for various contact kinematics

Numerical approaches are in case of contact problems mainly dealing with additional terms enforcing constraints. Within the Nitsche approach the inclusion of constraints for the non-penetration and equilibrium of stresses of the contacting bodies is carried out in a fully variational sense. Taking into account a specific choice and the physical meaning of the encountered Lagrange multipliers two different schemes for the Nitsche formulation are obtained. Both types of the Nitsche approach are implemented in a nonlinear element and verification with numerical examples is done. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

International financial networks with intermediation: modeling,analysis, and computations

In this paper, we develop a framework for the modeling, analysis, and computation of solutions to international financial networks with intermediation. We consider three tiers of decision-makers consisting of: source agents in different countries, financial intermediaries, and consumers associated with the demand markets for different products in distinct currencies and countries. We model the behavior of the decision-makers, derive the equilibrium conditions, and establish the variational inequality formulation. We then utilize the variational inequality formulation to obtain qualitative properties of the equilibrium financial flow and price pattern as well as to propose an algorithm along with convergence results. Numerical examples are presented to illustrate both the model and the computational procedure. This research extends the recent results surrounding the modeling of financial networks with intermediation to the international dimension.Revised: January 2003, AMS Classification: 90, 91     

基于时间敏感产品的多厂商供应链管理

本文主要研究基于时间敏感产品的多厂商供应链网络模型。在该模型中,每个厂商都希望自己的运营成本和时间消耗最少,但目标函数和约束条件都受到竞争对手决策的影响,因此属于广义纳什均衡问题的范畴。在过去的文献中,这类问题通常被转化成一般形式的变分不等式来处理。本文中,注意到模型中所涉及的约束函数都是线性函数,我们将问题转化成混合互补系统来求解。与一般形式的变分不等式问题相比,混合互补系统要容易处理得多。借助于所谓Fischer-Burmeister函数,我们将混合互补系统转化成非线性方程组,然后利用半光滑牛顿法进行求解。初步的数值实验表明,本文提出的方法是切实可行的。     

A supply chain network equilibrium model with random demands

In this paper, we develop a supply chain network model consisting of manufacturers and retailers in which the demands associated with the retail outlets are random. We model the optimizing behavior of the various decision-makers, derive the equilibrium conditions, and establish the finite-dimensional variational inequality formulation. We provide qualitative properties of the equilibrium pattern in terms of existence and uniqueness results and also establish conditions under which the proposed computational procedure is guaranteed to converge. Finally, we illustrate the model through several numerical examples for which the equilibrium prices and product shipments are computed. This is the first supply chain network equilibrium model with random demands for which modeling, qualitative analysis, and computational results have been obtained.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

优化和均衡的等价性

通过向量优化问题, 向量变分不等式问题以及向量变分原理来分析优化问题及均衡问题的一致性.从而显然, 可以用统一的观点来处理数值优化、向量优化以及博弈论等问题.进而为非线性分析提供了一个新的发展空间.     

An operator splitting method for variational inequalities with partially unknown mappings

In this paper, we propose a new operator splitting method for solving a class of variational inequality problems in which part of the underlying mappings are unknown. This class of problems arises frequently from engineering, economics and transportation equilibrium problems. At each iteration, by using the information observed from the system, the method solves a system of nonlinear equations, which is well-defined. Under mild assumptions, the global convergence of the method is proved, and its efficiency is demonstrated with numerical examples. The research of D. Han is supported by NSFC grant 10501024 and NSF of Jiangsu Province at Grant No. BK2006214.     

Variational inequalities and discrete and continuum models of network equilibrium problems

In this paper, we present different equilibrium models (the traffic equilibrium model in the static, in the dynamic and in the continuum case, the market equilibrium problem in the static and in the dynamic case) and we find the variational inequality related to each problem. We propose also a computational procedure for the calculation of the equilibrium solution and present the dual formulation of the variational inequality related to the traffic equilibrium problem.     

Some equilibrium problems under uncertainty and random variational inequalities

In this paper we describe some nonlinear equilibrium problems under uncertainty arising from economics and operations research. In particular we treat Wardrop equilibria in traffic networks. We show how the theory of monotone random variational inequalities, where random variables occur both in the operator and the constraint set, can be applied to model these problems. Therefore in this contribution we introduce the topic of random variational inequalities and present some of our recent results in this field. In particular, we treat the more structured case where a finite Karhunen-Loève expansion leads to a separation of the random and the deterministic variables. Here we describe a norm convergent approximation procedure based on averaging and truncation. We illustrate this procedure by means of some small sized numerical examples.     

解可分离结构变分不等式的一种新的交替方向法

交替方向法是求解可分离结构变分不等式问题的经典方法之一, 它将一个大型的变分不等式问题分解成若干个小规模的变分不等式问题进行迭代求解. 但每步迭代过程中求解的子问题仍然摆脱不了求解变分不等式子问题的瓶颈. 从数值计算上来说, 求解一个变分不等式并不是一件容易的事情.因此, 本文提出一种新的交替方向法, 每步迭代只需要求解一个变分不等式子问题和一个强单调的非线性方程组子问题. 相对变分不等式问题而言, 我们更容易、且有更多的有效算法求解一个非线性方程组问题. 在与经典的交替方向法相同的假设条件下, 我们证明了新算法的全局收敛性. 进一步的数值试验也验证了新算法的有效性.     

A variational inequality formulation of the environmental pollution control problem

In this paper we develop the time-dependent pollution control problem in which different countries aim to determine the optimal investment allocation in environmental projects and the tolerable pollutant emissions, so as to maximize their welfare. We provide the equilibrium conditions governing the model and derive the evolutionary variational inequality formulation. The existence of solutions is investigated and a numerical example is also presented.     

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.     

Lexicographic variational inequalities with applications

In this article, we consider equivalence properties between various kinds of lexicographic variational inequalities. By employing various concepts of monotonicity, we show that the usual sequential variational inequality is equivalent to the direct lexicographic variational inequality or to the dual lexicographic variational inequality. We establish several existence results for lexicographic variational inequalities. Also, we introduce the lexicographic complementarity problem and establish its equivalence with the lexicographic variational inequality. We illustrate our approach by several examples of applications to vector transportation and vector spatial equilibrium problems.     

Finite difference technique for solving obstacle problems

In this paper, we use the variational inequality theory coupled with finite difference technique to obtain an approximate solution for a class of obstacle problems in elasticity, like those describing the equilibrium configuration of an elastic string stretched over an elastic obstacle. The variational inequality formulation is used to discuss the problem of uniqueness and existence of the solution of the obstacle problems.