Primal-dual affine scaling interior point methods for linear complementarity problems

A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary … Read more

A Path to the Arrow-Debreu Competitive Market Equilibrium

We present polynomial-time interior-point algorithms for solving the Fisher and Arrow-Debreu competitive market equilibrium problems with linear utilities and $n$ players. Both of them have the arithmetic operation complexity bound of $O(n^4\log(1/\epsilon))$ for computing an $\epsilon$-equilibrium solution. If the problem data are rational numbers and their bit-length is $L$, then the bound to generate an … Read more

A Note on Exchange Market Equilibria with Leontief’s Utility: Freedom of Pricing Leads to Rationality

We extend the analysis of [27] to handling more general utility functions: piece-wise linear functions, which include Leontief’s utility. We show that the problem reduces to the general analytic center model discussed in [27]. Thus, the same linear programming complexity bound applies to approximating the Fisher equilibrium problem with these utilities. More importantly, we show … Read more

An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version

We discuss local convergence of Newton’s method to a singular solution $x^*$ of the nonlinear equations $F(x) = 0$, for $F:\R^n \rightarrow \R^n$. It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution $x^*$ from a starlike domain around $x^*$ for $F$ twice Lipschitz continuously differentiable and $x^*$ satisfying … Read more

Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path

Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path CitationTechnical Report UMBC, TR2006-22, January 2005, Revised: March 2006.ArticleDownload View PDF

Erratum: Predictor-corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path,

We correct an error in Algorithms 4.1 and 4.8 from the paper with the same title that was published in Optimization Methods and Software, 20, 1 (2005), 145–168. Citationsubmitted to Optimization Methods and SoftwareArticleDownload View PDF

Erratum: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with (\sqrt{n}L)hBciteration complexity

We correct an error in Algorithm 2 from the paper with the same name that was published in Mathematical Programming, Ser. A, 100, 2(2004), 317–337. Citationsubmitted to Mathematical ProgrammingArticleDownload View PDF

Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

Two corrector-predictor interior point algorithms are proposed for solving mono\-tone linear complementarity problems. The algorithms produce a sequence of iterates in the $\caln_{\infty}^{-}$ neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm … Read more

Using EPECs to model bilevel games in restructured electricity markets

We study a bilevel noncooperative game-theoretic model of restructured electricity markets, with locational marginal prices. Each player in this game faces a bilevel optimization problem that we remodel as a mathematical program with equilibrium constraints, MPEC. The corresponding game is an example of an EPEC, equilibrium problem with equilibrium constraints. We establish sufficient conditions for … Read more