Search

We address the minimization of an objective function over the solution set of a (non-parametric) lower-level variational inequality. This problem is a special instance of semi-infinite programs and encompasses, as particular cases, simple (smooth) bilevel and equilibrium selection problems. We resort to a suitable approximated version of the hierarchical problem. We show that this, on the one hand, does not perturb the original (exact) program ‘too much’, on the other hand, allows one to rely on some suitable exact penalty approaches whose convergence properties are established.

In this paper, we introduce an inertial projection-type method with different updating strategies for solving quasi-variational inequalities with strongly monotone and Lipschitz continuous operators in real Hilbert spaces. Under standard assumptions, we establish different strong convergence results for the proposed algorithm. Primary numerical experiments demonstrate the potential applicability of our scheme compared with some related methods in the literature.

Distributed and parallel algorithms have been frequently investigated in the recent years, in particular in applications like machine learning. Nonetheless, only a small subclass of the optimization algorithms in the literature can be easily distributed, for the presence, e.g., of coupling constraints that make all the variables dependent from each other with respect to the feasible set. Augmented Lagrangian methods are among the most used techniques to get rid of the coupling constraints issue, namely by moving such constraints to the objective function in a structured, well-studied manner. Unfortunately, standard augmented Lagrangian methods need the solution of a nested problem by needing to (at least inexactly) solve a subproblem at each iteration, therefore leading to potential inefficiency of the algorithm. To fill this gap, we propose an augmented Lagrangian method to solve convex problems with linear coupling constraints that can be distributed and requires a single gradient projection step at every iteration. We give a formal convergence proof to at least $$\varepsilon $$-approximate solutions of the problem and a detailed analysis of how the parameters of the algorithm influence the value of the approximating parameter $$\varepsilon $$. Furthermore, we introduce a distributed version of the algorithm allowing to partition the data and perform the distribution of the computation in a parallel fashion.

We analyze a Nash equilibrium problem arising when trades from different accounts are pooled for execution. We introduce a new general multi-portfolio model and state sufficient conditions for the monotonicity of the underlying Nash equilibrium problem. Monotonicity makes it possible to treat the problem numerically and, for the case of nonunique equilibria, to solve hierarchical problems of equilibrium selection. We also give sufficient conditions for the Nash equilibrium problem formulation to be a potential game. Our computational experience confirms the theoretical insights and substantiates the significance of the equilibrium selection.

Urged by the outbreak of the COVID-19 in Italy, this study aims at helping to tackle the spread of the disease by resorting to operations research techniques. In particular, we propose a mathematical program to model the problem of establishing how many diagnostic tests the Italian regions must perform in order to maximize the overall disease detection capability. An important feature of our approach is its simplicity: data we resort to are easy to obtain and one can employ standard optimization tools to address the problem. The results we obtain when applying our method to the Italian case seem promising.

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branc...

We study connections between optimistic bilevel programming problems and generalized Nash equilibrium problems. We remark that, with respect to bilevel problems, we consider the general case in which the lower level program is not assumed to have a unique solution. Inspired by the optimal value approach, we propose a Nash game that, transforming the so-called implicit value function constraint into an explicitly defined constraint function, incorporates some taste of hierarchy and turns out to be related to the bilevel programming problem. We provide a complete theoretical analysis of the relationship between the vertical bilevel problem and our ``uneven'' horizontal model: in particular, we define classes of problems for which solutions of the bilevel program can be computed by finding equilibria of our game. Furthermore, by referring to some applications in economics, we show that our ``uneven'' horizontal model, in some sense, lies between the vertical bilevel model and a ``pure'' horizontal game.

We introduce the noncooperative fixed charge transportation problem (NFCTP), which is a game-theoretic extension of the fixed charge transportation problem. In the NFCTP, competing players solve coupled fixed charge transportation problems simultaneously. Three versions of the NFCTP are discussed and compared which differ in the treatment of shared social costs. This may be used from central authorities in order to find a socially balanced framework which is illustrated in a numerical study. Using techniques from generalized Nash equilibrium problems with mixed-integer variables we show the existence of Nash equilibria for these models and examine their structural properties. Since there is no unique equilibrium for the NFCTP, we also discuss how to solve the Nash selection problem and, finally, propose numerical methods for the computation of Nash equilibria which are based on mixed-integer programming.

We consider a class of optimistic bilevel problems. Specifically, we address bilevel problems in which at the lower level the objective function is fully convex and the feasible set does not depend on the upper level variables. We show that this nontrivial class of mathematical programs is sufficiently broad to encompass significant real-world applications and proves to be numerically tractable. From this respect, we establish that the stationary points for a relaxation of the original problem can be obtained addressing a suitable generalized Nash equilibrium problem. The latter game is proven to be convex and with a nonempty solution set. Leveraging this correspondence, we provide a provably convergent, easily implementable scheme to calculate stationary points of the relaxed bilevel program. As witnessed by some numerical experiments on an application in economics, this algorithm turns out to be numerically viable also for big dimensional problems.

