Partial penalization for the solution of generalized Nash equilibrium problems

In this paper we reformulate the generalized Nash equilibrium problem (GNEP) as a nonsmooth Nash equilibrium problem by means of a partial penalization of the difficult coupling constraints. We then propose a suitable method for the solution of the penalized problem and we study classes of GNEPs for which the penalty approach is guaranteed to converge to a solution. In particular, we are able to prove convergence for an interesting class of GNEPs for which convergence results were previously unknown.     

惩罚框架下求解广义Nash均衡问题的分解算法

广义Nash均衡问题(GNEP),是非合作博弈论中一类重要的问题,它在经济学、管理科学和交通规划等领域有着广泛的应用.本文主要提出一种新的惩罚算法来求解一般的广义Nash均衡问题,并根据罚函数的特殊结构,采用交替方向法求解子问题.在一定的条件下,本文证明新算法的全局收敛性.多个数值例子的试验结果表明算法是可行的,并且是有效的.     

Solving singularly constrained generalized network problems

The singularly constrained generalized network problem represents a large class of capacitated linear programming (LP) problems. This class includes any LP problem whose coefficient matrix, ignoring single upper bound constraints, containsm + 1 rows which may be ordered such that each column has at most two non-zero entries in the firstm rows. The paper describes efficient procedures for solving such problems and presents computational results which indicate that, on large problems, these procedures are at least twenty-five times more efficient than the state of the art LP systemapex-iii.This research was partly supported by ONR Contract N00014-76-C-0383 with Decision Analysis and Research Institute and by Project NR047-021, ONR Contracts N00014-75-C-0616 and N00014-75-C-0569 with the Center for Cybernetic Studies, The University of Texas. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

A NEW GENERALIZED GRADIENT PROJECTION TYPEALGORITHM FOR LINEARLY CONSTRAINED PROBLEMS

In this paper, we provide a new generalized gradient projection algorithm for nonlinear programming problems with linear constraints. This algorithm has simple structure and is very practical and stable. Under the weaker assumptions, we have proved the global convergence of our algorithm.     

Pseudopower expansion of solutions of generalized equations and constrained optimization problems

We show that the solution of a strongly regular generalized equation subject to a scalar perturbation expands in pseudopower series in terms of the perturbation parameter, i.e., the expansion of orderk is the solution of generalized equations expanded to orderk and thus depends itself on the perturbation parameter. In the polyhedral case, this expansion reduces to a usual Taylor expansion. These results are applied to the problem of regular perturbation in constrained optimization. We show that, if the strong regularity condition is satisfied, the property of quadratic growth holds and, at least locally, the solutions of the optimization problem and of the associated optimality system coincide. If, in addition the number of inequality constraints is finite, the solution and the Lagrange multiplier can be expanded in Taylor series. If the data are analytic, the solution and the multiplier are analytic functions of the perturbation parameter.     

Homogenization and penalization of functional first-order PDE

In this paper we study the asymptotic behavior of viscosity solutions for a functional partial differential equation with a small parameter as the parameter tends to zero. We study simultaneous effects of homogenization and penalization in functional first-order PDE. We establish a convergence theorem in which the limit equation is identified with some first order PDE.     

Gap functions and penalization for solving equilibrium problems with nonlinear constraints

The paper deals with equilibrium problems (EPs) with nonlinear convex constraints. First, EP is reformulated as a global optimization problem introducing a class of gap functions, in which the feasible set of EP is replaced by a polyhedral approximation. Then, an algorithm is given for solving EP through a descent type procedure, which exploits also exact penalty functions, and its global convergence is proved. Finally, the algorithm is tested on a network oligopoly problem with nonlinear congestion constraints.     

A weighted pseudoinverse,generalized singular values,and constrained least squares problems

The weighted pseudoinverse providing the minimum semi-norm solution of the weighted linear least squares problem is studied. It is shown that it has properties analogous to those of the Moore-Penrose pseudoinverse. The relation between the weighted pseudoinverse and generalized singular values is explained. The weighted pseudoinverse theory is used to analyse least squares problems with linear and quadratic constraints. A numerical algorithm for the computation of the weighted pseudoinverse is briefly described.This work was supported in part by the Swedish Institute for Applied Mathematics.     

On approximation in total variation penalization for image reconstruction and inverse problems

