A self-adaptive trust region method for the extended linear complementarity problems

By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions. This work is supported by National Natural Science Foundation of China (No. 10671126) and Shanghai Leading Academic Discipline Project (S30501).     

Optimal Synthesis of Steel Frameworks Using Standard Sections* †

This paper presents a computer-based method for optimally sizing members of planar steel frameworks using commercially available standard sections. For first-order behavior and static loads, a minimum-weight structure is found while simultaneously ensuring stress and displacement performance conditions under applied service loads. Architectural conditions are imposed on section sizes to satisfy fabrication requirements related to member continuity and structure symmetry. The design method presented is iterative in nature and remarkably efficient. The number of iterations is generally quite small and almost totally independent: of the complexity of the structure. Designs are presented for two steel frameworks that are typical of those encountered in professional practise.     

互补问题算法的新进展

互补问题是一类重要的优化问题，在最近３０多年的时间里，人们为求解它而提出了许多算法，该文主要介绍１９９０－１９９７年之间出现的某些新算法，它们大致可归类为：（１）光滑方程法；（２）非光滑方程法；（３）可微无约束优化法；（４）ＧＬＰ投影法；（５）内点法；（６）磨光与非内点连续法，文中对每类算法及相应的收敛性结果做了描述与评论，并列出有关文献。     

Degeneracy Subgraph of the Lemke Complementary Pivot Algorithm and Anticycling Rule

In this paper, we use the theory of degeneracy graphs recently developed by Gal et al. to introduce a graph for studying the adjacency of almost complementary feasible bases, some of which may be degenerate, which are of interest in the context of the linear complementarity problem. We study the structure of this graph with particular reference to the possibility of cycling and various anticycling rules in the Lemke complementary pivoting algorithm. We consider the transition node pivot rule introduced by Geue and show that this rule helps in avoiding cycling in the Lemke complementary pivoting algorithm under a suitable assumption.     

Equivalence of the generalized complementarity problem to differentiable unconstrained minimization

We consider an unconstrained minimization reformulation of the generalized complementarity problem (GCP). The merit function introduced here is differentiable and has the property that its global minimizers coincide with the solutions of GCP. Conditions for its stationary points to be global minimizers are given. Moreover, it is shown that the level sets of the merit function are bounded under suitable assumptions. We also show that the merit function provides global error bounds for GCP. These results are based on a condition which reduces to the condition of the uniform P-function when GCP is specialized to the nonlinear complementarity problem. This condition also turns out to be useful in proving the existence and uniqueness of a solution for GCP itself. Finally, we obtain as a byproduct an error bound result with the natural residual for GCP.We thank Jong-Shi Pang for his valuable comments on error bound results with the natural residual for the nonlinear complementarity problem. We are also grateful to the anonymous referees for some helpful comments. The research of the second author was supported in part by the Science Research Grant-in-Aid from the Ministry of Education, Science, and Culture, Japan.     

The prediction–correction approach to nonlinear complementarity problems

This paper presents a prediction–correction approach to solving the nonlinear complementarity problem (NCP). Each iteration of the new method consists of a prediction and a correction. The predictor is produced by an inexact Logarithmic-Quadratic Proximal method; and then it is corrected by the Proximal Point Algorithm. Convergence of the new method is proved under mild assumptions. Comparison to existing methods shows the superiority of the new method. Numerical experiments including the application to traffic equilibrium problems demonstrate that the new method is attractive in practice.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

An NE/SQP Method for the Bounded Nonlinear Complementarity Problem

NE/SQP (Refs. 2–3) is a recent algorithm that has proven quite effective for solving the nonlinear complementarity problem (NCP). NE/SQP is robust in the sense that its direction-finding subproblems are always solvable; in addition, the convergence rate of this method is q-quadratic. In this note, we consider a generalized version of NE/SQP, as first described in Ref. 4, which is suitable for the bounded NCP. We extend the work in Ref. 4 by demonstrating a stronger convergence result and present numerical results on test problems.     

Nonlinear mappings associated with the generalized linear complementarity problem

We show that the Cottle—Dantzig generalized linear complementarity problem (GLCP) is equivalent to a nonlinear complementarity problem (NLCP), a piecewise linear system of equations (PLS), a multiple objective programming problem (MOP), and a variational inequalities problem (VIP). On the basis of these equivalences, we provide an algorithm for solving problem GLCP.Project partially supported by a grant from Oak Ridge Associated Universities, TN, USA.     

对称锥互补问题

对称锥互补问题是一类均衡优化,包括标准互补问题、二阶锥互补问题和半定互补问题等,近几年,人们借助欧几里德若当代数技术,在对称锥互补问题的研究方面获得了突破性进展并使之逐渐受到重视,本文主要从理论和算法两方面总结和评述这些新成果,同时,列出了相应的重要文献。