Export 7 results:
Sort by: Author Title Type [ Year  (Desc)]
In Press
Brás, C. P., A. N. Iusem, and J. J. Júdice. "On the Quadratic Eigenvalue Complementarity Problem." Journal of Global Optimization, DOI: 10.1007/s10898-014-0260-5. (In Press).
Brás, C., G. Eichfelder, and J. Júdice. "Copositivity tests based on the Linear Complementarity Problem." Computational Optimization and Applications. 63.2 (2016): 461-493. AbstractWebsite

We present copositivity tests based on new necessary and sufficient conditions which require the solution of linear complementarity problems (LCP). We propose methodologies involving Lemke’s method, an enumerative algorithm and a linear mixed-integer programming formulation to solve the required LCPs. Moreover, we discuss a new necessary condition for (strict) copositivity based on solving a linear program, which can be used as a preprocessing step. The algorithms with these three different variants are thoroughly applied to test matrices from the literature and to max-clique instances with matrices of order up to 496×496. We compare our procedures with three other copositivity tests from the literature as well as with a general global optimization solver. The numerical results are very promising and equally good and in many cases better than the results reported elsewhere.

Brás, C. P., M. Fukushima, A. N. Iusem, and J. J. Júdice. "On the Quadratic Eigenvalue Complementarity Problem over a General Convex Cone." Applied Mathematics and Computation. 271 (2015): 594-608. AbstractWebsite

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.

Brás, C. P., J. J. Júdice, and H. D. Sherali. "On the Solution of the Inverse Eigenvalue Complementarity Problem." Journal of Optimization Theory and Applications. 162 (2014): 88-106. AbstractWebsite

In this paper, we discuss the solution of an Inverse Eigenvalue Complementarity Problem. Two nonlinear formulations are presented for this problem. A necessary and sufficient condition for a stationary point of the first of these formulations to be a solution of the problem is established. On the other hand, for assuring global convergence to a solution of this problem when it exists, an enumerative algorithm is designed by exploiting the structure of the second formulation. The use of additional implied constraints for enhancing the efficiency of the algorithm is also discussed. Computational results are provided to highlight the performance of the algorithm.

Brás, C. P., W. W. Hager, and J. J. Júdice. "An investigation of feasible descent algorithms for estimating the condition number of a matrix." TOP - Journal of the Spanish Society of Statistics and Operations Research. 20 (2012): 791-809. AbstractWebsite

Techniques for estimating the condition number of a nonsingular matrix are developed. It is shown that Hager's 1-norm condition number estimator is equivalent to the conditional gradient algorithm applied to the problem of maximizing the 1-norm of a matrix-vector product over the unit sphere in the 1-norm. By changing the constraint in this optimization problem from the unit sphere to the unit simplex, a new formulation is obtained which is the basis for both conditional gradient and projected gradient algorithms. In the test problems, the spectral projected gradient algorithm yields condition number estimates at least as good as those obtained by the previous approach. Moreover, in some cases, the spectral gradient projection algorithm, with a careful choice of the parameters, yields improved condition number estimates.

Brás, C. P., M. Fukushima, J. J. Júdice, and S. S. Rosa. "Variational Inequality Formulation of the Asymmetric Eigenvalue Complementarity Problem and Its Solution by Means of Gap Functions." Pacific Journal of Optimization. 8.(2) (2012): 197-215. AbstractWebsite

In this paper, the solution of the asymmetric eigenvalue complementarity problem (EiCP) is investigated by means of a variational inequality formulation. This problem is then solved by finding a stationary point of the gap function and the regularized gap function. A nonlinear programming formulation of the EiCP results from the gap function. A hybrid algorithm combining a projection technique and a modified Josephy-Newton method is proposed to solve the EiCP by finding a stationary point of the regularized gap function. Numerical results show that the proposed method can in general solve EiCPs efficiently.

Brás, C. P., and J. J. Júdice Complementary approaches for the computation of the independent number of a graph. Proceedings of the 14th WSEAS International Conference on Applied Mathematics (MATH’09). Tenerife, Spain, 2009. Abstract

The problem of finding the independent number of an undirected graph is formulated as two equivalent Mathematical Programs with Linear Complementarity Constraints (MPLCC). A multistarting Lemke’s method
is introduced for dealing with the first formulation and is able to find a good approximate of the independent
number in a finite number of iterations. A sequential complementary algorithm is also discussed for the second formulation and can find the independent number at least in theory. Some computational experience is included to highlight the efficacy of the complementary approaches for computing the independent number of graphs from the Dimacs collection.