A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

Two characterization theorems in complementarity theory

In this paper, we establish two characterization theorems for the linear and non-linear complementarity problems. Theorem 1 concerns the local uniqueness of a solution to a linear complementarity problem. Theorem 2 provides a necessary and sufficient condition for the differentiability of a solution to a parametric non-linear complementarity problem.     

Solution Sets of Quadratic Complementarity Problems

In this paper, we study quadratic complementarity problems, which form a subclass of nonlinear complementarity problems with the nonlinear functions being quadratic polynomial mappings. Quadratic complementarity problems serve as an important bridge linking linear complementarity problems and nonlinear complementarity problems. Various properties on the solution set for a quadratic complementarity problem, including existence, compactness and uniqueness, are studied. Several results are established from assumptions given in terms of the comprising matrices of the underlying tensor, henceforth easily checkable. Examples are given to demonstrate that the results improve or generalize the corresponding quadratic complementarity problem counterparts of the well-known nonlinear complementarity problem theory and broaden the boundary knowledge of nonlinear complementarity problems as well.     

Linear complementarity problems and multiple objective programming

An equivalence is demonstrated between solving a linear complementarity problem with general data and finding a certain subset of the efficient points of a multiple objective programming problem. A new multiple objective programming based approach to solving linear complementarity problems is presented. Results on existence, uniqueness and computational complexity are included.     

On sensitivity of central solutions in semidefinite programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open. Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001     

Asymptotic optimality conditions for linear semi-infinite programming

In this paper, the classical KKT, complementarity and Lagrangian saddle-point conditions are generalized to obtain equivalent conditions characterizing the optimality of a feasible solution to a general linear semi-infinite programming problem without constraint qualifications. The method of this paper differs from the usual convex analysis methods and its main idea is rooted in some fundamental properties of linear programming.     

Quadratic programming problems and related linear complementarity problems

This paper investigates the general quadratic programming problem, i.e., the problem of finding the minimum of a quadratic function subject to linear constraints. In the case where, over the set of feasible points, the objective function is bounded from below, this problem can be solved by the minimization of a linear function, subject to the solution set of a linear complementarity problem, representing the Kuhn-Tucker conditions of the quadratic problem.To detect in the quadratic problem the unboundedness from below of the objective function, necessary and sufficient conditions are derived. It is shown that, when these conditions are applied, the general quadratic programming problem becomes equivalent to the investigation of an appropriately formulated linear complementarity problem.This research was supported by the Hungarian Research Foundation, Grant No. OTKA/1044.     

Characterizations for solidness of dual cones with applications

In this paper, some characterizations for the solidness of dual cones are established. As applications, we prove that a Banach space is reflexive if it contains a solid pointed closed convex cone having a weakly compact base, and prove an analogue of a Karamardian’s result for the linear complementarity problem in reflexive Banach spaces. The uniqueness of the solution of the linear complementarity problem is also discussed.     

On alternative optimal solutions to quasimonotonic programming with linear constraints

In this paper, the nonlinear programming problem with quasimonotonic （ both quasiconvex and quasiconcave ）objective function and linear constraints is considered. With the decomposition theorem of polyhedral sets, the structure of optimal solution set for the programming problem is depicted. Based on a simplified version of the convex simplex method, the uniqueness condition of optimal solution and the computational procedures to determine all optimal solutions are given, if the uniqueness condition is not satisfied. An illustrative example is also presented.     

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.     

Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

Preparation of Papers

In this paper, we study the local uniqueness of the solutions to the extended linear complementarity problem (XLCP, Ref. 1) by means of a concept which is an extension of the nondegenerate matrix in the standard LCP. Then, we give some special characterizations for the local uniqueness of the solutions to the horizontal linear complementarity problem (HLCP).     

一类线性约束变分不等式问题的幂罚函数法

本文研究了一类线性约束变分不等式(Ⅵ)的幂罚函数法求解问题.利用Ⅵ的KKT条件,将Ⅵ转化为等价的混合互补问题和一个新的Ⅵ问题,并在一定条件下分析了解的存在性和唯一性.利用度理论证明了幂罚方程组解的存在性与唯一性.由以上结果最终证明了幂罚函数法的收敛性,即幂罚方程组的解收敛于Ⅵ问题的解.     

On the convergence of a basic iterative method for the implicit complementarity problem

In Part 1 of this study (Ref. 1), we have defined the implicit complementarity problem and investigated its existence and uniqueness of solution. In the present paper, we establish a convergence theory for a certain iterative algorithm to solve the implicit complementarity problem. We also demonstrate how the algorithm includes as special cases many existing iterative methods for solving a linear complementarity problem.This research was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-75-C-0621-NR-047-048 with the Office of Naval Research.     

The solution set structure of monotone linear complementarity problems over second-order cone

The second-order cone linear complementarity problem (SOCLCP) is a generalization of the linear complementarity problem (LCP). In this paper we characterize the solution set of a monotone SOCLCP with the help of the Jordan-algebraic technique.     

Existence and Uniqueness of Solutions for Homogeneous Cone Complementarity Problems

We consider existence and uniqueness properties of a solution to homogeneous cone complementarity problem. Employing an algebraic characterization of homogeneous cones due to Vinberg from the 1960s, we generalize the properties of existence and uniqueness of solutions for a nonlinear function associated with the standard nonlinear complementarity problem to the setting of homogeneous cone complementarity problem. We provide sufficient conditions for a continuous function so that the associated homogeneous cone complementarity problems have solutions. In particular, we give sufficient conditions for a monotone continuous function so that the associated homogeneous cone complementarity problem has a unique solution (if any). Moreover, we establish a global error bound for the homogeneous cone complementarity problem under some conditions.     

Generalized principal pivot transforms, complementarity theory and their applications in stochastic games

In this article, we revisit the concept of principal pivot transform and its generalization in the context of vertical linear complementarity problem. We study solution set and solution rays of a vertical linear complementarity problem. Finally we present an application of generalized principal pivot transform in game theory.     

Minimum-support solutions of polyhedral concave programs *

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if

such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the

complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

Conditions for the uniqueness of the optimal solution in linear semi-infinite programming

In this paper, we establish different conditions for the uniqueness of the optimal solution of a semi-infinite programming problem. The approach here is based on the differentiability properties of the optimal value function and yields the corresponding extensions to the general linear semi-infinite case of many results provided by Mangasarian and others. In addition, detailed optimality conditions for the most general problem are supplied, and some features of the optimal set mapping are discussed. Finally, we obtain a dimensional characterization of the optimal set, provided that a usual closedness condition (Farkas-Minkowski condition) holds.