Search

We introduce an Alternating Direction Method of Multipliers (ADMM) for finding a solution of the nonsymmetric Eigenvalue Complementarity Problem (EiCP). A simpler version of this method is proposed for the symmetric EiCP, that is, for the computation of a Stationary Point (SP) of a Standard Fractional Quadratic Program. The algorithm is also extended for the computation of an SP of a Standard Quadratic Program (StQP). Convergence analyses of these three versions of ADMM are presented. The main computational effort of ADMM is the solution of a Strictly Convex StQP, which can be efficiently solved by a Block Principal Pivoting algorithm. Furthermore, this algorithm provides a stopping criterion for ADMM that improves very much its efficacy to compute an accurate solution of the EiCP. Numerical results indicate that ADMM is in general very efficient for solving symmetric EiCPs in terms of the number of iterations and computational effort, but is less efficient for the solution of nonsymmetric EiCPs. However, ADMM is able to provide a good initial point for a fast second-order method, such as the so-called Semismooth Newton method. The resulting hybrid ADMM and SN algorithm seems to be quite efficient in practice for the solution of nonsymmetric EiCPs. [ABSTRACT FROM AUTHOR]

We study splitting methods for solving the Eigenvalue Complementarity Problem (EiCP). We introduce four variants, which depend on the properties (symmetry, nonsymmetry, positive definite, negative definite, indefinite) of the matrices included in the definition of EiCP. Convergence analyses for each one of these versions of the splitting method are discussed. Special choices for the splitting matrices associated with these versions are recommended and tested on the solution of small and large symmetric and nonsymmetric EiCPs. These experiments show that the four versions of the splitting method work well at least for some choices of the splitting matrices. Furthermore, these versions of the splitting methods seem to be competitive with the most efficient state-of-the-art algorithms for the solution of EiCP. [ABSTRACT FROM AUTHOR]

In this paper, the solution of the symmetric quadratic eigenvalue complementarity problem (QEiCP) is addressed. The QEiCP has a solution provided the so-called co-regular and co-hyperbolic properties hold and is said to be symmetric if all the matrices involved in its definition are symmetric. We show that under the two conditions stated above the symmetric QEiCP can be reduced to the problem of computing a stationary point of an appropriate nonlinear program (NLP). We also investigate the reduction of the QEiCP to a simpler eigenvalue complementarity problem (EiCP). This transformation enables us to show that the co-regular and co-hyperbolic properties are not necessary for the existence of a solution to the QEiCP. Furthermore the QEiCP is shown to be equivalent to the problem of finding a stationary point of a quadratic fractional program (QFP) under special conditions on the matrices of the QEiCP. The use of the so-called spectral projected-gradient (SPG) algorithm for dealing with the programs NLP and QFP is also investigated. Some considerations about the implementation of this algorithm are discussed. Computational experience is included to highlight the efficiency of the algorithm for finding a solution of the QEiCP by exploring the NLPs mentioned above. [ABSTRACT FROM PUBLISHER]

In this paper a discrete location model for non-essential service facilities planning is described, which seeks the number, location, and size of facilities, that maximizes the total expected demand attracted by the facilities. It is assumed that the demand for service is sensitive to the distance from facilities and to their size. It is also assumed that facilities must satisfy a threshold level of demand (facilities are not economically viable below that level). A Mixed-Integer Nonlinear Programming (MINLP) model is proposed for this problem. A branch-and-bound algorithm is designed for solving this MINLP and its convergence to a global minimum is established. A finite procedure is also introduced to find a feasible solution for the MINLP that reduces the overall search in the binary tree generated by the branch-and-bound algorithm. Some numerical results using a GAMS/MINOS implementation of the algorithm are reported to illustrate its efficacy and efficiency in practice. [ABSTRACT FROM AUTHOR]

This article discusses an engineering optimization problem which arises in hydraulics and is related to the use of a new criterion for sizing water distribution piping in large buildings. The optimization model aims to find the most suitable interior pipe diameters for the various pipes in the system, using commercial sizes and minimizing the overall installation cost according to some boundary conditions. The problem is formulated as a non-convex nonlinear program and a branch-and-bound algorithm is introduced for its solution. A procedure is proposed to obtain a feasible solution with standard values from the optimal solution of the non-convex program. The performance of the algorithm is analysed for a real-life problem and the cost of the computed solution is assessed, showing the appropriateness of the model and the optimization techniques. [ABSTRACT FROM AUTHOR]

