📉Variational Analysis Unit 4 – Variational Inequalities & Complementarity

Key Concepts and Definitions

• Variational inequality problem involves finding a vector $x^*$ in a subset $K$ of $\mathbb{R}^n$ such that $\langle F(x^*), x - x^* \rangle \geq 0$ for all $x \in K$, where $F: \mathbb{R}^n \rightarrow \mathbb{R}^n$ is a given mapping
• Complementarity problem is a special case of variational inequality where $K$ is the non-negative orthant $\mathbb{R}^n_+$ and the problem is to find $x^* \in \mathbb{R}^n_+$ such that $F(x^*) \in \mathbb{R}^n_+$ and $\langle x^*, F(x^*) \rangle = 0$
• Solution set of a variational inequality is the set of all vectors $x^*$ satisfying the variational inequality condition
  • Can be empty, a singleton, or contain multiple elements depending on the properties of $F$ and $K$
• Monotonicity plays a crucial role in the existence and uniqueness of solutions to variational inequalities
  • $F$ is monotone if $\langle F(x) - F(y), x - y \rangle \geq 0$ for all $x, y \in \mathbb{R}^n$
  • Strict monotonicity and strong monotonicity are stronger conditions that guarantee uniqueness of solutions
• Lipschitz continuity of $F$ is another important property in the analysis of variational inequalities
  • $F$ is Lipschitz continuous with constant $L > 0$ if $\|F(x) - F(y)\| \leq L\|x - y\|$ for all $x, y \in \mathbb{R}^n$

Mathematical Foundations

• Variational inequalities are closely related to optimization problems and can be seen as a generalization of optimality conditions
  • If $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is a differentiable convex function and $K$ is a convex set, then $x^*$ is a solution to the optimization problem $\min_{x \in K} f(x)$ if and only if $x^*$ satisfies the variational inequality $\langle \nabla f(x^*), x - x^* \rangle \geq 0$ for all $x \in K$
• Projection operators play a key role in the formulation and solution of variational inequalities
  • The projection of a point $x$ onto a closed convex set $K$ is defined as $P_K(x) = \arg\min_{y \in K} \|y - x\|$
  • Variational inequalities can be equivalently formulated using projection operators, leading to fixed-point characterizations of solutions
• Subdifferential calculus is a powerful tool in the analysis of variational inequalities, especially for non-smooth problems
  • The subdifferential of a convex function $f$ at $x$ is the set $\partial f(x) = \{g \in \mathbb{R}^n : f(y) \geq f(x) + \langle g, y - x \rangle, \forall y \in \mathbb{R}^n\}$
  • Variational inequalities can be formulated using subdifferentials, allowing for the treatment of non-smooth objectives and constraints
• Monotone operator theory provides a unified framework for studying variational inequalities and related problems
  • A set-valued mapping $T: \mathbb{R}^n \rightrightarrows \mathbb{R}^n$ is monotone if $\langle x - y, u - v \rangle \geq 0$ for all $x, y \in \mathbb{R}^n$, $u \in T(x)$, and $v \in T(y)$
  • Variational inequalities can be seen as finding zeros of monotone operators, i.e., finding $x^*$ such that $0 \in T(x^*)$

Types of Variational Inequalities

• Classical variational inequalities involve finding $x^*$ in a closed convex set $K$ such that $\langle F(x^*), x - x^* \rangle \geq 0$ for all $x \in K$, where $F$ is a single-valued mapping
  • Well-studied class of problems with extensive theory and algorithms available
• Quasi-variational inequalities (QVIs) are a generalization where the feasible set $K$ depends on the solution $x^*$, i.e., $K = K(x^*)$
  • QVIs arise in equilibrium problems, such as Nash equilibria in game theory, where players' strategies depend on the strategies of other players
• Mixed variational inequalities involve a combination of single-valued and set-valued mappings
  • Find $x^*$ such that $\langle F(x^*), x - x^* \rangle + \varphi(x) - \varphi(x^*) \geq 0$ for all $x \in K$, where $F$ is single-valued and $\varphi$ is a convex function
• Generalized variational inequalities consider set-valued mappings $T$ instead of single-valued mappings $F$
  • Find $x^*$ and $u^* \in T(x^*)$ such that $\langle u^*, x - x^* \rangle \geq 0$ for all $x \in K$
• Hemivariational inequalities involve non-convex and non-smooth functions, using the concept of generalized directional derivatives
  • Arise in mechanics and engineering problems with non-monotone and non-smooth behavior
