Exceptional family and solvability of copositive complementarity problems

In this paper, by extending the concept of exceptional family to complementarity problems over the cone of symmetric copositive real matrices, we propose an existence theorem of a solution to the copositive complementarity problem. Extensions of Isac–Carbone?s condition, Karamardian?s condition, weakly properness and coercivity are also introduced. Several applications of these results are presented, and we prove that without exceptional family is a sufficient and necessary condition for the solvability of pseudomonotone copositive complementarity problems.     

Functions Without Exceptional Family of Elements and Complementarity Problems

In Ref. 1, Isac, Bulavski, and Kalashnikov introduced the concept of exceptional family of elements for a continuous function f: R ⁿR ⁿ. It is known that, if there does not exist an exceptional family of elements for f, then the corresponding complementarity problem has a solution. In this paper, we show that several classes of nonlinear functions, known in complementarity theory or other domains, are functions without exceptional family of elements and consequently the corresponding complementarity problem is solvable. It is evident that the notion of exceptional family of elements provides an alternative way of determining whether or not the complementarity problem has a solution.     

A GLOBAL LINEAR AND LOCAL QUADRATIC SINGLE-STEP NONINTERIOR CONTINUATION METHOD FOR MONOTONE SEMIDEFINITE COMPLEMENTARITY PROBLEMS

A noninterior continuation method is proposed for semidefinite complementarity problem (SDCP). This method improves the noninterior continuation methods recently developed for SDCP by Chen and Tseng. The main properties of our method are: (i) it is well defined for the monotones SDCP; (ii) it has to solve just one linear system of equations at each step; (iii) it is shown to be both globally linearly convergent and locally quadratically convergent under suitable assumptions.     

具有间断非线性项的拟线性抛物型方程(英)

本文研究具有间断非线性项的拟线性抛物型方程，利用Clarke广义梯度和伪单调算子理论证明了解的存在性．     

POSITIVE SOLUTIONS TO(k,n-k) NONHOMOGENEOUS BOUNDARYVALUE PROBLEM

By the Schauder fixed point theory,this paper establishes the existence of positive solutions to a(k,n k) m-point boundary value problem.We show that there exists a positive constant b such that the problem has at least one positive solution when the homogeneous boundary parameter is smaller than b,and no positive solution when this parameter is greater than b.     

On KKT points of Celis-Dennis-Tapia subproblem

The Celis-Dennis-Tapia(CDT) problem is a subproblem of the trust region algorithms for the constrained optimization. CDT subproblem is studied in this paper. It is shown that there exists the KKT point such that the Hessian matrix of the Lagrangian is positive semidefinite, if the multipliers at the global solution are not unique. Next the second order optimality conditions are also given, when the Hessian matrix of Lagrange at the solution has one negative eigenvalue. And furthermore, it is proved that all feasible KKT points satisfying that the corresponding Hessian matrices of Lagrange have one negative eigenvalue are the local optimal solutions of the CDT subproblem.     

Characterizing degree-sum maximal nonhamiltonian bipartite graphs

In 1963, Moon and Moser gave a bipartite analogue to Ore’s famed theorem on hamiltonian graphs. While the sharpness examples of Ore’s Theorem have been independently characterized in at least four different papers, no similar characterization exists for the Moon–Moser Theorem. In this note, we give such a characterization, consisting of one infinite family and two exceptional graphs of order eight.     

Inexact non-interior continuation method for solving large-scale monotone SDCP

For exact Newton method for solving monotone semidefinite complementarity problems (SDCP), one needs to exactly solve a linear system of equations at each iteration. For problems of large size, solving the linear system of equations exactly can be very expensive. In this paper, we propose a new inexact smoothing/continuation algorithm for solution of large-scale monotone SDCP. At each iteration the corresponding linear system of equations is solved only approximately. Under mild assumptions, the algorithm is shown to be both globally and superlinearly convergent.     

对称锥互补问题

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

A new infinite family of minimally nonideal matrices

Minimally nonideal matrices are a key to understanding when the set covering problem can be solved using linear programming. The complete classification of minimally nonideal matrices is an open problem. One of the most important results on these matrices comes from a theorem of Lehman, which gives a property of the core of a minimally nonideal matrix. Cornuéjols and Novick gave a conjecture on the possible cores of minimally nonideal matrices. This paper disproves their conjecture by constructing a new infinite family of square minimally nonideal matrices. In particular, we show that there exists a minimally nonideal matrix with r ones in each row and column for any r?3.     

Exceptional family of elements for generalized variational inequalities

This paper introduces a new concept of exceptional family of elements for a finite-dimensional generalized variational inequality problem. Based on the topological degree theory of set-valued mappings, an alternative theorem is obtained which says that the generalized variational inequality has either a solution or an exceptional family of elements. As an application, we present a sufficient condition to ensure the existence of a solution to the variational inequality. The set-valued mapping is assumed to be upper semicontinuous with nonempty compact convex values.     