In this paper, we address the solution of the symmetric eigenvalue complementarity problem (EiCP) by treating an equivalent reformulation of finding a stationary point of a fractional quadratic program on the unit simplex. The spectral projected-gradient (SPG) method has been recommended to this optimization problem when the dimension of the symmetric EiCP is large and the accuracy of the solution is not a very important issue. We suggest a new algorithm which combines elements from the SPG method and the block active set method, where the latter was originally designed for box constrained quadratic programs. In the new algorithm the projection onto the unit simplex in the SPG method is replaced by the much cheaper projection onto a box. This can be of particular advantage for large and sparse symmetric EiCPs. Global convergence to a solution of the symmetric EiCP is established. Computational experience with medium and large symmetric EiCPs is reported to illustrate the efficacy and efficiency of the new algorithm. [ABSTRACT FROM AUTHOR]

The eigenvalue complementarity problem (EiCP) differs from the traditional eigenvalue problem in that the primal and dual variables belong to a closed and convex coneKand its dual, respectively, and satisfy a complementarity condition. In this paper we investigate the solution of the second-order cone EiCP (SOCEiCP) whereKis the Lorentz cone. We first show that the SOCEiCP reduces to a special Variational Inequality Problem on a compact set defined byKand a normalization constraint. This guarantees that SOCEiCP has at least one solution, and a new enumerative algorithm is introduced for finding a solution to this problem. The method is based on finding a global minimum of an appropriate nonlinear programming (NLP) formulation of the SOCEiCP using a special branching scheme along with a local nonlinear optimizer that computes stationary points on subsets of the feasible region of NLP associated with the nodes generated by the algorithm. A semi-smooth Newton's method is combined with this enumerative algorithm to enhance its numerical performance. Our computational experience illustrates the efficacy of the proposed techniques in practice. [ABSTRACT FROM AUTHOR]

The Vertical Generalized Linear Complementarity Problem (VGLCP) is an extension of the well-known Linear Complementarity Problem (LCP) that has been discussed in the literature and has found many interesting applications in the past several years. A Block Principal Pivoting (BPP) algorithm was designed for finding the unique solution of the LCP when the matrix of this problem is a P-matrix and shown to be quite efficient for solving large-scale LCPs. In this paper, we introduce an extension of this BPP algorithm for finding the unique solution of the VGLCP when its matrix is a vertical block P-matrix. A Least-Index Single Principal Pivoting (LISPP) algorithm is used as a safeguard to guarantee convergence for the BPP algorithm in a finite number of iterations. Computational experiments with a number of VGLCP test problems indicate that the new BPP algorithm is quite efficient for computing the unique solution of large-scale VGLCPs with vertical block P-matrices in practice. [ABSTRACT FROM AUTHOR]

In this article, we study the bi-level linear programming problem with multiple objective functions on the upper level (with particular focus on the bi-objective case) and a single objective function on the lower level. We have restricted our attention to this type of problem because the consideration of several objectives at the lower level raises additional issues for the bi-level decision process resulting from the difficulty of anticipating a decision from the lower level decision maker. We examine some properties of the problem and propose a methodological approach based on the reformulation of the problem as a multiobjective mixed 0–1 linear programming problem. The basic idea consists in applying a reference point algorithm that has been originally developed as an interactive procedure for multiobjective mixed-integer programming. This approach further enables characterization of the whole Pareto frontier in the bi-objective case. Two illustrative numerical examples are included to show the viability of the proposed methodology. [ABSTRACT FROM PUBLISHER]

The solution of the Conic Quadratic Eigenvalue Complementarity Problem (CQEiCP) is first investigated without assuming symmetry on the matrices defining the problem. A new sufficient condition for existence of solutions of CQEiCP is presented, extending to arbitrary pointed, closed and convex cones a condition known to hold when the cone is the nonnegative orthant. We also address the symmetric CQEiCP where all its defining matrices are symmetric. We show that, assuming that two of its defining matrices are positive definite, this symmetric CQEiCP reduces to the computation of a stationary point of an appropriate merit function on a convex set. Furthermore, we discuss the use of the so called Spectral Projected Gradient (SPG) algorithm for solving CQEiCP when the cone of interest is the second-order cone (SOCQEiCP). A new algorithm is designed for the computation of the projections required by the SPG method to deal with SOCQEiCP. Numerical results are included to illustrate the efficiency of the SPG method and the new projection technique in practice. [ABSTRACT FROM AUTHOR]