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.     

A note on linear complementarity problems and multiple objective programming

Kostreva and Wiecek [3] introduced a problem called LCP-related weighted problem in connection with a multiple objective programming problem, and suggested that a given linear complementarity problem (LCP) can be solved by solving the LCP-related weighted problem associated with it. In this note we provide several clarifications of the claims made in [3]. Finally, we feel that solving any LCP by the approach given in [3] may not be as useful as it is claimed.Mathematics Subject Classification (2000): 90C33Received: October 1998 / Revised version: August 2003     

A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

Robust aspects of solutions in deterministic multiple objective linear programming

We study questions of robustness of linear multiple objective problems in the sense of post-optimal analysis, that is, we study conditions under which a given efficient solution remains efficient when the criteria/objective matrix undergoes some alterations. We consider addition or removal of certain criteria, convex combination with another criteria matrix, or small perturbations of its entries. We provide a necessary and sufficient condition for robustness in a verifiable form and give two formulae to compute the radius of robustness.     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

Multiple-objective approximation of feasible but unsolvable linear complementarity problems

Using a multiple-objective framework, feasible linear complementarity problems (LCPs) are handled in a unified manner. The resulting procedure either solves the feasible LCP or, under certain conditions, produces an approximate solution which is an efficient point of the associated multiple-objective problem. A mathematical existence theory is developed which allows both specialization and extension of earlier results in multiple-obkective programming. Two perturbation approaches to finding the closest solvable LCPs to a given unsolvable LCP are proposed. Several illustrative examples are provided and discussed.     

多目标数学规划有效集的参数表示

研究了p-维多目标数学规划问题有效集的参数表示. 通过研究相关的单目标优化问题和相关的(p-1)-维多目标优化问题, 提出了几个新的关于p-维多目标规划有效集的表示定理.     

PROMISE: A DSS for multiple objective stochastic linear programming problems

Most of the multiple objective linear programming (MOLP) methods which have been proposed in the last fifteen years suppose deterministic contexts, but because many real problems imply uncertainty, some methods have been recently developed to deal with MOLP problems in stochastic contexts. In order to help the decision maker (DM) who is placed before such stochastic MOLP problems, we have built a Decision Support System called PROMISE. On the one hand, our DSS enables the DM to identify many current stochastic contexts: risky situations and also situations of partial uncertainty. On the other hand, according to the nature of the uncertainty, our DSS enables the DM to choose the most appropriate interactive stochastic MOLP method among the available methods, if such a method exists, and to solve his problem via the chosen method.     

Selecting tolerances in chance-constrained programming: A multiple objective linear programming approach

An importance issue concerning the practical application of chance-constrained programming is the lack of a rational method for choosing risk levels or tolerances on the chance constraints. While there has also been much recent debate on the relationship, equivalence, usefulness, and other characteristics of chance-constrained programming relative to stochastic programming with recourse, this paper focuses on the problem of improving the selection of tolerances within the chance-constrained framework. An approach is presented, based on multiple objective linear programming, which allows the decision maker to be more involved in the tolerance selection process, but does not demand a priori decisions on appropriate tolerances. An example is presented which illustrates the approach.     

Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems

We consider semidefinite monotone linear complementarity problems (SDLCP) in the space ⁿ of real symmetric n×n-matrices equipped with the cone ⁿ₊ of all symmetric positive semidefinite matrices. One may define weighted (using any Mⁿ₊₊ as weight) infeasible interior point paths by replacing the standard condition XY=rI, r>0, (that defines the usual central path) by (XY+YX)/2=rM. Under some mild assumptions (the most stringent is the existence of some strictly complementary solution of (SDLCP)), these paths have a limit as r0, and they depend analytically on all path parameters (such as r and M), even at the limit point r=0.Mathematics Subject Classification (1991): 90C33, 65K05     

Proper efficiency in vector infinite programming problems

Using the notion of invexity, we give sufficient conditions of optimality for properly efficient solutions of a vector infinite programming problem and show that the set of properly efficient solutions coincides with the set of optimal solutions of a related scalar problem.     

Inexact algorithm for continuous complementarity problems on measure spaces

In this paper, we discuss a type of complementarity problem posed over a measure space. We give some conditions under which there exists a solution for the problem and work toward a new inexact algorithm for its solution. A general convergence proof for this algorithm is given and the advantage of using this approach is discussed.The authors thank the referees for their helpful suggestions and comments.     

Tolerance approach to sensitivity analysis in linear complementarity problems

In this paper, we apply the tolerance approach proposed by Wendell for sensitivity analysis in linear programs to study sensitivity analysis in linear complementarity problems. In the tolerance approach, we find the range or the maximum tolerance within which the coefficients of the right-hand side of the problem can vary simultaneously and independently such that the solution of the original and the perturbed problems have the same index set of nonzero elements.The work of the first author was completed while he was at Virginia Commonwealth University, Richmond, Virginia.     

Reformulation of mathematical programming problems as linear complementarity problems and investigation of their solution methods

A family of complementarity problems is defined as extensions of the well-known linear complementarity problem (LCP). These are:

Solution behavior for parametric implicit complementarity problems

In this paper we study the solution behavior for a special class of quasi-variational inequalities, namely implicit complementarity problems. We derive conditions under which the perturbed solution of a parametric implicit complementarity problem is locally unique, continuous and Fréchet differentiable.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

一种双层规划的光滑化目标罚函数算法

论文研究了一种双层规划的光滑化目标罚函数算法,在一些条件下,证明了光滑化罚优化问题等价于原双层规划问题,而且,当下层规划问题是凸规划问题时, 给出了一个求解算法和收敛性证明.     

Convolution complementarity problems with application to impact problems

^** Email: dstewart{at}math.uiowa.edu. Part of this work was carried out while visiting CMAF at the University of Lisbon and while visiting the University of Lyons 1. Convolution complementarity problems (CCPs) have the followingform: given a matrix-valued function k and a vector-valued functionq, find a vector-valued function u satisfying 0 u(t) (k*u)(t)+ q(t) 0 for all t. In this paper CCPs are applied to a mechanicalimpact problem, but they can also be applied to other dynamicproblems with hard constraints. CCPs are shown to have solutionsprovided q(0) 0 and q is sufficiently regular, k has locallybounded variation and k(0⁺) is a P-matrix. Uniqueness also holdsprovided, in addition, k(0⁺) is symmetric positive definite.This theory shows that the impact problem studied here has aunique solution, and that energy is conserved. Numerical methodshave been devised and implemented for the impact problem, andthe results are presented.