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     

Entropic proximal decomposition methods for convex programs and variational inequalities

We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to produce for the first time provably convergent decomposition schemes based on C ^∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty solution sets, global convergence of the primal-dual sequences produced by the algorithm is established. Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001     

On the convexity of the multiplicative potential and penalty functions and related topics

It is well known that a function f of the real variable x is convex if and only if (x,y)→yf(y ^-1 x),y>0 is convex. This is used to derive a recursive proof of the convexity of the multiplicative potential function. In this paper, we obtain a conjugacy formula which gives rise, as a corollary, to a new rule for generating new convex functions from old ones. In particular, it allows to extend the aforementioned property to functions of the form (x,y)→g(y)f(g(y)^-1 x) and provides a new tool for the study of the multiplicative potential and penalty functions. Received: June 3, 1999 / Accepted: September 29, 2000?Published online January 17, 2001     

An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints

In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids. The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems. Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA and the combined DCA-branch-and-bound algorithm. Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000     

The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform P-functions

We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods. By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing parameter and establish the global linear convergence of this method. Some preliminary computational results are reported. Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000     

Conditions ensuring the applicability of cutting-plane methods for solving variational inequalities

Let VIP(F,C) denote the variational inequality problem associated with the mapping F and the closed convex set C. In this paper we introduce weak conditions on the mapping F that allow the development of a convergent cutting-plane framework for solving VIP(F,C). In the process we introduce, in a natural way, new and useful notions of generalized monotonicity for which first order characterizations are presented. Received: September 25, 1997 / Accepted: March 2, 1999?Published online July 20, 2000     

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     

A probabilistic analysis of a measure of combinatorial complexity for the central curve

We investigate certain combinatorial properties of the central curve associated with interior point methods for linear optimization. We define a measure of complexity for the curve in terms of the number of turns, or changes of direction, that it makes in a geometric sense, and then perform an average case analysis of this measure for P-matrix linear complementarity problems. We show that the expected number of nondegenerate turns taken by the central curve is bounded by n ²-n, where the expectation is taken with respect to a sign-invariant probability distribution on the problem data. As an alternative measure of complexity, we also consider the number of times the central curve intersects with a wide class of algebraic hypersurfaces, including such objects as spheres and boxes. As an example of the results obtained, we show that the primal and dual variables in each coordinate of the central curve cross each other at most once, on average. As a further example, we show that the central curve intersects any sphere centered at the origin at most twice, on average. Received May 28, 1998 / Revised version received October 12, 1999?Published online December 15, 1999     

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     

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     

Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods

The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance. Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000     

Existence of optimal solutions and duality results under weak conditions

In this paper we consider an ordinary convex program with no qualification conditions (such as Slater’s condition) and for which the optimal set is neither required to be compact, nor to be equal to the sum of a compact set and a linear space. It is supposed only that the infimum α is finite. A very wide class of convex functions is exhibited for which the optimum is always attained and α is equal to the supremum of the ordinary dual program. Additional results concerning the existence of optimal solutions in the non convex case are also given. Received: February 1, 1999 / Accepted: December 15, 1999?Published online February 23, 2000     

Error bounds for proximal point subproblems and associated inexact proximal point algorithms

We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem, and of the closely related problem of finding a zero of a maximal monotone operator. A new merit function is proposed for proximal point subproblems associated with the latter. This merit function is based on Burachik-Iusem-Svaiter’s concept of ε-enlargement of a maximal monotone operator. For variational inequalities, we establish a precise relationship between the regularized gap function, which is a natural error measure in this context, and our new merit function. Some error bounds are derived using both merit functions for the corresponding formulations of the proximal subproblem. We further use the regularized gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact proximal point method preserves all the desirable global and local convergence properties of the classical exact/inexact method, while providing a constructive error tolerance criterion, suitable for further practical applications. The use of other tolerance rules is also discussed. Received: April 28, 1999 / Accepted: March 24, 2000?Published online July 20, 2000     

An infeasible-interior-point potential-reduction algorithm for linear programming

n . The method is based on Rockafellar’s proximal point algorithm and a cutting-plane technique. At each step, we use an approximate proximal point p^a(x_k) of x_k to define a v_k∈∂_εkf(p^a(x_k)) with ε_k≤α∥v_k∥, where α is a constant. The method monitors the reduction in the value of ∥v_k∥ to identify when a line search on f should be used. The quasi-Newton step is used to reduce the value of ∥v_k∥. Without the differentiability of f, the method converges globally and the rate of convergence is Q-linear. Superlinear convergence is also discussed to extend the characterization result of Dennis and Moré. Numerical results show the good performance of the method. Received October 3, 1995 / Revised version received August 20, 1998 Published online January 20, 1999     

