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     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Non-special divisors on real algebraic curves and embeddings into real projective spaces

We show that there is a large class of non-special divisors of relatively small degree on a given real algebraic curve. If the real algebraic curve has many real components, such a divisor gives rise to an embedding (birational embedding, resp.) of the real algebraic curve into the real projective space ℙ ^r for r≥3 (r=2, resp.). We study these embeddings in quite some detail. Received: October 17, 2001?Published online: February 20, 2003     

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     

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     

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     

Continuous modified Newton’s-type method for nonlinear operator equations

A nonlinear operator equation F(x)=0, F:H→H, in a Hilbert space is considered. Continuous Newton’s-type procedures based on a construction of a dynamical system with the trajectory starting at some initial point x ₀ and becoming asymptotically close to a solution of F(x)=0 as t→+∞ are discussed. Well-posed and ill-posed problems are investigated. Received: June 29, 2001; in final form: February 26, 2002?Published online: February 20, 2003 This paper was finished when AGR was visiting Institute for Theoretical Physics, University of Giessen. The author thanks DAAD for support     

Some presentations for the special linear groups on finite fields

We simplify the Steinberg presentation of SL _n (F _d ), where n≥1 and F _d is any finite field with d elements. That presentation has the elementary matrices e _ij (r), with i,j∈{1,...,n}, i≠=j and r∈F _d , as generators, and (E1)–(E3), described at the opening of this work, as relations. The presentation that we shall obtain reduces the number of generators e _ij (r) and relations (E1)–(E3). In particular, relations (E3) are considerably reduced. Received: March 16, 1998; in final form: November 3, 2000?Published online: October 2, 2001     

On a characterization of convexity-preserving maps, Davidon’s collinear scalings and Karmarkar’s projective transformations

In a recent paper, the authors have proved results characterizing convexity-preserving maps defined on a subset of a not-necessarily finite dimensional real vector space as projective maps. The purpose of this note is three-fold. First, we state a theorem characterizing continuous, injective, convexity-preserving maps from a relatively open, connected subset of an affine subspace of ℝ ^m into ℝ ⁿ as projective maps. This result follows from the more general results stated and proved in a coordinate-free manner in the above paper, and is intended to be more accessible to researchers interested in optimization algorithms. Second, based on that characterization theorem, we offer a characterization theorem for collinear scalings first introduced by Davidon in 1977 for deriving certain algorithms for nonlinear optimization, and a characterization theorem for projective transformations used by Karmarkar in 1984 in his linear programming algorithm. These latter two theorems indicate that Davidon’s collinear scalings and Karmarkar’s projective transformations are the only continuous, injective, convexity-preserving maps possessing certain features that Davidon and Karmarkar respectively desired in the derivation of their algorithms. The proofs of these latter two theorems utilize our characterization of continuous, injective, convexity-preserving maps in a way that has implications to the choice of scalings and transformations in the derivation of optimization algorithms in general. The third purpose of this note is to point this out. Received: January 2000 / Accepted: November 2000?Published online January 17, 2001     

Green functions and eigenfunction expansions for the square of the Laplace–Beltrami operator on plane domains

For a certain class of domains Ω⊂ℂ with smooth boundary and Δtilde;_Ω=w ²Δ the Laplace–Beltrami operator with respect to the Poincaré metric ds ²=w(z)^-2 dz dz on Ω, we (1) show that the Green function for the biharmonic operator Δtilde;_Ω ², with Dirichlet boundary data, is positive on Ω×Ω; and (2) obtain an eigenfunction expansion for the operator Δtilde;_Ω, which reduces to the ordinary non-Euclidean Fourier transform of Helgason for Ω=𝔻 (the unit disc). In both cases the proofs go via uniformization, and in (1) we obtain a Myrberg-like formula for the corresponding Green function. Finally, the latter formula as well as the eigenfunction expansion are worked out more explicitly in the simplest case of Ω an annulus, and a result is established concerning the convergence of the series ∑ _ω∈G (1-|ω0|²) ^s for G the covering group of the uniformization map of Ω and 0<s<1. Received: August 21, 2000?Published online: October 30, 2002 RID="*" ID="*"The first author was supported by GA AV CR grants no. A1019701 and A1019005.     

A priori and universal estimates for global solutions of superlinear degenerate parabolic equations

We prove an a priori estimate and a universal bound for any global solution of the nonlinear degenerate reaction-diffusion equation u _t =Δu ^m +u ^p in a bounded domain with zero Dirichlet boundary conditions. Received: October 1, 2001?Published online: July 9, 2002     

Oscillation and asymptotic behaviour of a class of higher-order non-linear difference equations

The dynamical characteristics of scalar difference equations of the form?x _{n +1}=f ₁(x _{n −τ1})+f ₂(x _{n −τ2}), n=0,1,2,...,?are investigated. A necessary and sufficient condition is obtained for all positive solutions to be oscillatory about a unique positive equilibrium point and sufficient criteria for the global attractivity of the equilibrium are established. Also, the stability and periodicity of more general equations are studied via comparison with the corresponding properties of an associated first-order non-linear equation. Received: September 5, 2001; in final form: March 7, 2002?Published online: April 14, 2003     

Extension of locally pseudocompact group actions

It is shown that: (1) any action of a Moscow group G on a first countable, Dieudonné complete (in particular, on a metrizable) space X can uniquely be extended to an action of the Dieudonné completion γG on X, (2) any action of a locally pseudocompact topological group G on a b _f -space (in particular, on a first countable space) X can uniquely be extended to an action of the Weil completion on the Dieudonné completion γX of X. As a consequence, we obtain that, for each locally pseudocompact topological group G, every G-space with the b _f -property admits an equivariant embedding into a compact Hausdorff G-space. Furthermore, for each pseudocompact group G, every metrizable G-space has a G-invariant metric compatible with its topology. We also give a direct construction of such an invariant metric. Received: June 22, 2000; in final form: May 22, 2001?Published online: June 11, 2002     

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     

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     

On the limit laws of the second order for additive functionals of Harris recurrent Markov chains

Let {X _n } _{n ≥0} be a Harris recurrent Markov chain with state space E and invariant measure π. The law of the iterated logarithm and the law of weak convergence are given for the additive functionals of the form

Detecting Jacobian sparsity patterns by Bayesian probing

In this paper we describe an automatic procedure for successively reducing the set of possible nonzeros in a Jacobian matrix until eventually the exact sparsity pattern is obtained. The dependence information needed in this probing process consist of “Boolean” Jacobian-vector products and possibly also vector-Jacobian products, which can be evaluated exactly by automatic differentiation or approximated by divided differences. The latter approach yields correct sparsity patterns, provided there is no exact cancellation at the current argument.?Starting from a user specified, or by default initialized, probability distribution the procedure suggests a sequence of probing vectors. The resulting information is then used to update the probabilities that certain elements are nonzero according to Bayes’ law. The proposed probing procedure is found to require only O(logn) probing vectors on randomly generated matrices of dimension n, with a fixed number of nonzeros per row or column. This result has been proven for (block-) banded matrices, and for general sparsity pattern finite termination of the probing procedure can be guaranteed. Received: April 29, 2000 / Accepted: September 2001?Published online April 12, 2002     

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     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001