共查询到20条相似文献,搜索用时 15 毫秒
1.
A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain
higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of
such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive
compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementarity
problem. We establish the convexity of the optimization problem in the case where each player's strategy set is unidimensional.
In the multivariate case, we propose upper and lower bounding procedures for the collusive optimization problem and establish
convergence properties of these procedures. Computational results with these procedures for solving some test problems are
reported.
It is with great honor that we dedicate this paper to Professor Terry Rockafellar on the occasion of his 70th birthday. Our
work provides another example showing how Terry's fundamental contributions to convex and variational analysis have impacted
the computational solution of applied game problems.
This author's research was partially supported by the National Science Foundation under grant ECS-0080577.
This author's research was partially supported by the National Science Foundation under grant CCR-0098013. 相似文献
2.
Miguel A. Goberna Mercedes Larriqueta Virginia N. Vera de Serio 《Journal of Computational and Applied Mathematics》2008
Many mathematical programming models arising in practice present a block structure in their constraint systems. Consequently, the feasibility of these problems depends on whether the intersection of the solution sets of each of those blocks is empty or not. The existence theorems allow to decide when the intersection of non-empty sets in the Euclidean space, which are the solution sets of systems of (possibly infinite) inequalities, is empty or not. In those situations where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining whether the relative position of the sets is preserved by sufficiently small perturbations or not. This paper focuses on the stability of the non-empty (empty) intersection of the solutions of some given systems, which can be seen as the images of set-valued mappings. We give sufficient conditions for the stability, and necessary ones as well; in particular we consider (semi-infinite) convex systems and also linear systems. In this last case we discuss the distance to ill-posedness. 相似文献
3.
4.
《Optimization》2012,61(6):693-713
We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size. 相似文献
5.
This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in n. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05. 相似文献
6.
Yong-Chao Liu Jin Zhang Gui-Hua Lin 《Journal of Computational and Applied Mathematics》2011,235(13):3870-3882
This paper considers a stochastic mathematical program with hybrid equilibrium constraints (SMPHEC), which includes either “here-and-now” or “wait-and-see” type complementarity constraints. An example is given to describe the necessity to study SMPHEC. In order to solve the problem, the sampling average approximation techniques are employed to approximate the expectations and smoothing and penalty techniques are used to deal with the complementarity constraints. Limiting behaviors of the proposed approach are discussed. Preliminary numerical experiments show that the proposed approach is applicable. 相似文献
7.
8.
G. Still 《Mathematical Programming》2001,91(1):53-69
The discretization approach for solving semi-infinite optimization problems is considered. We are interested in the convergence
rate of the error between the solution of the semi-infinite problem and the solution of the discretized program depending
on the discretization mesh-size. It will be shown how this rate depends on whether the minimizer is strict of order one or
two and on whether the discretization includes boundary points of the index set in a specific way. This is done for ordinary
and for generalized semi-infinite problems.
Received: November 21, 2000 / Accepted: May 2001?Published online September 17, 2001 相似文献
9.
This paper discusses the consistent regularization property of the generalized α method when applied as an integrator to an initial value high index and singular differential-algebraic equation model of a multibody system. The regularization comes from within the discretization itself and the discretization remains consistent over the range of values the regularization parameter may take. The regularization involves increase of the smallest singular values of the ill-conditioned Jacobian of the discretization and is different from Baumgarte and similar techniques which tend to be inconsistent for poor choice of regularization parameter. This regularization also helps where pre-conditioning the Jacobian by scaling is of limited effect, for example, when the scleronomic constraints contain multiple closed loops or singular configuration or when high index path constraints are present. The feed-forward control in Kane’s equation models is additionally considered in the numerical examples to illustrate the effect of regularization. The discretization presented in this work is adopted to the first order DAE system (unlike the original method which is intended for second order systems) for its A-stability and same order of accuracy for positions and velocities. 相似文献
10.
A semi-infinite programming algorithm for solving optimal power flow with transient stability constraints 总被引:1,自引:0,他引:1
This paper proposes a new algorithm for solving a type of complicated optimal power flow (OPF) problems in power systems, i.e., OPF problems with transient stability constraints (OTS). The OTS is converted into a semi-infinite programming (SIP) via some suitable function analysis. Then based on the KKT system of the reformulated SIP, a smoothing quasi-Newton algorithm is presented in which the numerical integration is used. The convergence of the algorithm is established. An OTS problem in power system is tested, which shows that the proposed algorithm is promising. 相似文献
11.
This paper is devoted to the study of nonsmooth generalized semi-infinite programming problems in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be locally Lipschitz. We introduce a constraint qualification which is based on the Mordukhovich subdifferential. Then, we derive a Fritz–John type necessary optimality condition. Finally, interrelations between the new and the existing constraint qualifications such as the Mangasarian–Fromovitz, linear independent, and the Slater are investigated. 相似文献
12.
This paper studies the stability of the set containment problem. Given two non-empty sets in the Euclidean space which are
the solution sets of two systems of (possibly infinite) inequalities, the Farkas type results allow to decide whether one
of the two sets is contained or not in the other one (which constitutes the so-called containment problem). In those situations
where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining
whether the relative position of the two sets is preserved by sufficiently small perturbations or not. This paper deals with
this stability problem as a particular case of the maintaining of the relative position of the images of two set-valued mappings;
first for general set-valued mappings and second for solution sets mappings of convex and linear systems. Thus the results
in this paper could be useful in the postoptimal analysis of optimization problems with inclusion constraints.
相似文献
13.
In this paper we present an analysis of a numerical method for a degenerate partial differential equation, called the Black–Scholes
equation, governing American and European option pricing. The method is based on a fitted finite volume spatial discretization
and an implicit time stepping technique. The analysis is performed within the framework of the vertical method of lines, where
the spatial discretization is formulated as a Petrov–Galerkin finite element method with each basis function of the trial
space being determined by a set of two-point boundary value problems. We establish the stability and an error bound for the
solutions of the fully discretized system. Numerical results are presented to validate the theoretical results. 相似文献
14.
Extending Scope of Robust Optimization: Comprehensive Robust Counterparts of Uncertain Problems 总被引:2,自引:0,他引:2
In this paper, we propose a new methodology for handling optimization problems with uncertain data. With the usual Robust
Optimization paradigm, one looks for the decisions ensuring a required performance for all realizations of the data from a
given bounded uncertainty set, whereas with the proposed approach, we require also a controlled deterioration in performance
when the data is outside the uncertainty set.
The extension of Robust Optimization methodology developed in this paper opens up new possibilities to solve efficiently multi-stage
finite-horizon uncertain optimization problems, in particular, to analyze and to synthesize linear controllers for discrete
time dynamical systems.
Research was supported by the Binational Science Foundation grant #2002038 相似文献
15.
Marco A. López Andrea B. Ridolfi Virginia N. Vera de Serio 《Nonlinear Analysis: Theory, Methods & Applications》2012,75(3):1461-1482
In this paper, we apply the concept of coderivative and other tools from the generalized differentiation theory for set-valued mappings to study the stability of the feasible sets of both the primal and the dual problem in infinite-dimensional linear optimization with infinitely many explicit constraints and an additional conic constraint. After providing some specific duality results for our dual pair, we study the Lipschitz-like property of both mappings and also give bounds for the associated Lipschitz moduli. The situation for the dual shows much more involved than the case of the primal problem. 相似文献
16.
R. Goldbach 《Applied Mathematics and Optimization》1999,39(1):121-142
We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems,
which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation
and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic
constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present.
We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical
results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered
in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since
many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular,
we do not assume boundedness of the feasible set as required in related methods.
Accepted 7 May 1997 相似文献
17.
《European Journal of Operational Research》1998,107(3):633-643
In this paper we address the problem of the infeasibility of systems defined by quadratic convex inequality constraints. In particular, we investigate properties of irreducible infeasible sets and provide an algorithm that identifies a set of all constraints (K) that may affect the feasibility status of the system after some perturbation of the right-hand sides. We show that all irreducible sets, as well as infeasibility sets, are subsets of the set K, and that every infeasible system contains an inconsistent subsystem of cardinality not greater than the number of variables plus one. The results presented in this paper are also applicable to linear systems. 相似文献
18.
Dao-Lan Han Jin-Bao Jian Jie Li 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(9):3022-3032
In this paper, the problem of identifying the active constraints for constrained nonlinear programming and minimax problems at an isolated local solution is discussed. The correct identification of active constraints can improve the local convergence behavior of algorithms and considerably simplify algorithms for inequality constrained problems, so it is a useful adjunct to nonlinear optimization algorithms. Facchinei et al. [F. Facchinei, A. Fischer, C. Kanzow, On the accurate identification of active constraints, SIAM J. Optim. 9 (1998) 14-32] introduced an effective technique which can identify the active set in a neighborhood of a solution for nonlinear programming. In this paper, we first improve this conclusion to be more suitable for infeasible algorithms such as the strongly sub-feasible direction method and the penalty function method. Then, we present the identification technique of active constraints for constrained minimax problems without strict complementarity and linear independence. Some numerical results illustrating the identification technique are reported. 相似文献
19.
F. Guerra Vázquez J.-J. Rückmann O. Stein G. Still 《Journal of Computational and Applied Mathematics》2008
This tutorial presents an introduction to generalized semi-infinite programming (GSIP) which in recent years became a vivid field of active research in mathematical programming. A GSIP problem is characterized by an infinite number of inequality constraints, and the corresponding index set depends additionally on the decision variables. There exist a wide range of applications which give rise to GSIP models; some of them are discussed in the present paper. Furthermore, geometric and topological properties of the feasible set and, in particular, the difference to the standard semi-infinite case are analyzed. By using first-order approximations of the feasible set corresponding constraint qualifications are developed. Then, necessary and sufficient first- and second-order optimality conditions are presented where directional differentiability properties of the optimal value function of the so-called lower level problem are used. Finally, an overview of numerical methods is given. 相似文献
20.
In this paper we consider the power utility maximization problem under partial information in a continuous semimartingale setting. Investors construct their strategies using the available information, which possibly may not even include the observation of the asset prices. Resorting to stochastic filtering, the problem is transformed into an equivalent one, which is formulated in terms of observable processes. The value process, related to the equivalent optimization problem, is then characterized as the unique bounded solution of a semimartingale backward stochastic differential equation (BSDE). This yields a unified characterization for the value process related to the power and exponential utility maximization problems, the latter arising as a particular case. The convergence of the corresponding optimal strategies is obtained by means of BSDEs. Finally, we study some particular cases where the value process admits an explicit expression. 相似文献