A feasible descent SQP algorithm for general constrained optimization without strict complementarity

In this paper, a class of optimization problems with equality and inequality constraints is discussed. Firstly, the original problem is transformed to an associated simpler problem with only inequality constraints and a parameter. The later problem is shown to be equivalent to the original problem if the parameter is large enough (but finite), then a feasible descent SQP algorithm for the simplified problem is presented. At each iteration of the proposed algorithm, a master direction is obtained by solving a quadratic program (which always has a feasible solution). With two corrections on the master direction by two simple explicit formulas, the algorithm generates a feasible descent direction for the simplified problem and a height-order correction direction which can avoid the Maratos effect without the strict complementarity, then performs a curve search to obtain the next iteration point. Thanks to the new height-order correction technique, under mild conditions without the strict complementarity, the globally and superlinearly convergent properties are obtained. Finally, an efficient implementation of the numerical experiments is reported.     

Strictly feasible equation-based methods for mixed complementarity problems

Summary.   We introduce a new algorithm for the solution of the mixed complementarity problem (MCP) which has stronger properties than most existing methods. In fact, typical solution methods for the MCP either generate feasible iterates but have to solve relatively complicated subproblems (like quadratic programs or linear complementarity problems), or they have relatively simple subproblems (like linear systems of equations) but generate not necessarily feasible iterates. The method to be presented here combines the nice features of these two classes of methods: It has to solve only one linear system of equations (of reduced dimension) at each iteration, and it generates feasible (more precisely: strictly feasible) iterates. The new method has some nice global and local convergence properties. Some preliminary numerical results will also be given. Received August 26, 1999 / Revised version recived April 11, 2000 / Published online February 5, 2001     

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     

Fuzzy approaches for multiple objective linear fractional optimization

The problem of finding a solution to a multiple objective linear fractional program arises in several real world situations.In this paper we advocate that fuzzy sets theory provides a basis for solving this problem with sufficient consistency and rigorousness.After representing imprecise aspirations of the decision maker by structured linguistic variables or converting the original problem via approximations or change of variables into a multiple objective linear program, techniques of fuzzy linear programming may be used to reach a satisfactory solution.It is shown that under reasonable restrictions, this solution is efficient (Pareto optimal) for the original problem. Numerical examples are also included for illustration.     

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.     

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.     

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.     

Finding a strict feasible solution of a linear semidefinite program

This study deals with the performance of projective interior point methods for linear semidefinite program. We propose a modification in the initialization phases of the method in order to reduce the computation time.This purpose is confirmed by numerical experiments showing the efficiency which are presented in the last section of the paper.     

Isotone solutions of parametric linear complementarity problems

The parametric linear complementarity problem is given by the conditions:q + p + Mz 0, 0,z 0,z ^T (q + p + Mz) = 0. Under the assumption thatM is a P-matrix, Cottle proved that the solution mapz() of the above problem is montonically nondecreasing in the parameter for every nonnegativeq and everyp if and only ifM is a Minkowski matrix. This paper examines whether a similar result holds in various other settings including a nonlinear case.     

Robust solutions to uncertain linear complementarity problems

In this paper,we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain,and it is only known to belong to a prescribed uncertainty set.We propose the notion of the p- robust counterpart and the p-robust solution of uncertain linear complementarity problems.We discuss uncertain linear complementarity problems with three different uncertainty sets,respectively,including an unknown-but-bounded uncertainty set,an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set,and present some sufficient and necessary(or sufficient) conditions which p- robust solutions satisfy.Some special cases are investigated in this paper.     

Efficiency in multiple objective optimization problems

We generalize many of the results on efficient points for linear multiple objective optimization problems to the nonlinear case by focusing on an auxiliary problem. The approach, which relies on duality theory, is a straightforward development that even in the linear case yields simpler proofs.This research was partially supported by the National Science Foundation through Grant No. ENG 74-15488.     

On proto-differentiability and strict proto-differentiability of multifunctions of feasible points in perturbed optimization problems

This paper is concerned with the study of the proto-differentiability of the multifunction associated with the feasible points of optimization problems. It is proved under some natural conditions that the proto-differentiability of the data multifunctions ensure that of the resulting multifunctions of feasible points.     

Analysis of the objective space in multiple objective linear programming

A multiple objective linear program is defined by a matrix C consisting of the coefficients of the linear objectives and a convex polytope X defined by the linear constraints. An analysis of the objective space Y = C[X] for this problem is presented. A characterization between a face of Y and the corresponding faces of X is obtained. This result gives a necessary and sufficient condition for a face to be efficient. The theory and examples demonstrate the collapsing (simplification) that occurs in mapping X to Y. These results form a basis for a new approach to analyzing multiple objective linear programs.     

Q-matrices and boundedness of solutions to linear complementarity problems

This paper is concerned with the existence and boundedness of the solutions to the linear complementarity problemw=Mz+q,w0,z0,w ^T z=0, for eachq ⁿ . It has been previously established that, ifM is copositive plus, then the solution set is nonempty and bounded for eachq ⁿ iffM is aQ-matrix. This result is shown to be valid also forL ₂-matrices,P ₀-matrices, nonnegative matrices, andZ-matrices.     

On duality in multiple objective linear programming

In this paper we present two approaches to duality in multiple objective linear programming. The first approach is based on a duality relation between maximal elements of a set and minimal elements of its complement. It offers a general duality scheme which unifies a number of known dual constructions and improves several existing duality relations. The second approach utilizes polarity between a convex polyhedral set and the epigraph of its support function. It leads to a parametric dual problem and yields strong duality relations, including those of geometric duality.     

Numerical validation of solutions of linear complementarity problems

Summary. This paper proposes a validation method for solutions of linear complementarity problems. The validation procedure consists of two sufficient conditions that can be tested on a digital computer. If the first condition is satisfied then a given multidimensional interval centered at an approximate solution of the problem is guaranteed to contain an exact solution. If the second condition is satisfied then the multidimensional interval is guaranteed to contain no exact solution. This study is based on the mean value theorem for absolutely continuous functions and the reformulation of linear complementarity problems as nonsmooth nonlinear systems of equations. Received August 21, 1997 / Revised version July 2, 1998     

Monotone solutions of the parametric linear complementarity problem

The parametric linear complementarity problem under study here is given by the conditionsq + αp + Mz ≥ 0,α ≥ 0,z ≥ 0,z ^T (q + αp + Mz) = 0 whereq is nonnegative. This paper answers three questions including the following one raised by G. Maier: What are the necessary and sufficient conditions onM guaranteeing that for every nonnegative starting pointq and every directionp the components of the solution to the parametric linear complementarity problem are nondecreasing functions of the parameterα?