Graphical analysis of duality and the Kuhn-Tucker conditions in linear programming

Careful inspection of the geometry of the primal linear programming problem reveals the Kuhn-Tucker conditions as well as the dual. Many of the well-known special cases in duality are also seen from the geometry, as well as the complementary slackness conditions and shadow prices. The latter at demonstrated to differ from the dual variables in situations involving primal degeneracy. Virtually all the special relationships between linear programming and duality theory can be seen from the geometry of the primal and an elementary application of vector analysis.     

Regular exceptional family of elements with respect to isotone projection cones in Hilbert spaces and complementarity problems

Conditions for the non-existence of a regular exceptional family of elements with respect to an isotone projection cone in a Hilbert space will be presented. The obtained results will be used for generating existence theorems for a complementarity problem with respect to an isotone projection cone in a Hilbert space.     

Kuhn-Tucker sufficiency for global minimum of multi-extremal mathematical programming problems

The Kuhn-Tucker Sufficiency Theorem states that a feasible point that satisfies the Kuhn-Tucker conditions is a global minimizer for a convex programming problem for which a local minimizer is global. In this paper, we present new Kuhn-Tucker sufficiency conditions for possibly multi-extremal nonconvex mathematical programming problems which may have many local minimizers that are not global. We derive the sufficiency conditions by first constructing weighted sum of square underestimators of the objective function and then by characterizing the global optimality of the underestimators. As a consequence, we derive easily verifiable Kuhn-Tucker sufficient conditions for general quadratic programming problems with equality and inequality constraints. Numerical examples are given to illustrate the significance of our criteria for multi-extremal problems.     

The non-existence of a regular exceptional family of elements. A necessary and sufficient condition. Applications to complementarity theory

This paper is the second part of our recent work [Isac and Németh, J Optim Theory Appl (forthcoming)]. Our goal is now to present some new results related to the non-existence of a regular exceptional family of elements (REFE) for a mapping and to show how can they be applied to complementarity theory.     

Optimization of a linear fractional function on a hypersphere of an affine space

In this paper, we consider the following nonlinear programming problem:

On the solution and complexity of a generalized linear complementarity problem

We introduce some sufficient conditions under which a generalized linear complementarity problem (GLCP) can be solved as a pure linear complementarity problem. We also establish that the GLCP is in general a NP-Hard problem.Support of this work has been provided by the Instituto Nacional de Investigação Cientifica de Portugal (INIC) under contract 89/EXA/5.     

On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm

This paper is devoted to the eigenvalue complementarity problem (EiCP) with symmetric real matrices. This problem is equivalent to finding a stationary point of a differentiable optimization program involving the Rayleigh quotient on a simplex (Queiroz et al., Math. Comput. 73, 1849–1863, 2004). We discuss a logarithmic function and a quadratic programming formulation to find a complementarity eigenvalue by computing a stationary point of an appropriate merit function on a special convex set. A variant of the spectral projected gradient algorithm with a specially designed line search is introduced to solve the EiCP. Computational experience shows that the application of this algorithm to the logarithmic function formulation is a quite efficient way to find a solution to the symmetric EiCP.     

On the equivalence of nonlinear complementarity problems and least-element problems

Strictly pseudomonotoneZ-maps operating on Banach lattices are considered. Equivalence of complementarity problems and least-element problems is established under certain regularity and growth conditions. This extends a recent result by Riddell (1981) for strictly monotoneZ-maps to the pseudomonotone case. Some other problems equivalent to the above are discussed as well.This work was partially supported by the National Science Council under grant NSC 82-0208-M-110-023.Corresponding author.     

Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126–140. Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education, Science and Culture, Japan. Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028     

紧约束函数梯度向量线性无关约束规范下Kuhn-Tucker条件的一个简洁证明

在紧约束函数的梯度向量线性无关这一约束规范下,运用隐函数定理和直交投影的性质,给出约束最优化问题Kuhn-Tucker一阶必要条件的一个简洁证明.     

On the coerciveness of some merit functions for complementarity problems over symmetric cones

One of the popular solution methods for the complementarity problem over symmetric cones is to reformulate it as the global minimization of a certain merit function. An important question to be answered for this class of methods is under what conditions the level sets of the merit function are bounded (the coerciveness of the merit function). In this paper, we introduce the generalized weak-coerciveness of a continuous transformation. Under this condition, we prove the coerciveness of some merit functions, such as the natural residual function, the normal map, and the Fukushima-Yamashita function for complementarity problems over symmetric cones. We note that this is a much milder condition than strong monotonicity, used in the current literature.     

Second-order necessary conditions of the Kuhn-Tucker type under new constraint qualifications

We are concerned with a nonlinear programming problem with equality and inequality constraints. We shall give second-order necessary conditions of the Kuhn-Tucker type and prove that the conditions hold under new constraint qualifications. The constraint qualifications are weaker than those given by Ben-Tal (Ref. 1).The author would like to thank Professor N. Furukawa and the referees for their many valuable comments and helpful suggestions.     