A modified method for constructing efficient solutions structure of MOLP

This paper deals with a recently proposed algorithm for obtaining all weak efficient and efficient solutions in a multi objective linear programming (MOLP) problem. The algorithm is based on solving some weighted sum problems, and presents an easy and clear solution structure. We first present an example to show that the algorithm may fail when at least one of these weighted sum problems has not a finite optimal solution. Then, the algorithm is modified to overcome this problem. The modified algorithm determines whether an efficient solution exists for a given MOLP and generates the solution set correctly (if exists) without any change in the complexity.     

拟变分不等式解集的极小本质集及应用

引入了拟变分不等式解集的极小本质集的概念，并证明了每个拟变分不等式(满足一定条件)的解集至少存在一个极小本质集．作为应用，还证明了大多数(在Baire分类意义下)拟-似变分不等式问题的解集是稳定的；每个拟-似变分不等式(满足一定条件)的解集至少存在一个本质连通区．     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Nonuniqueness of solutions for a singular diffusion problem

In this paper, we consider a singular diffusion problem and show, by constructing a counterexample, that the weak solution to the problem is not unique. The proof consists of several steps. First, we prove that there exists a maximal weak solution to the problem. We show that the support of the continuous maximal weak solution cannot decrease in time. Then we cite an example of a nonnegative continuous function with shrinking support that also solves the problem, and therefore the problem possesses at least two weak solutions for some continuous nonnegative initial data.     

Semidefinite complementarity reformulation for robust Nash equilibrium problems with Euclidean uncertainty sets

Consider the N-person non-cooperative game in which each player’s cost function and the opponents’ strategies are uncertain. For such an incomplete information game, the new solution concept called a robust Nash equilibrium has attracted much attention over the past several years. The robust Nash equilibrium results from each player’s decision-making based on the robust optimization policy. In this paper, we focus on the robust Nash equilibrium problem in which each player’s cost function is quadratic, and the uncertainty sets for the opponents’ strategies and the cost matrices are represented by means of Euclidean and Frobenius norms, respectively. Then, we show that the robust Nash equilibrium problem can be reformulated as a semidefinite complementarity problem (SDCP), by utilizing the semidefinite programming (SDP) reformulation technique in robust optimization. We also give some numerical example to illustrate the behavior of robust Nash equilibria.     

Exceptional family of elements for general order complementarity problems

The notion of exceptional family of elements for general order complementarity problems in Banach spaces will be introduced. It will be shown that for general order complementarity problems defined by completely continuous fields the problem has either a solution or an exceptional family of elements. Finite dimensional examples and an application to integral operators will be given.     

Two Classes of Merit Functions for Infinite-Dimensional Second Order Complimentary Problems

In this article, we extend two classes of merit functions for the second-order complementarity problem (SOCP) to infinite-dimensional SOCP. These two classes of merit functions include several popular merit functions, which are used in nonlinear complementarity problem, (NCP)/(SDCP) semidefinite complementarity problem, and SOCP, as special cases. We give conditions under which the infinite-dimensional SOCP has a unique solution and show that all these merit functions provide an error bound for infinite-dimensional SOCP and have bounded level sets. These results are very useful for designing solution methods for infinite-dimensional SOCP.     

Solvability of Generalized Variational Inequality Problems for Unbounded Sets in Reflexive Banach Spaces

By employing the notion of exceptional family of elements, we establish some existence results for generalized variational inequality problems in reflexive Banach spaces provided that the mapping is upper sign-continuous. We show that the nonexistence of an exceptional family of elements is a necessary condition for the solvability of the dual variational inequality. For quasimonotone variational inequalities, we present some sufficient conditions for the existence of strong solutions. For the pseudomonotone case, the nonexistence of an exceptional family of elements is proved to be an equivalent characterization of the problem having strong solutions. Furthermore, we establish several equivalent conditions for the solvability for the pseudomonotone case. As a byproduct, a quasimonotone generalized variational inequality is proved to have a strong solution if it is strictly feasible. Moreover, for the pseudomonotone case, the strong solution set is nonempty and bounded if it is strictly feasible.     

POSITIVE SOLUTIONS TO SECOND-ORDER SINGULAR NEUMANN BOUNDARY VALUE PROBLEM WITH PARAMETERS IN THE BOUNDARY CONDITIONS

In this paper, we consider a class of nonlinear second-order singular Neumann boundary value problem with parameters in the boundary conditions. By the fixed point index, spectral theory of the linear operators, and lower and upper solutions method, we prove that there exists a constant λ* > 0 such that for λ∈ (0, λ * ), NBVP has at least two positive solutions; for λ = λ* , NBVP has at least one positive solution; for λ > λ* , NBVP has no solution.