• Stochastic variational inequalities incorporate uncertainty by considering random mappings or random feasible sets
  • Used to model equilibrium problems under uncertainty, such as stochastic Nash equilibria

Complementarity Problems

• Complementarity problems are a special case of variational inequalities where the feasible set is the non-negative orthant $K = \mathbb{R}^n_+$
  • Find $x^* \in \mathbb{R}^n_+$ such that $F(x^*) \in \mathbb{R}^n_+$ and $\langle x^*, F(x^*) \rangle = 0$
• Linear complementarity problems (LCPs) involve a linear mapping $F(x) = Mx + q$, where $M$ is a matrix and $q$ is a vector
  • LCPs arise in various applications, such as contact mechanics, game theory, and optimization
  • Existence and uniqueness of solutions depend on the properties of the matrix $M$ (e.g., positive semidefinite, P-matrix)
• Nonlinear complementarity problems (NCPs) consider nonlinear mappings $F$
  • NCPs can be reformulated as equivalent fixed-point problems or nonlinear equations using NCP-functions
  • NCP-functions, such as the min-function and the Fischer-Burmeister function, satisfy $\phi(a, b) = 0 \Leftrightarrow a \geq 0, b \geq 0, ab = 0$
• Mixed complementarity problems (MCPs) involve a combination of complementarity constraints and general equality and inequality constraints
  • MCPs can be seen as a generalization of KKT conditions for optimization problems with complementarity constraints
• Semidefinite complementarity problems (SDCPs) consider matrix variables and complementarity constraints in the cone of positive semidefinite matrices
  • SDCPs have applications in control theory, robust optimization, and combinatorial optimization
• Complementarity problems can be solved using a variety of algorithms, such as pivoting methods, interior-point methods, and smoothing methods
  • The choice of algorithm depends on the structure of the problem (linear, nonlinear, mixed) and the desired properties (convergence, complexity)

Solution Methods and Algorithms

• Projection methods are a class of algorithms that solve variational inequalities by iteratively projecting onto the feasible set
  • The basic projection method updates the solution as $x^{k+1} = P_K(x^k - \alpha_k F(x^k))$, where $\alpha_k$ is a step size and $P_K$ is the projection operator onto $K$
  • Convergence of projection methods depends on the properties of $F$ (e.g., monotonicity, Lipschitz continuity) and the choice of step sizes
• Extragradient methods improve upon projection methods by performing an additional projection step to enhance convergence
  • The extragradient method updates the solution as $y^k = P_K(x^k - \alpha_k F(x^k))$ and $x^{k+1} = P_K(x^k - \alpha_k F(y^k))$
  • Extragradient methods can handle a wider range of problems, including pseudo-monotone and non-monotone mappings
• Proximal point methods solve variational inequalities by adding a regularization term to the mapping
  • The proximal point method updates the solution as $x^{k+1} = (I + \lambda_k T)^{-1}(x^k)$, where $T$ is a monotone operator and $\lambda_k$ is a regularization parameter
  • Proximal point methods have good convergence properties and can handle set-valued mappings and non-smooth problems
• Interior-point methods solve complementarity problems by reformulating them as equivalent optimization problems with logarithmic barrier functions
  • The central path is defined as the solution to the barrier problem for varying barrier parameters, and interior-point methods follow this path to reach the solution
  • Interior-point methods have polynomial complexity and can handle large-scale problems efficiently
• Smoothing methods solve non-smooth variational inequalities by approximating them with a sequence of smooth problems
  • Smoothing methods introduce a smooth approximation of the non-smooth mapping or use a regularization technique to obtain a smooth problem
  • The smooth problems are solved using standard algorithms, and the smoothing parameter is gradually reduced to recover the original solution
• Splitting methods decompose the variational inequality into simpler subproblems that are easier to solve
  • Examples include the forward-backward splitting method, which alternates between a forward step (evaluation of $F$) and a backward step (projection onto $K$)
  • Splitting methods are particularly effective for problems with separable structure or when the projection onto $K$ is computationally expensive

Applications in Optimization

• Variational inequalities provide a unified framework for studying optimization problems and their optimality conditions
  • Karush-Kuhn-Tucker (KKT) conditions for nonlinear optimization problems can be formulated as a mixed complementarity problem
  • Variational inequalities can be used to characterize saddle points and minimax problems in optimization
• Convex optimization problems can be reformulated as equivalent variational inequalities
  • The solution to a convex optimization problem $\min_{x \in K} f(x)$ satisfies the variational inequality $\langle \nabla f(x^*), x - x^* \rangle \geq 0$ for all $x \in K$
  • This reformulation allows the application of variational inequality algorithms to solve convex optimization problems
