Some non-interior path-following methods based on a scaled central path for linear complementarity problems

In this paper we present some non-interior path-following methods for linear complementarity problems. Instead of using the standard central path we use a scaled central path. Based on this new central path, we first give a feasible non-interior path-following method for linear complementarity problems. And then we extend it to an infeasible method. After proving the boundedness of the neighborhood, we prove the convergence of our method. Another point we should present is that we prove the local quadratic convergence of feasible method without the assumption of strict complementarity at the solution.     

A non-interior continuation method for generalized linear complementarity problems

In this paper, we propose a non-interior continuation method for solving generalized linear complementarity problems (GLCP) introduced by Cottle and Dantzig. The method is based on a smoothing function derived from the exponential penalty function first introduced by Kort and Bertsekas for constrained minimization. This smoothing function can also be viewed as a natural extension of Chen-Mangasarian’s neural network smooth function. By using the smoothing function, we approximate GLCP as a family of parameterized smooth equations. An algorithm is presented to follow the smoothing path. Under suitable assumptions, it is shown that the algorithm is globally convergent and local Q-quadratically convergent. Few preliminary numerical results are also reported. Received September 3, 1997 / Revised version received April 27, 1999?Published online July 19, 1999     

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second-order cone programming (SOCP) based on a family of directions that is a natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O( logε^-1) iteration-complexity to reduce the duality gap by a factor of ε, where n is the number of second-order cones. Since the MZ-type family studied in this paper includes an analogue of the Alizadeh, Haeberly and Overton pure Newton direction, we establish for the first time the polynomial convergence of primal-dual algorithms for SOCP based on this search direction. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000     

Componentwise fast convergence in the solution of full-rank systems of nonlinear equations

The asymptotic convergence of parameterized variants of Newton’s method for the solution of nonlinear systems of equations is considered. The original system is perturbed by a term involving the variables and a scalar parameter which is driven to zero as the iteration proceeds. The exact local solutions to the perturbed systems then form a differentiable path leading to a solution of the original system, the scalar parameter determining the progress along the path. A path-following algorithm, which involves an inner iteration in which the perturbed systems are approximately solved, is outlined. It is shown that asymptotically, a single linear system is solved per update of the scalar parameter. It turns out that a componentwise Q-superlinear rate may be attained, both in the direct error and in the residuals, under standard assumptions, and that this rate may be made arbitrarily close to quadratic. Numerical experiments illustrate the results and we discuss the relationships that this method shares with interior methods in constrained optimization. Received: September 8, 2000 / Accepted: September 17, 2001?Published online February 14, 2002     

Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems

We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ ²ⁿ satisfying y=f(x) and x _i y _i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ ⁿ to ℝ ⁿ . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ ³ⁿ which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ ²ⁿ in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it. Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999     

Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems

ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρ_f is a feasibility measure. We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility (primal or dual) can be detected in O(ln) iterations, where ρ_· is a primal or dual infeasibility measure. Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998     

互补问题的一个修改算法

本文给出了一个修改的路径跟踪预测校正非内点算法 ,同时给出了一个新的中心路邻域的表示 .并在此基础上给出了全局和局部收敛性 ,最后给出的数值结果验证了其有效性     

Self-regular functions and new search directions for linear and semidefinite optimization

In this paper, we introduce the notion of a self-regular function. Such a function is strongly convex and smooth coercive on its domain, the positive real axis. We show that any such function induces a so-called self-regular proximity function and a corresponding search direction for primal-dual path-following interior-point methods (IPMs) for solving linear optimization (LO) problems. It is proved that the new large-update IPMs enjoy a polynomial ?(n log) iteration bound, where q≥1 is the so-called barrier degree of the kernel function underlying the algorithm. The constant hidden in the ?-symbol depends on q and the growth degree p≥1 of the kernel function. When choosing the kernel function appropriately the new large-update IPMs have a polynomial ?(lognlog) iteration bound, thus improving the currently best known bound for large-update methods by almost a factor . Our unified analysis provides also the ?(log) best known iteration bound of small-update IPMs. At each iteration, we need to solve only one linear system. An extension of the above results to semidefinite optimization (SDO) is also presented. Received: March 2000 / Accepted: December 2001?Published online April 12, 2002     

An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming

We prove the superlinear convergence of the primal-dual infeasible interior-point path-following algorithm proposed recently by Kojima, Shida, and Shindoh and by the present authors, under two conditions: (i) the semidefinite programming problem has a strictly complementary solution; (ii) the size of the central path neighborhood approaches zero. The nondegeneracy condition suggested by Kojima, Shida, and Shindoh is not used in our analysis. Our result implies that the modified algorithm of Kojima, Shida, and Shindoh, which enforces condition (ii) by using additional corrector steps, has superlinear convergence under the standard assumption of strict complementarity. Finally, we point out that condition (ii) can be made weaker and show the superlinear convergence under the strict complementarity assumption and a weaker condition than (ii).     

A New Wide Neighborhood Primal–Dual Infeasible-Interior-Point Method for Symmetric Cone Programming

We present a new infeasible-interior-point method, based on a wide neighborhood, for symmetric cone programming. The convergence is shown for a commutative class of search directions, which includes the Nesterov–Todd direction and the xs and sx directions. Moreover, we derive the complexity bound of the wide neighborhood infeasible interior-point methods that coincides with the currently best known theoretical complexity bounds for the short step path-following algorithm.     

Nonlinear rescaling vs. smoothing technique in convex optimization

We introduce an alternative to the smoothing technique approach for constrained optimization. As it turns out for any given smoothing function there exists a modification with particular properties. We use the modification for Nonlinear Rescaling (NR) the constraints of a given constrained optimization problem into an equivalent set of constraints.?The constraints transformation is scaled by a vector of positive parameters. The Lagrangian for the equivalent problems is to the correspondent Smoothing Penalty functions as Augmented Lagrangian to the Classical Penalty function or MBFs to the Barrier Functions. Moreover the Lagrangians for the equivalent problems combine the best properties of Quadratic and Nonquadratic Augmented Lagrangians and at the same time are free from their main drawbacks.?Sequential unconstrained minimization of the Lagrangian for the equivalent problem in primal space followed by both Lagrange multipliers and scaling parameters update leads to a new class of NR multipliers methods, which are equivalent to the Interior Quadratic Prox methods for the dual problem.?We proved convergence and estimate the rate of convergence of the NR multipliers method under very mild assumptions on the input data. We also estimate the rate of convergence under various assumptions on the input data.?In particular, under the standard second order optimality conditions the NR method converges with Q-linear rate without unbounded increase of the scaling parameters, which correspond to the active constraints.?We also established global quadratic convergence of the NR methods for Linear Programming with unique dual solution.?We provide numerical results, which strongly support the theory. Received: September 2000 / Accepted: October 2001?Published online April 12, 2002     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

A Non-Interior Path Following Method for Convex Quadratic Programming Problems with Bound Constraints

We propose a non-interior path following algorithm for convex quadratic programming problems with bound constraints based on Chen-Harker-Kanzow-Smale smoothing technique. Conditions are given under which the algorithm is globally convergent or globally linearly convergent. Preliminary numerical experiments indicate that the method is promising.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

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     

非线性互补问题的一种不可行非内点连续算法

基于Chen-Harker—Kanzow-Smale光滑函数，对单调非线性互补问题NCP(f)给出了一种不可行非内点连续算法，该算法在每次迭代时只需求解一个线性等式系统，执行一次线搜索，算法在NCP(f)的解处不需要严格互补的条件下，具有全局线性收敛性和局部二次收敛性．