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     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Existence and multiplicity of solutions for a nonlinear Neumann problem

We consider a Neumann problem of the type -εΔu+F ^′(u(x))=0 in an open bounded subset Ω of R ⁿ , where F is a real function which has exactly k maximum points. Using Morse theory we find that, for ε suitably small, there are at least 2k nontrivial solutions of the problem and we give some qualitative information about them. Received: October 30, 1999 Published online: December 19, 2001     

A note on quadratic forms

We extend an interesting theorem of Yuan [12] for two quadratic forms to three matrices. Let C ₁, C ₂, C ₃ be three symmetric matrices in ℜ ^n×n , if max{x ^T C ₁ x,x ^T C ₂ x,x ^T C ₃ x}≥0 for all x∈ℜ ⁿ , it is proved that there exist t _i ≥0 (i=1,2,3) such that ∑ _i=1 ³ t _i =1 and ∑ _i=1 ³ t _i C _i has at most one negative eigenvalue. Received February 18, 1997 / Revised version received October 1, 1997? Published online June 11, 1999     

Primal and dual convergence of a proximal point exponential penalty method for linear programming

We consider the diagonal inexact proximal point iteration where f(x,r)=c ^T x+r∑exp[(A _i x-b _i )/r] is the exponential penalty approximation of the linear program min{c ^T x:Ax≤b}. We prove that under an appropriate choice of the sequences λ _k , ε _k and with some control on the residual ν ^k , for every r _k →0⁺ the sequence u ^k converges towards an optimal point u ^∞ of the linear program. We also study the convergence of the associated dual sequence μ _i ^k =exp[(A _i u ^k -b _i )/r _k ] towards a dual optimal solution. Received: May 2000 / Accepted: November 2001?Published online June 25, 2002     

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     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

A method of approximation by rational functions on the real line

For a given system of numbers {z _k } _k=1 ⁿ , IMz _k > 0, rational functions of order 4n — 2 are constructed which effect for a functionf(x∈C _∞) an approximation of the same order as the best approximation by proper rational functions having poles at the points {z _{k k=1} ⁿ and . Translated from Matematicheskie Zametki, Vol. 22, No. 3, pp. 375–380, September, 1977. In conclusion the author thanks E. P. Dolzhenko and S. B. Stechkin, whose discussions contributed to improvements in this work.     

Adaptive policies for time-varying stochastic systems under discounted criterion

We consider a class of time-varying stochastic control systems, with Borel state and action spaces, and possibly unbounded costs. The processes evolve according to a discrete-time equation x _{n + 1}=G _n (x _n , a _n , ξ_n), n=0, 1, … , where the ξ_n are i.i.d. ℜ^k-valued random vectors whose common density is unknown, and the G _n are given functions converging, in a restricted way, to some function G _∞ as n→∞. Assuming observability of ξ_n, we construct an adaptive policy which is asymptotically discounted cost optimal for the limiting control system x _n+1=G _∞ (x _n , a _n , ξ_n).