Finding an interior point in the optimal face of linear programs

We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n ³ L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.Research supported in part by NSF Grant CCR-8810107, CCR-9019469 and a grant from GTE Laboratories.Research supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615 through Rice University.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

Global Optimization Method for Solving Mathematical Programs with Linear Complementarity Constraints

We propose a method for finding a global optimal solution of programs with linear complementarity constraints. This problem arises for instance in bilevel programming. The main idea of the method is to generate a sequence of points either ending at a global optimal solution within a finite number of iterations or converging to a global optimal solution. The construction of such sequence is based on branch-and-bound techniques, which have been used successfully in global optimization. Results on a numerical test of the algorithm are reported.The main part of this article was written during the first authors stay as Visiting Professor at the Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Japan. The second and the third authors were supported by Grant-in-Aid for Scientific Research C(2) 13650061 of the Ministry of Education, Culture, Sports, Science, and\break Technology of Japan.The authors thank P. B. Hermanns, Department of Mathematics, University of Trier, for carrying out the numerical test reported in Section 5. The authors also thank the referees and the Associate Editor for comments and suggestions which helped improving the first version of this article.     

A Gauss-Seidel iteration method for nonlinear variational inequality problems over rectangles

This paper presents a simple yet practically useful Gauss-Seidel iterative method for solving a class of nonlinear variational inequality problems over rectangles and of nonlinear complementarity problems. This scheme is a nonlinear generalization of a robust iterative method for linear complementarity problems developed by Mangasarian. Global convergence is presented for problems with Z-functions. It is noted that the suggested method can be viewed as a specific case of a class of linear approximation methods studied by Pang and others.     

PROPERTIES OF TENSOR COMPLEMENTARITY PROBLEM AND SOME CLASSES OF STRUCTURED TENSORS

This paper deals with the class of Q-tensors, that is, a Q-tensor is a real tensor A such that the tensor complementarity problem(q, A):finding an x ∈ R~n such that x ≥ 0, q+Ax~(m-1)≥ 0, and x~T(q+Ax~(m-1)) = 0,has a solution for each vector q ∈ R~n. Several subclasses of Q-tensors are given: P-tensors, R-tensors, strictly semi-positive tensors and semi-positive R_0-tensors. We prove that a nonnegative tensor is a Q-tensor if and only if all of its principal diagonal entries are positive, and so the equivalence of Q-tensor,R-tensors, strictly semi-positive tensors was showed if they are nonnegative tensors. We also show that a tensor is an R_0-tensor if and only if the tensor complementarity problem(0, A) has no non-zero vector solution, and a tensor is a R-tensor if and only if it is an R_0-tensor and the tensor complementarity problem(e, A) has no non-zero vector solution, where e =(1, 1 ···, 1)~T.     

一种新的遗传算法最优保存策略

提出了一种新的遗传算法最优保存策略,该策略在最优个体保留的基础上,添加一个与最优个体相异因子较大,而适应值不过小的个体.这样做既利用了最优保存策略的全局收敛性,又通过新添加的个体来保持种群的多样性,以防止早熟现象的出现.对典型优化函数进行了测试,结果表明基于新的最优保存策略的遗传算法(DESGA)收敛性能显著好于一般简单遗传算法(SGA)和最优保存简单遗传算法(ESGA).该策略与最优保存策略一样具有一般通用性.     

Levenberg-Marquardt method with a general LM parameter and a nonmonotone trust region technique

We propose a new Levenberg-Marquardt (LM) method for solving the nonlinear equations. The new LM method takes a general LM parameter \lambda_k=\mu_k[(1-\theta)\|F_k\|^\delta+\theta\|J_k^TF_k\|^\delta] where \theta\in[0,1] and \delta\in(0,3) and adopts a nonmonotone trust region technique to ensure the global convergence. Under the local error bound condition, we prove that the new LM method has at least superlinear convergence rate with the order \min\{1+\delta,4-\delta,2\}. We also apply the new LM method to solve the nonlinear equations arising from the weighted linear complementarity problem. Numerical experiments indicate that the new LM method is efficient and promising.     

The Generalized Order Tensor Complementarity Problems

The main propose of this paper is devoted to studying the solvability of the generalized order tensor complementarity problem. We define two problems: the generalized order tensor complementarity problem and the vertical tensor complementarity problem and show that the former is equivalent to the latter. Using the degree theory, we present a comprehensive analysis of existence, uniqueness and stability of the solution set of a given generalized order tensor complementarity problem.