We consider nested variational inequalities consisting in a (upper-level) variational inequality whose feasible set is given by the solution set of another (lower-level) variational inequality. Purely hierarchical convex bilevel optimization problems and certain multi-follower games are particular instances of nested variational inequalities. We present an explicit and ready-to-implement Tikhonov-type solution method for such problems. We give conditions that guarantee the convergence of the proposed method. Moreover, inspired by recent works in the literature, we provide a convergence rate analysis. In particular, for the simple bilevel instance, we are able to obtain enhanced convergence results.

We define the concept of reproducible map and show that, whenever the constraint map defining the quasivariational inequality (QVI) is reproducible then one can characterize the whole solution set of the QVI as a union of solution sets of some variational inequalities (VI). By exploiting this property, we give sufficient conditions to compute any solution of a generalized Nash equilibrium problem (GNEP) by solving a suitable VI. Finally, we define the class of pseudo-Nash equilibrium problems, which are (not necessarily convex) GNEPs whose solutions can be computed by solving suitable Nash equilibrium problems.

Pessimistic bilevel optimization problems, as do optimistic ones, possess a structure involving three interrelated optimization problems. Moreover, their finite infima are only attained under strong conditions. We address these difficulties within a framework of moderate assumptions and a perturbation approach which allows us to approximate such finite infima arbitrarily well by minimal values of a sequence of solvable single-level problems. To this end, as has already been done for optimistic problems, for the first time in the literature we introduce the standard version of the pessimistic bilevel problem. For its algorithmic treatment, we reformulate it as a standard optimistic bilevel program with a two follower Nash game in the lower level. The latter lower-level game, in turn, is replaced by its Karush-Kuhn-Tucker conditions, resulting in a single-level mathematical program with complementarity constraints. We prove that the perturbed pessimistic bilevel problem, its standard version, the two follower game, as well as the mathematical program with complementarity constraints are equivalent with respect to their global minimal points. We study the more intricate connections between their local minimal points in detail. As an illustration, we numerically solve a regulator problem from economics for different values of the perturbation parameters.

We propose a new formulation of the Karush---Kunt---Tucker conditions of a particular class of quasi-variational inequalities. In order to reformulate the problem we use the Fisher---Burmeister complementarity function and canonical duality theory. We establish the conditions for a critical point of the new formulation to be a solution of the original quasi-variational inequality showing the potentiality of such approach in solving this class of problems. We test the obtained theoretical results with a simple heuristic that is demonstrated on several problems coming from the academy and various engineering applications.

We consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches.

We consider Cournot oligopoly models in which some variables represent indivisible quantities. These models can be addressed by computing equilibria of Nash equilibrium problems in which the players solve mixed-integer nonlinear problems. In the literature there are no methods to compute equilibria of this type of Nash games. We propose a Jacobi-type method for computing solutions of Nash equilibrium problems with mixed-integer variables. This algorithm is a generalization of a recently proposed method for the solution of discrete so-called “2-groups partitionable” Nash equilibrium problems. We prove that our algorithm converges in a finite number of iterations to approximate equilibria under reasonable conditions. Moreover, we give conditions for the existence of approximate equilibria. Finally, we give numerical results to show the effectiveness of the proposed method.

The Support Vector Machines (SVMs) dual formulation has a non-separable structure that makes the design of a convergent distributed algorithm a very difficult task. Recently some separable and distributable reformulations of the SVM training problem have been obtained by fixing one primal variable. While this strategy seems effective for some applications, in certain cases it could be weak since it drastically reduces the overall final performance. In this work we present the first fully distributable algorithm for SVMs training that globally converges to a solution of the original (non-separable) SVMs dual formulation. Besides a detailed convergence analysis, we provide a simple demonstrative example showing the advantages of the original SVMs dual formulation with respect to the weak separable one and highlights the practical effectiveness of our method. We report further tests to show practical convergence of the proposed method on real-world datasets.

When dealing with big data problems it is crucial to design methods able to decompose the original problem into smaller and more manageable pieces. Parallel methods lead to a solution by concurrently working on different pieces that are distributed among available agents, so that exploiting the computational power of multi-core processors and therefore efficiently solving the problem. Beyond gradient-type methods, that can of course be easily parallelized but suffer from practical drawbacks, recently a convergent decomposition framework for the parallel optimization of (possibly non-convex) big data problems was proposed. Such framework is very flexible and includes both fully parallel and fully sequential schemes, as well as virtually all possibilities in between. We illustrate the versatility of this parallel decomposition framework by specializing it to different well-studied big data problems like LASSO, logistic regression and support vector machines training. We give implementation guidelines and numerical results showing that proposed parallel algorithms work very well in practice.

The Nash equilibrium problem is a widely used tool to model non-cooperative games. Many solution methods have been proposed in the literature to compute solutions of Nash equilibrium problems with continuous strategy sets, but, besides some specific methods for some particular applications, there are no general algorithms to compute solutions of Nash equilibrium problems in which the strategy set of each player is assumed to be discrete. We define a branching method to compute the whole solution set of Nash equilibrium problems with discrete strategy sets. This method is equipped with a procedure that, by fixing variables, effectively prunes the branches of the search tree. Furthermore, we propose a preliminary procedure that by shrinking the feasible set improves the performances of the branching method when tackling a particular class of problems. Moreover, we prove existence of equilibria and we propose an extremely fast Jacobi-type method which leads to one equilibrium for a new class of Nash equilibrium problems with discrete strategy sets. Our numerical results show that all proposed algorithms work very well in practice.