Modified auxiliary boundary conditions method for an ill-posed problem for the homogeneous biharmonic equation

In this paper, we are interested in the inverse problem for the biharmonic equation posed on a rectangle, which is of great importance in many areas of industry and engineering. We show that the problem under consideration is ill-posed; therefore, to solve it, we opted for a regularization method via modified auxiliary boundary conditions. The numerical implementation is based on the application of the semidiscrete finite difference method for a sequence of well-posed direct problems depending on a small parameter of regularization. Numerical results are performed for a rectangle domain showing the effectiveness of the proposed method.     

On the number of solutions to a class of complementarity problems

In this paper we consider the problem of establishing the number of solutions to the complementarity problem. For the case when the Jacobian of the mapping has all principal minors negative, and satisfies a condition at infinity, we prove that the problem has either 0, 1, 2 or 3 solutions. We also show that when the Jacobian has all principal minors positive, and satisfies a condition at infinity, the problem has a unique solution.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS77-03472 and Grant No. MCS78-09525. This work appeared as an MRC Technical Report No. 1964, University of Wisconsin, Madison, WI, June 1979.     

On the number of solutions to a class of linear complementarity problems

In this note, we consider the linear complementarity problemw = Mz + q, w 0, z 0, w ^T z = 0, when all principal minors ofM are negative. We show that for such a problem for anyq, there are either 0, 1, 2, or 3 solutions. Also, a set of sufficiency conditions for uniqueness is stated.The work of both authors is partially supported by a grant from the National Science Foundation, MCS 77-03472.     

Growth behavior of a class of merit functions for the nonlinear complementarity problem

When the nonlinear complementarity problem is reformulated as that of finding the zero of a self-mapping, the norm of the selfmapping serves naturally as a merit function for the problem. We study the growth behavior of such a merit function. In particular, we show that, for the linear complementarity problem, whether the merit function is coercive is intimately related to whether the underlying matrix is aP-matrix or a nondegenerate matrix or anR _o-matrix. We also show that, for the more popular choices of the merit function, the merit function is bounded below by the norm of the natural residual raised to a positive integral power. Thus, if the norm of the natural residual has positive order of growth, then so does the merit function.This work was partially supported by the National Science Foundation Grant No. CCR-93-11621.The author thanks Dr. Christian Kanzow for his many helpful comments on a preliminary version of this paper. He also thanks the referees for their helpful suggestions.     

An unconstrained smooth minimization reformulation of the second-order cone complementarity problem

A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over ℝⁿ. A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over ℝⁿ and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiability, not continuous differentiability, was established. In this paper, we extend this merit function and its analysis, including continuous differentiability, to the second-order cone complementarity problem (SOCCP). Although SOCCP is reducible to a SDCP, the reduction does not allow for easy translation of the analysis from SDCP to SOCCP. Instead, our analysis exploits properties of the Jordan product and spectral factorization associated with the second-order cone. We also report preliminary numerical experience with solving DIMACS second-order cone programs using a limited-memory BFGS method to minimize the merit function. In honor of Terry Rockafellar on his 70th birthday     

A weak linearization of the Kuhn-tucker conditions for a class of allocation problems

The return obtained from the allocation of resources to an activity is occasionally modelled by means of concave, strictly increasing functions. Exponential functions of a certain class conveniently lend themselves to such modelling. A nonlinear programming formulation of a multiresource allocation problem with return functions of the class appears to have Kuhn-Tucker conditions which in a sense are intrinsically linear. The paper shows how this fact can be utilised to save processing time in the execution of numerical algorithms for the solution of this mathematical programming problem.     

Small-amplitude solutions of the sine-Gordon equation on an interval under dirichlet or Neumann boundary conditions

Summary We give a complete classification of the small-amplitude finite-gap solutions of the sine-Gordon (SG) equation on an interval under Dirichlet or Neumann boundary conditions. Our classification is based on an analysis of the finite-gap solutions of the boundary problems for the SG equation by means of the Schottky uniformization approach.On leave from IPPI, Moscow, Russia     

On estimation of the optimal parameter of the modulus-based matrix splitting algorithm for linear complementarity problems on second-order cones

There are many studies on the well-known modulus-based matrix splitting (MMS) algorithm for solving complementarity problems, but very few studies on its optimal parameter, which is of theoretical and practical importance. Therefore and here, by introducing a novel mapping to explicitly cast the implicit fixed point equation and thus obtain the iteration matrix involved, we first present the estimation approach of the optimal parameter of each step of the MMS algorithm for solving linear complementarity problems on the direct product of second-order cones (SOCLCPs). It also works on single second-order cone and the non-negative orthant. On this basis, we further propose an iteration-independent optimal parameter selection strategy for practical usage. Finally, the practicability and effectiveness of the new proposal are verified by comparing with the experimental optimal parameter and the diagonal part of system matrix. In addition, with the optimal parameter, the effectiveness of the MMS algorithm can indeed be greatly improved, even better than the state-of-the-art solvers SCS and SuperSCS that solve the equivalent SOC programming.