We exploit a recently proposed local error bound condition for a nonsmooth reformulation of the Karush-Kuhn-Tucker conditions of generalized Nash equilibrium problems (GNEPs) to weaken the theoretical convergence assu...
详细信息
We exploit a recently proposed local error bound condition for a nonsmooth reformulation of the Karush-Kuhn-Tucker conditions of generalized Nash equilibrium problems (GNEPs) to weaken the theoretical convergence assumptions of a hybrid method for GNEPs that uses a smooth reformulation. Under the presented assumptions the hybrid method, which combines a potential reduction algorithm and an LP-Newton method, has global and fast local convergence properties. Furthermore we adapt the algorithm to a nonsmooth reformulation, prove under some additional strong assumptions similar convergence properties as for the smooth reformulation, and compare the two approaches.
This paper considers the numerical solution of linear generalized Nash equilibrium problems (LGNEPs). Since many methods for nonlinear problems require the nonsingularity of some second-order derivative, standard conv...
详细信息
This paper considers the numerical solution of linear generalized Nash equilibrium problems (LGNEPs). Since many methods for nonlinear problems require the nonsingularity of some second-order derivative, standard convergence conditions are not satisfied in our linear case. We provide new convergence criteria for a potential reduction algorithm (PRA) that allow its application to LGNEPs. Furthermore, we discuss a projected subgradient method (PSM) and a penalty method that exploit some known Nikaido-Isoda function-based constrained and unconstrained optimization reformulations of the LGNEP. Moreover, it is shown that normalized Nash equilibria of an LGNEP can be obtained by solving a single linear program. All proposed algorithms are tested on randomly generated instances of economic market models that are introduced and analysed in this paper and that lead to LGNEPs with shared and with non-shared constraints. It is shown that these problems have some favourable properties that can be exploited to obtain their solutions. With the PRA and in particular with the PSM we are able to compute solutions with satisfying precision even for problems with up 10,000 variables.
In an interference limited network, joint power and admission control (JPAC) aims at supporting a maximum number of links at their specified signal-to-interference-plus-noise ratio (SINR) targets while using minimum t...
详细信息
In an interference limited network, joint power and admission control (JPAC) aims at supporting a maximum number of links at their specified signal-to-interference-plus-noise ratio (SINR) targets while using minimum total transmission power. Various convex approximation deflation approaches have been developed for the JPAC problem. In this paper, we propose an effective polynomial time non-convex approximation deflation approach for solving the problem. The approach is based on the non-convex l(q) (0 < q < 1) approximation of an equivalent sparse to reformulation of the JPAC problem. We show that, for any instance of the JPAC problem, there exists (q) over bar is an element of (0, 1) such that it can be exactly solved by solving its l(q) approximation problem with any q is an element of (0, (q) over bar]. We also show that finding the global solution of the l(q) approximation problem is NP-hard. Then, we propose a potentialreduction interior-point algorithm, which can return an epsilon-KKT solution of the NP-hard tq approximation problem in polynomial time. The returned solution can be used to check the simultaneous supportability of all links in the network and to guide an iterative link removal procedure, resulting in the polynomial time non-convex approximation deflation approach for the JPAC problem. Numerical simulations show that the proposed approach outperforms the existing convex approximation approaches in terms of the number of supported links and the total transmission power, particularly exhibiting a quite good performance in selecting which subset of links to support.
We present a new algorithm for the solution of Generalized Nash Equilibrium Problems. This hybrid method combines the robustness of a potential reduction algorithm and the local quadratic convergence rate of the LP-Ne...
详细信息
We present a new algorithm for the solution of Generalized Nash Equilibrium Problems. This hybrid method combines the robustness of a potential reduction algorithm and the local quadratic convergence rate of the LP-Newton method. We base our local convergence theory on a local error bound and provide a new sufficient condition for it to hold that is weaker than known ones. In particular, this condition implies neither local uniqueness of a solution nor strict complementarity. We also report promising numerical results.
A potential reduction algorithm is proposed for optimization of a convex function subject to linear *** each step of the algorithm,a system of linear equations is solved to get a search direction and the Armijo's ...
详细信息
A potential reduction algorithm is proposed for optimization of a convex function subject to linear *** each step of the algorithm,a system of linear equations is solved to get a search direction and the Armijo's rule is used to determine a *** is proved that the algorithm is globally *** results are reported.
This paper deals with a parallel implementation of an interior point algorithm for solving sparse convex quadratic programs with bound constraints. The parallelism is introduced at the linear algebra level. Concerning...
详细信息
This paper deals with a parallel implementation of an interior point algorithm for solving sparse convex quadratic programs with bound constraints. The parallelism is introduced at the linear algebra level. Concerning the solution of the linear system arising at each step of the considered algorithm, we use an iterative approach based on the conjugate gradient method and on a block diagonal preconditioning technique. Moreover, we apply an incomplete Cholesky factorization with limited memory into each block, in order to put together the high degree of parallelism of diagonal preconditioning techniques and the greater effectiveness of incomplete factorizations procedures. The goal is to obtain an efficient parallel interior point solver for general sparse problems. Results of computational experiments carried out on an IBM SP parallel system by using randomly generated very sparse problems without a particular structure are presented. Such results show that the considered inner iterative approach allows to obtain a constant CPU time reduction as the number of processors used increases. (C) 2003 Elsevier Science B.V. All rights reserved.
This paper deals with a parallel implementation of an interior point algorithm for solving sparse convex quadratic programs with bound constraints. The parallelism is introduced at the linear algebra level. Concerning...
详细信息
This paper deals with a parallel implementation of an interior point algorithm for solving sparse convex quadratic programs with bound constraints. The parallelism is introduced at the linear algebra level. Concerning the solution of the linear system arising at each step of the considered algorithm, we use an iterative approach based on the conjugate gradient method and on a block diagonal preconditioning technique. Moreover, we apply an incomplete Cholesky factorization with limited memory into each block, in order to put together the high degree of parallelism of diagonal preconditioning techniques and the greater effectiveness of incomplete factorizations procedures. The goal is to obtain an efficient parallel interior point solver for general sparse problems. Results of computational experiments carried out on an IBM SP parallel system by using randomly generated very sparse problems without a particular structure are presented. Such results show that the considered inner iterative approach allows to obtain a constant CPU time reduction as the number of processors used increases. (C) 2003 Elsevier Science B.V. All rights reserved.
Presents a regular splitting and potentialreduction method for solving a quadratic programming problem with box constraints. Discussion on the regular splitting and potential reduction algorithm; Complexity analysis ...
详细信息
Presents a regular splitting and potentialreduction method for solving a quadratic programming problem with box constraints. Discussion on the regular splitting and potential reduction algorithm; Complexity analysis of the algorithm; Analysis of the complexity bound on obtaining an approximate solution.
This paper extends and analyzes a new potential reduction algorithm for solving smooth convex programming. Under a kind of strict feasibility assumption, we show that the algorithm under modification requires a total ...
详细信息
Primal-dual affine-scaling methods have recently been extended from linear programming to semidefinite programming. We show how to analyze these methods in the framework of potential reduction algorithms. The analysis...
详细信息
Primal-dual affine-scaling methods have recently been extended from linear programming to semidefinite programming. We show how to analyze these methods in the framework of potential reduction algorithms. The analysis suggests implementable variants of the methods as 'long step predictor-corrector' algorithms, where the step length is determined by the potential function. A numerical comparison with the potentialreduction method of Nesterov and Todd is presented. (C) 1999 Elsevier Science B.V. and IMACS. All rights reserved.
暂无评论