A new interior-point algorithm based on modified Nesterov–Todd direction for symmetric cone linear complementarity problem

We present a new primal-dual path-following interior-point algorithm for linear complementarity problem over symmetric cones. The algorithm is based on a reformulation of the central path for finding the search directions. For a full Nesterov–Todd step feasible interior-point algorithm based on the search directions, the complexity bound of the algorithm with the small update approach is the best available.     

A projected–gradient interior–point algorithm for complementarity problems

Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.     

An arc-search predictor-corrector infeasible-interior-point algorithm for P∗(κ)-SCLCPs

Numerical Algorithms - In this paper, we propose a new arc-search predictor-corrector infeasible-interior-point algorithm for linear complementarity problems over symmetric cones with the Cartesian...     

A Barzilai–Borwein type method for stochastic linear complementarity problems

We consider the expected residual minimization (ERM) formulation of stochastic linear complementarity problem (SLCP). By employing the Barzilai–Borwein (BB) stepsize and active set strategy, we present a BB type method for solving the ERM problem. The global convergence of the proposed method is proved under mild conditions. Preliminary numerical results show that the method is promising.     

A predictor-corrector interior-point algorithm for P ∗ ( κ ) -horizontal linear complementarity problem

We present a predictor-corrector path-following interior-point algorithm for \(P_*(\kappa )\) horizontal linear complementarity problem based on new search directions. In each iteration, the algorithm performs two kinds of steps: a predictor (damped Newton) step and a corrector (full Newton) step. The full Newton-step is generated from an algebraic reformulation of the centering equation, which defines the central path and seeks directions in a small neighborhood of the central path. While the damped Newton step is used to move in the direction of optimal solution and reduce the duality gap. We derive the complexity for the algorithm, which coincides with the best known iteration bound for \(P_*(\kappa )\) -horizontal linear complementarity problems.     

A quadratically convergentO((\kappa + 1)\sqrt n L)-iteration algorithm for theP *(κ)-matrix linear complementarity problem

An interior-point predictor-corrector algorithm for theP _*()-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno—Todd—Ye's predictor—corrector algorithm for linear programming problem. The extended algorithm is quadratically convergent with iteration complexity . It is the first polynomially and quadratically convergent algorithm for a class of LCPs that are not necessarily monotone.     

A non–interior predictor–corrector path following algorithm for the monotone linear complementarity problem

We present a predictor–corrector non–interior path following algorithm for the monotone linear complementarity problem based on Chen–Harker–Kanzow–Smale smoothing techniques. Although the method is modeled on the interior point predictor–corrector strategies, it is the first instance of a non–interior point predictor–corrector algorithm. The algorithm is shown to be both globally linearly convergent and locally quadratically convergent under standard hypotheses. The approach to global linear convergence follows the authors’ previous work on this problem for the case of (P ₀+R ₀) LCPs. However, in this paper we use monotonicity to refine our notion of neighborhood of the central path. The refined neighborhood allows us to establish the uniform boundedness of certain slices of the neighborhood of the central path under the standard hypothesis that a strictly positive feasible point exists. Received September 1997 / Revised version received May 1999?Published online December 15, 1999     

A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones

This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal POPs. A numerical example is also given to exhibit its high potential. Research of M. Kojima supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234. Research of M. Muramatsu supported in part by Grant-in-Aid for Young Scientists (B) 15740054.     

A linear time algorithm for the Koopmans–Beckmann QAP linearization and related problems

An instance of the quadratic assignment problem (QAP) with cost matrix $Q$ is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix $C$ such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in $O\left(n^4\right)$ time. However, for the special cases of Koopmans–Beckmann QAP and the multiplicative assignment problem the input size is of $\Omega \left(n^2\right)$. We show that the QAP linearization problem for these special cases can be solved in $O\left(n^2\right)$ time. For symmetric Koopmans–Beckmann QAP, Bookhold [I. Bookhold, A contribution to quadratic assignment problems, Optimization 21 (1990) 933–943.] gave a sufficient condition for linearizability and raised the question if the condition is necessary. We show that Bookhold’s condition is also necessary for linearizability of symmetric Koopmans–Beckmann QAP.     

New proximity and complexity result for P*(κ)-linear complementarity problem (Poster Presentation)

One of the main ingredients of interior point methods is the proximity functions to measure the distance of the iterates from the central path of linear optimization problems. In this paper, an interior point method for solving P_*(κ)-linear complementarity problem, κ ≥ 0, is proposed. For this version, we use a new class of proximity functions induced by new kernel functions. Using some mild and easy to check conditions, we show that the large-update primal-dual interior point methods for solving P_*(κ)-linear complementarity problem enjoy the so far best worst case theoretical complexity, namely O (κ √n log n log n /ε) iteration bound, with special choices of the parameters p, q ≥ 1. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Infeasible Mehrotra-Type Predictor-Corrector Interior-Point Algorithm for the Cartesian P *(κ)-LCP Over Symmetric Cones

We propose an infeasible Mehrotra-type predictor-corrector algorithm with a new center parameter updating scheme for Cartesian P _*(κ)-linear complementarity problem over symmetric cones. Based on the Nesterov-Todd direction, we show that the iteration-complexity bound of the proposed algorithm is 𝒪((1 + κ)³ r ²log ε^?1), where r is the rank of the associated Euclidean Jordan algebras and κ is the handicap of the problem and ε > 0 is the required precision. Some numerical results are reported as well.     

A Mehrotra-Type Predictor-Corrector Algorithm for P*(κ) Linear Complementarity Problems

Mehrotra-type predictor-corrector algorithm,as one of most efficient interior point methods,has become the backbones of most optimization packages.Salahi et al.proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice.We extend their algorithm to P_*（κ）linear complementarity problems.The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ο(（1+4κ）（17+19κ） √（1+2κn）^3/2log[（x⁰）^Ts⁰/ε] worst case iteration complexity bound.An numerical experiment verifies the feasibility of the new algorithm.     

A nonmonotone derivative-free algorithm for nonlinear complementarity problems based on the new generalized penalized Fischer–Burmeister merit function

In this paper, we propose a new generalized penalized Fischer–Burmeister merit function, and show that the function possesses a system of favorite properties. Moreover, for the merit function, we establish the boundedness of level set under a weaker condition. We also propose a derivative-free algorithm for nonlinear complementarity problems with a nonmonotone line search. More specifically, we show that the proposed algorithm is globally convergent and has a locally linear convergence rate. Numerical comparisons are also made with the merit function used by Chen (J Comput Appl Math 232:455–471, 2009), which confirm the superior behaviour of the new merit function.