• Variational inequalities arise naturally in the study of equilibrium problems, such as Nash equilibria in game theory
  • A Nash equilibrium is a strategy profile where no player can improve their payoff by unilaterally changing their strategy
  • Finding a Nash equilibrium can be formulated as a variational inequality problem, enabling the use of variational inequality algorithms for computing equilibria
• Bilevel optimization problems, where one optimization problem is embedded within another, can be reformulated as variational inequalities
  • The lower-level problem is replaced by its optimality conditions, leading to a variational inequality formulation of the bilevel problem
  • This reformulation allows the application of variational inequality algorithms to solve bilevel optimization problems
• Inverse optimization problems, which aim to infer the objective function or constraints of an optimization problem from observed solutions, can be formulated as variational inequalities
  • The observed solutions are assumed to satisfy the optimality conditions, which are then used to construct a variational inequality
  • Solving the variational inequality yields the parameters of the underlying optimization problem
• Robust optimization problems, which seek solutions that are immune to uncertainty in the problem data, can be addressed using variational inequalities
  • The robust counterpart of an optimization problem can be formulated as a variational inequality, incorporating the uncertainty sets
  • Variational inequality algorithms can then be applied to find robust solutions that are feasible for all realizations of the uncertain parameters

Real-World Examples

• Traffic network equilibrium problems model the distribution of traffic flow in a transportation network
  • Drivers choose their routes to minimize their travel times, leading to a Wardrop equilibrium where no driver can improve their travel time by unilaterally changing their route
  • The traffic equilibrium problem can be formulated as a variational inequality, with the mapping representing the travel time functions and the feasible set representing the flow conservation constraints
• Market equilibrium problems study the balance between supply and demand in an economy
  • Producers and consumers make decisions to maximize their profits and utilities, respectively, leading to an equilibrium where supply equals demand
  • The market equilibrium problem can be formulated as a variational inequality, with the mapping representing the excess demand functions and the feasible set representing the price and quantity constraints
• Contact mechanics problems investigate the behavior of deformable bodies in contact with each other
  • The contact forces and displacements must satisfy the Signorini conditions, which ensure non-penetration and complementarity between normal stresses and displacements
  • The contact problem can be formulated as a variational inequality, with the mapping representing the elasticity operators and the feasible set representing the contact constraints
• Portfolio optimization problems aim to allocate assets in a financial portfolio to maximize returns while minimizing risk
  • Investors seek to find an optimal balance between expected returns and risk, subject to budget and investment constraints
  • The portfolio optimization problem can be formulated as a variational inequality, with the mapping representing the risk-return trade-off and the feasible set representing the investment constraints
• Energy markets problems model the interactions between producers, consumers, and regulators in the energy sector
  • Producers compete to maximize their profits, consumers aim to minimize their costs, and regulators ensure fair competition and environmental sustainability
  • The energy market equilibrium problem can be formulated as a variational inequality, with the mapping representing the supply and demand functions and the feasible set representing the market and regulatory constraints
• Structural design problems seek to find the optimal shape and topology of a structure subject to loading and performance criteria
  • The design problem involves minimizing the compliance or maximizing the stiffness of the structure, subject to volume and manufacturing constraints
  • The structural design problem can be formulated as a variational inequality, with the mapping representing the stiffness and compliance operators and the feasible set representing the design constraints

Advanced Topics and Extensions

• Infinite-dimensional variational inequalities consider problems where the decision variables belong to an infinite-dimensional space, such as a function space
  • Examples include partial differential equations (PDEs) with variational formulations, such as the Navier-Stokes equations in fluid mechanics
  • The theory and algorithms for infinite-dimensional variational inequalities are more complex and require tools from functional analysis and numerical analysis
• Generalized Nash equilibrium problems (GNEPs) extend the concept of Nash equilibrium to situations where players' feasible sets depend on the strategies of other players
  • GNEPs can be formulated as quasi-variational inequalities (QVIs), where the feasible set is a point-to-set mapping
  • The existence and uniqueness of solutions to GNEPs and QVIs require more advanced fixed-point theorems and generalized convexity concepts
• Equilibrium problems with equilibrium constraints (EPECs) are a class of problems that combine optimization and variational inequalities
  • EPECs arise in multi-leader-follower games, where leaders optimize their objectives while anticipating the equilibrium behavior of followers
  • The solution concepts and algorithms for EPECs involve a combination of optimization techniques and variational inequality methods
• Variational-hemivariational inequalities (VHVIs) are a generalization of variational inequalities that incorporate non-convex and non