In this paper, we examine some theoretical issues associated with the use of total variation based image reconstruction. Our investigations are motivated by problems of inverse interferome-try, in which laser light phase shifts are used to reconstruct medium density profiles in flow field sensing. The reconstruction problem is posed as a residual minimization with total variation reg-ularization applied to handle the inherent ill-posedness. We consider numerical approximations of these penalized minimal residual problems, and analyze some approximation strategies and their properties. The standard definition of total variation leads to inconsistent approximations, with piecewise constant basis functions, so we consider alternative definitions, which preserve the needed compactness and produce convergent approximations.     

Stability for linearly constrained optimization problems

We deal with finite dimensional differentiable optimization problems under linear constraints. Stability of stationary solutions under restricted perturbations of the constraints will be characterized. The restriction on the constraint perturbations is given by means of a certain rank condition; in particular, righthandside perturbations are allowed.Corresponding author.     

Regularity conditions for constrained extremum problems

Necessary and/or sufficient conditions are stated in order to have regularity for nondifferentiable problems or differentiable problems. These conditions are compared with some known constraint qualifications.     

Convex constrained optimization for large-scale generalized Sylvester equations

We propose and study the use of convex constrained optimization techniques for solving large-scale Generalized Sylvester Equations (GSE). For that, we adapt recently developed globalized variants of the projected gradient method to a convex constrained least-squares approach for solving GSE. We demonstrate the effectiveness of our approach on two different applications. First, we apply it to solve the GSE that appears after applying left and right preconditioning schemes to the linear problems associated with the discretization of some partial differential equations. Second, we apply the new approach, combined with a Tikhonov regularization term, to restore some blurred and highly noisy images.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

Convexity of chance constrained programming problems with respect to a new generalized concavity notion

In this paper, convexity of chance constrained problems have been investigated. A new generalization of convexity concept, named h-concavity, has been introduced and it has been shown that this new concept is the generalization of the ??-concavity. Then, using the new concept, some of the previous results obtained by Shapiro et al. [in Lecture Notes on Stochastic Programming Modeling and Theory, SIAM and MPS, 2009] on properties of ??-concave functions, have been extended. Next the convexity of chance constraints with independent random variables is investigated. It will be shown how concavity properties of the mapping related to the decision vector have to be combined with suitable properties of decrease or increase for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels and then sufficient conditions for convexity of chance constrained problems which has been introduced by Henrion and Strugarek [in Convexity of chance constraints with independent random variables. Comput. Optim. Appl. 41:263?C276, 2008] has been extended in this paper for a wider class of real functions.     

Scaled constraint qualifications for generalized equation constrained problems and application to nonsmooth mathematical programs with equilibrium constraints

Positivity - In this paper, the notion of graphical derivatives is applied to define a new class of several well-known constraint qualifications for a nonconvex multifunction M at a point of its...     

Levitin-poyak well-posedness of generalized vector equilibrium problems with functional constraints

In this article, we study Levitin-Polyak type well-posedness for generalized vector equilibrium problems with abstract and functional constraints. Criteria and characterizations for these types of well-posednesses are given.     

Levitin-Polyak well-posedness of generalized vector quasi-equilibrium problems with functional constraints

In this paper, we introduce several types of Levitin-Polyak well-posedness for a generalized vector quasi-equilibrium problem with functional constraints and abstract set constraints. Criteria and characterizations of these types of Levitin-Polyak well-posedness with or without gap functions of generalized vector quasi-equilibrium problem are given. The results in this paper unify, generalize and extend some known results in the literature.     

On a class of constrained functional minimization problems and their numerical solution

We investigate a class of functional minimization problems with constraints. By means of variational principles, optimal control theory, and numerical methods for nonlinear equations, numerical methods and the corresponding computer software are established to solve the problems. These tools can be used in fitting curves with arbitrary smoothness, different boundary conditions, and constraints. For special boundary conditions, analytical expressions of the curves are derived. Numerical examples are given to demonstrate the effectiveness of the algorithms by the means of curve fitting.     

Regularity of components in optimal design problems with perimeter penalization

We consider minimal energy configurations of mixtures of two materials in , where the energy includes a penalty on the length of the interface between the materials. We show that, for one of the materials, the boundary of each component is smooth, and we prove the existence of an upper bound on the relative distances between components. Received: 24 March 2000 / Accepted: 25 October 2001 / Published online: 29 April 2002