We propose a decomposition framework for the parallel optimization of the sum of a differentiable function and a (block) separable nonsmooth, convex one. The latter term is typically used to enforce structure in the solution as, for example, in Lasso problems. Our framework is very flexible and includes both fully parallel Jacobi schemes and Gauss-Seidel (Southwell-type) ones, as well as virtually all possibilities in between (e.g., gradient- or Newton-type methods) with only a subset of variables updated at each iteration. Our theoretical convergence results improve on existing ones, and numerical results show that the new method compares favorably to existing algorithms., Comment: submitted to IEEE ICASSP 2014

The following article has been included in a multiple retraction: Canonical Dual Approach for Contact Mechanics Problems with Friction; Vittorio Latorre, Simone Sagratella, David Y Gao. http://mms.sagepub.com/content/early/2015/01/20/1081286514566534.abstract In 2015 SAGE were made aware of concerns regarding the Special Issue of Mathematics & Mechanics of Solids on Advances in Canonical Duality Theory, guest-edited by Professor David Gao. At the request of the Guest Editor, the Special Issue has been retracted, due to conflict of interest regarding Professor Gao’s role as Guest Editor and co-author on a number of submitted papers. In addition the peer review process was less rigorous than the journal requires. The Guest Editor takes full responsibility for the retraction. The following articles that were due to appear in the Special Issue have therefore been retracted: Canonical Duality-Triality: Bridge between Nonconvex Analysis/Mechanics and Global Optimization in complex systems; David Y Gao, Ning Ruan, and Vittorio Latorre. http://mms.sagepub.com/content/early/2015/02/24/1081286514566533.abstract Canonical Dual Approach for Contact Mechanics Problems with Friction; Vittorio Latorre, Simone Sagratella, David Y Gao. http://mms.sagepub.com/content/early/2015/01/20/1081286514566534.abstract Canonical Duality Theory for Solving Non-Monotone Variational Inequality Problems; Guoshan Liu, David Y Gao, Shouyang Wang. http://mms.sagepub.com/content/early/2015/02/04/1081286514566535.abstract Double Well Potential Function and Its Optimization in The n-dimensional Real Space. Part I; Shu-Cherng Fang, David Y Gao, Gang-Xuan Lin, Ruey-Lin Sheu, Wen-Xun Xing. http://mms.sagepub.com/content/early/2015/02/24/1081286514566704.abstract Double Well Potential Function and Its Optimization in The n-dimensional Real Space. Part II; Yong Xia, Ruey-Lin Sheu, Shu-Cherng Fang, Wenxun Xing. http://mms.sagepub.com/content/early/2015/02/09/1081286514566723.abstract Analytic Solutions to 3-D Finite Deformation Problems Governed by St Venant-Kirchhoff Material; David Y Gao and E. Hajilarov. http://mms.sagepub.com/content/early/2015/07/06/1081286515591084.abstract Triality Theory and Complete Post-buckling Solutions of Large Deformed Beam by Canonical Dual Finite Element Method; Kun Cai, David Y Gao, Qinghua Qin. http://mms.sagepub.com/content/early/2015/06/28/1081286515591085.abstract Global Solutions to Spherically Constrained Quadratic Minimization via Canonical Duality Theory; Yi Chen, David Y Gao. http://mms.sagepub.com/content/early/2015/04/08/1081286515577122.abstract Unified Canonical Duality Methodology for Global Optimization; Vittorio Latorre, David Y Gao and N. Ruan. http://mms.sagepub.com/content/early/2015/07/06/1081286515591305.abstract A Framework of Canonical Dual Algorithms for Global Optimization; Xiaojun Zhou, David Y Gao, Chunhua Yang. http://mms.sagepub.com/content/early/2015/07/22/1081286515592190.abstract Canonical Duality Theory for Solving Nonconvex/Discrete Constrained Global Optimization Problems; Ning Ruan, David Y Gao. http://mms.sagepub.com/content/early/2015/07/08/1081286515591087.abstract Global Optimization Solutions to a Class of Non-convex Quadratic Minimization Problems with Quadratic Constraints; Yubo Yuan. http://mms.sagepub.com/content/early/2015/07/06/1081286515591086.abstract On Minimal Distance between Two Non-Convex Surfaces; Daniel Morales-Silva, David Y Gao. http://mms.sagepub.com/content/early/2015/07/27/1081286515592949.abstract The Editor-in-Chief and SAGE strive to uphold the very highest standards of publication ethics and are committed to supporting the high standards of integrity of Mathematics & Mechanics of Solids. Authors, reviewers, editors and interested readers are encouraged to consult SAGE’s ethics statements and the Committee on Publication Ethics (COPE) website for guidelines on publication ethics.