An outer approximate subdifferential method for piecewise affine optimization

Piecewise affine functions arise from Lagrangian duals of integer programming problems, and optimizing them provides good bounds for use in a branch and bound method. Methods such as the subgradient method and bundle methods assume only one subgradient is available at each point, but in many situations there is more information available. We present a new method for optimizing such functions, which is related to steepest descent, but uses an outer approximation to the subdifferential to avoid some of the numerical problems with the steepest descent approach. We provide convergence results for a class of outer approximations, and then develop a practical algorithm using such an approximation for the compact dual to the linear programming relaxation of the uncapacitated facility location problem. We make a numerical comparison of our outer approximation method with the projection method of Conn and Cornuéjols, and the bundle method of Schramm and Zowe. Received September 10, 1998 / Revised version received August 1999?Published online December 15, 1999     

On semidefinite linear complementarity problems

Given a linear transformation L:? ⁿ →? ⁿ and a matrix Q∈? ⁿ , where ? ⁿ is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,? ⁿ ₊,Q) over the cone ? ⁿ ₊ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R ^n×n , we consider the linear transformation L _A :? ⁿ →? ⁿ defined by L _A (X):=AX+XA ^T and show that the P- and Q-properties for L _A are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov. Received: March 1999 / Accepted: November 1999?Published online April 20, 2000     

On inexact generalized proximal methods with a weakened error tolerance criterion

Two inexact versions of a Bregman-function-based proximal method for finding a zero of a maximal monotone operator, suggested in [J. Eckstein (1998). Approximate iterations in Bregman-function-based proximal algorithms. Math. Programming, 83, 113–123; P. da Silva, J. Eckstein and C. Humes (2001). Rescaling and stepsize selection in proximal methods using separable generalized distances. SIAM J. Optim., 12, 238–261], are considered. For a wide class of Bregman functions, including the standard entropy kernel and all strongly convex Bregman functions, convergence of these methods is proved under an essentially weaker accuracy condition on the iterates than in the original papers.

Also the error criterion of a logarithmic–quadratic proximal method, developed in [A. Auslender, M. Teboulle and S. Ben-Tiba (1999). A logarithmic-quadratic proximal method for variational inequalities. Computational Optimization and Applications, 12, 31–40], is relaxed, and convergence results for the inexact version of the proximal method with entropy-like distance functions are described.

For the methods mentioned, like in [R.T. Rockafellar (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim., 14, 877–898] for the classical proximal point algorithm, only summability of the sequence of error vector norms is required.     

Improving the robustness of descent-based methods for semismooth equations using proximal perturbations

A common difficulty encountered by descent-based equation solvers is convergence to a local (but not global) minimum of an underlying merit function. Such difficulties can be avoided by using a proximal perturbation strategy, which allows the iterates to escape the local minimum in a controlled fashion. This paper presents the proximal perturbation strategy for a general class of methods for solving semismooth equations and proves subsequential convergence to a solution based upon a pseudomonotonicity assumption. Based on this approach, two sample algorithms for solving mixed complementarity problems are presented. The first uses an extremely simple (but not very robust) basic algorithm enhanced by the proximal perturbation strategy. The second uses a more sophisticated basic algorithm based on the Fischer-Burmeister function. Test results on the MCPLIB and GAMSLIB complementarity problem libraries demonstrate the improvement in robustness realized by employing the proximal perturbation strategy. Received July 15, 1998 / Revised version received June 28, 1999?Published online November 9, 1999     

On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating

In previous work, the authors provided a foundation for the theory of variable metric proximal point algorithms in Hilbert space. In that work conditions are developed for global, linear, and super–linear convergence. This paper focuses attention on two matrix secant updating strategies for the finite dimensional case. These are the Broyden and BFGS updates. The BFGS update is considered for application in the symmetric case, e.g., convex programming applications, while the Broyden update can be applied to general monotone operators. Subject to the linear convergence of the iterates and a quadratic growth condition on the inverse of the operator at the solution, super–linear convergence of the iterates is established for both updates. These results are applied to show that the Chen–Fukushima variable metric proximal point algorithm is super–linearly convergent when implemented with the BFGS update. Received: September 12, 1996 / Accepted: January 7, 2000?Published online March 15, 2000     

On convergence of the Gauss-Newton method for convex composite optimization

The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h. Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001