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).     

Representation,interpolation, and reiteration theorems for generalized approximation spaces

We show that the representation theorem for classical approximation spaces can be generalized to spaces A(X,l ^q (ℬ))={f∈X:{E _n (f)}∈l ^q (ℬ)} in which the weighted l ^q -space l ^q (ℬ) can be (more or less) arbitrary. We use this theorem to show that generalized approximation spaces can be viewed as real interpolation spaces (defined with K-functionals or main-part K-functionals) between couples of quasi-normed spaces which satisfy certain Jackson and Bernstein-type inequalities. Especially, interpolation between an approximation space and the underlying quasi-normed space leads again to an approximation space. Together with a general reiteration theorem, which we also prove in the present paper, we obtain formulas for interpolation of two generalized approximation spaces. Received: December 6, 2001; in final form: April 2, 2002?Published online: March 14, 2003     

On Kernel polynomials and self-perturbation of orthogonal polynomials

Given an orthogonal polynomial system {Q _n (x)} _n=0 ^∞, define another polynomial system by where α _n are complex numbers and t is a positive integer. We find conditions for {P _n (x)} _n=0 ^∞ to be an orthogonal polynomial system. When t=1 and α₁≠0, it turns out that {Q _n (x)} _n=0 ^∞ must be kernel polynomials for {P _n (x)} _n=0 ^∞ for which we study, in detail, the location of zeros and semi-classical character. Received: November 25, 1999; in final form: April 6, 2000?Published online: June 22, 2001     

Smoothing Newton method for NCP with the identification of degenerate indices

We present a new smoothing Newton method for nonlinear complementarity problems (NCP(F)) by using an NCP function to reformulate the problem to its equivalent form. Compared with most current smoothing methods, our method contains an estimating technique based on the active-set strategy. This technique focuses on the identification of the degenerate set for a solution x^∗ of the NCP(F). The proposed method has the global convergence, each accumulation point is a solution of the problem. The introduction of the active-set strategy effectively reduces the scale of the problem. Under some regularity assumption, the degenerate set can be identified correctly near the solution and local superlinear convergence is obtained as well.     

Representation of measurable functions by series in Walsh subsystems

For any sequence {ω(n)} _n∈ℕ tending to infinity we construct a “quasiquadratic” representation spectrum Λ = {n ² + o(ω(n))} _n∈ℕ: for any almost everywhere (a. e.) finite measurable function f(x) there exists a series in the form $ \mathop \sum \limits_{k \in \Lambda } $ \mathop \sum \limits_{k \in \Lambda } α _k ω _k (x) that converges a. e. to this function, where {w _k (x)} _k∈ℕ is the Walsh system. We find representation spectra in the form {n ^l + o(n ^l )} _n∈ℕ, where l ∈ {2 ^k } _k∈ℕ.     

Homomorphisms between JC＊-algebras and Lie C＊-algebras

It is shown that every almost ＊-homomorphism h ： A→B of a unital JC＊-algebra A to a unital JC＊-algebra B is a ＊-homomorphism when h（rx） = rh（x） （r 〉 1） for all x∈A, and that every almost linear mapping h ： A→B is a ＊-homomorphism when h（2^nu o y） - h（2^nu） o h（y）, h（3^nu o y） - h（3^nu） o h（y） or h（q^nu o y） = h（q^nu） o h（y） for all unitaries u ∈A, all y ∈A, and n = 0, 1,.... Here the numbers 2, 3, q depend on the functional equations given in the almost linear mappings. We prove that every almost ＊-homomorphism h ： A→B of a unital Lie C＊-algebra A to a unital Lie C＊-algebra B is a ＊-homomorphism when h（rx） = rh（x） （r 〉 1） for all x ∈A.     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system

A conic linear system is a system of the form?P(d): find x that solves b - Ax∈C _Y , x∈C _X ,? where C _X and C _Y are closed convex cones, and the data for the system is d=(A,b). This system is“well-posed” to the extent that (small) changes in the data (A,b) do not alter the status of the system (the system remains solvable or not). Renegar defined the “distance to ill-posedness”, ρ(d), to be the smallest change in the data Δd=(ΔA,Δb) for which the system P(d+Δd) is “ill-posed”, i.e., d+Δd is in the intersection of the closure of feasible and infeasible instances d’=(A’,b’) of P(·). Renegar also defined the “condition measure” of the data instance d as C(d):=∥d∥/ρ(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equations. This study presents two categories of results related to ρ(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of ρ(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of ρ(d) to within certain constants, depending on whether P(d) is feasible or not, and where the constants depend on properties of the cones and the norms used. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P(d) or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P(d) (or its alternative system when P(d) is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r≤c ₁ C(d), and such that r≥ and R≤c ₃ C(d), where c ₁,c ₂,c ₃ are constants that depend only on properties of the cones and the norms used. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P(d) that is not too far from the origin and whose radius is not too small. Received November 2, 1995 / Revised version received June 26, 1998?Published online May 12, 1999     

Tracking and invariance problems for some classes of discrete delay systems

Consider the system with perturbation g _k ∈ ℝ ⁿ and output z _k = Cx _k . Here, A _k ,A _k ^(s) ∈ ℝ ^{n × n} , B _k ⁽¹⁾ ∈ ℝ ^{n × p} , B _k ⁽²⁾ ∈ ℝ ^{n × m} , C ∈ ℝ ^{p × n} . We construct a special Lyapunov-Krasovskii functional in order to synthesize controls u _k ⁽¹⁾ and u _k ⁽²⁾ for which the following properties are satisfied:

On convergence of gradient-dependent integrands

We study convergence properties of {υ(∇u _k )}k∈ℕ if υ ∈ C(ℝ ^m×m ), |υ(s)| ⩽ C(1+|s| ^p ), 1 < p < + ∞, has a finite quasiconvex envelope, u _k → u weakly in W ^1,p (Ω; ℝ ^m ) and for some g ∈ C(Ω) it holds that ∫_Ω g(x)υ(∇u _k (x))dx → ∫_Ω g(x)Qυ(∇u(x))dx as k → ∞. In particular, we give necessary and sufficient conditions for L ¹-weak convergence of {det ∇u _k } _k∈ℕ to det ∇u if m = n = p. Dedicated to Jiří V. Outrata on the occasion of his 60th birthday This work was supported by the grants IAA 1075402 (GA AV ČR) and VZ6840770021 (MŠMT ČR).