-
作者：Goldfarb, D; Scheinberg, K
作者单位：Columbia University; International Business Machines (IBM); IBM USA
摘要：Cholesky factorization has become the method of choice for solving the symmetric system of linear equations arising in interior point methods (IPMs) for linear programming (LP), its main advantages being numerical stability and efficiency for sparse systems. However in the presence of dense columns there is dramatic loss of efficiency. A typical approach to remedy this problem is to apply the Sherman-Morrison-Woodbury (SMW) update formula to the dense part. This approach while being very effic...
-
作者：Kocvara, M; Outrata, JV
作者单位：University of Erlangen Nuremberg; Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences
摘要：We consider a class of optimization problems with a generalized equation among the constraints. This class covers several problem types like MPEC (Mathematical Programs with Equilibrium Constraints) and MPCC (Mathematical Programs with Complementarity Constraints). We briefly review techniques used for numerical solution of these problems: penalty methods, nonlinear programming (NLP) techniques and Implicit Programming approach (ImP). We further present a new theoretical framework for the ImP ...
-
作者：Hall, JAJ; McKinnon, KIM
作者单位：University of Edinburgh
摘要：This paper introduces a class of linear programming examples that cause the simplex method to cycle and that are the simplest possible examples showing this behaviour. The structure of examples from this class repeats after two iterations. Cycling is shown to occur for both the most negative reduced cost and steepest-edge column selection criteria. In addition it is shown that the EXPAND anti-cycling procedure of Gill et al. is not guaranteed to prevent cycling.
-
作者：Kolliopoulos, SG; Stein, C
作者单位：McMaster University; Columbia University; Dartmouth College
摘要：In a packing integer program, we are given a matrix A and column vectors b,c with nonnegative entries. We seek a vector x of nonnegative integers, which maximizes c(T)x, subject to Axless than or equal tob. The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connect...
-
作者：Lawphongpanich, S; Hearn, DW
作者单位：State University System of Florida; University of Florida
摘要：This paper addresses two second-best toll pricing problems, one with fixed and the other with elastic travel demands, as mathematical programs with equilibrium constraints. Several equivalent nonlinear programming formulations for the two problems are discussed. One formulation leads to properties that are of interest to transportation economists. Another produces an algorithm that is capable of solving large problems and easy to implement with existing software for linear and nonlinear progra...
-
作者：Hamdouch, Y; Marcotte, P; Nguyen, S
作者单位：Universite de Montreal; Universite de Montreal
摘要：In a transit network involving vehicles with rigid capacities, we advocate the use of strategies for describing consumer behavior. At each boarding node, a user sorts the transit lines in decreasing order of preference, and boards the first vehicle in this list whose residual capacity is nonzero. Since a user's position in the queue varies from day to day, the delay experienced is stochastic. This leads to an equilibrium problem where, at a solution. users are assigned to strategies that minim...
-
作者：Hobbs, BF; Pang, JS
作者单位：Johns Hopkins University; Rensselaer Polytechnic Institute
摘要：This paper considers equilibria among multiple firms that are competing non-cooperatively against each other to sell electric power and buy resources needed to produce that power. Examples of such resources include fuels, power plant sites, and emissions allowances. The electric power market is a spatial market on a network in which flows are constrained by Kirchhoff's current and voltage laws. Arbitragers in the power market erase spatial price differences that are non-cost based. Power produ...
-
作者：Cheung, D; Cucker, F
作者单位：City University of Hong Kong
摘要：We define a condition number K(A,b,c) for a linear program min c(T)x s.t. Ax=b,xgreater than or equal to0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log K(A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution.
-
作者：Chen, JS; Chen, X; Tseng, P
作者单位：University of Washington; University of Washington Seattle; Massachusetts Institute of Technology (MIT)
摘要：Let K-n be the Lorentz/second-order cone in R-n. For any function f from R to R, one can define a corresponding function f(soc)(x) on R-n by applying f to the spectral values of the spectral decomposition of x is an element of R-n with respect to K-n. We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Frechet differentiability, continuous differentiability, as well as (rho-order) semismoothness. Th...
-
作者：Hintermüller, M; Ulbrich, M
作者单位：University of Graz; Rice University; University of Hamburg
摘要：For a class of semismooth operator equations a mesh independence result for generalized Newton methods is established. The main result states that the continuous and the discrete Newton process, when initialized properly, converge q-linearly with the same rate. The problem class considered in the paper includes MCP-function based reformulations of first order conditions of a class of control constrained optimal control problems for partial differential equations for which a numerical validatio...
