Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems

In this paper several types of perturbations on a convex inequality system are considered, and conditions are obtained for the system to be well-conditioned under these types of perturbations, where the well-conditionedness of a convex inequality system is defined in terms of the uniform boundedness of condition numbers under a set of perturbations. It is shown that certain types of perturbations can be used to characterize the well-conditionedness of a convex inequality system, in which either the system has a bounded solution set and satisfies the Slater condition or an associated convex inequality system, which defines the recession cone of the solution set for the system, satisfies the Slater condition. Finally, sufficient conditions are given for the existence of a global error bound for an analytic system. It is shown that such a global error bound always holds for any inequality system defined by finitely many convex analytic functions when the zero vector is in the relative interior of the domain of an associated convex conjugate function.     

Perturbation analysis of global error bounds for systems of linear inequalities

This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and a certain compactness condition, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if the original system is bounded or its homogeneous system has a strict solution. Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000     

Error bounds for nondifferentiable convex inequalities under a strong Slater constraint qualification

A global error bound is given on the distance between an arbitrary point in then-dimensional real spaceR ⁿ and its projection on a nonempty convex set determined bym convex, possibly nondifferentiable, inequalities. The bound is in terms of a natural residual that measures the violations of the inequalities multiplied by a new simple condition constant that embodies a single strong Slater constraint qualification (CQ) which implies the ordinary Slater CQ. A very simple bound on the distance to the projection relative to the distance to a point satisfying the ordinary Slater CQ is given first and then used to derive the principal global error bound. This material is based on research supported by National Science Foundation Grant CCR-9322479 and Air Force Office of Scientific Research grant F49620-97-1-0326.     

On the Stability of the Boundary of the Feasible Set in Linear Optimization

This paper analizes the relationship between the stability properties of the closed convex sets in finite dimensions and the stability properties of their corresponding boundaries. We consider a given closed convex set represented by a certain linear inequality system whose coefficients can be arbitrarily perturbed, and we measure the size of these perturbations by means of the pseudometric of the uniform convergence. It is shown that the feasible set mapping is Berge lower semicontinuous at if and only if the boundary mapping satisfies the same property. Moreover, if the boundary mapping is semicontinuous in any sense (lower or upper; Berge or Hausdorff) at , then it is also closed at . All the mentioned stability properties are equivalent when the feasible set is a convex body.     

A Note on Error Bounds for Convex and Nonconvex Programs

Given a single feasible solution and a single infeasible solution of a mathematical program, we provide an upper bound to the optimal dual value. We assume that satisfies a weakened form of the Slater condition. We apply the bound to convex programs and we discuss its relation to Hoffman-like bounds. As a special case, we recover a bound due to Mangasarian [11] on the distance of a point to a convex set specified by inequalities.     

Limiting Lagrangians: A primal approach

In this paper, we consider a convex program with either a finite or an infinite number of constraints and its formal Lagrangian dual. We show that either the primal program satisfies a general condition which implies there is no duality gap or that there is a nonzero vectord with the following properties: First, wheneverd is added to the objective function, where is a positive number not greater than one, the resulting program satisfies the general sufficient condition cited above for no duality gap. Second, the optimal value of this perturbed program is attained and tends to the optimal value of the original program as tends to zero. Third, the optimal solutions of the perturbed programs form a minimizing sequence of the original program. As a consequence of the above, we derive the limiting Lagrangian theory of Borwein, Duffin, and Jeroslow.The authors are indebted to an unknown referee who suggested the very short and elegant proofs of Lemma 2.3 and Theorem 2.3.This work was completed while the first author was a member of the College of Management, Georgia Institute of Technology, Atlanta, Georgia.     

Best Approximation by Free Knot Splines

We consider the problem of finding the best (uniform) approximation of a given continuous function by spline functions with free knots. Our approach can be sketched as follows. By using the Gauß transform with arbitrary positive real parameter t, we map the set of splines under consideration onto a function space, which is arbitrarily close to the spline set, but satisfies the local Haar condition and also possesses other nice structural properties. This enables us to give necessary and sufficient conditions for best approximations (in terms of alternants) and, under some assumptions, even full characterizations and a uniqueness result. By letting t 0, we recover best approximation in the original spline space. Our results are illustrated by some numerical examples, which show in particular the nice alternation behavior of the error function.     

On the linear convergence of the alternating direction method of multipliers

We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth \(\ell _1\) regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.     

αBB: A global optimization method for general constrained nonconvex problems

A branch and bound global optimization method,BB, for general continuous optimization problems involving nonconvexities in the objective function and/or constraints is presented. The nonconvexities are categorized as being either of special structure or generic. A convex relaxation of the original nonconvex problem is obtained by (i) replacing all nonconvex terms of special structure (i.e. bilinear, fractional, signomial) with customized tight convex lower bounding functions and (ii) by utilizing the parameter as defined in [17] to underestimate nonconvex terms of generic structure. The proposed branch and bound type algorithm attains finite-convergence to the global minimum through the successive subdivision of the original region and the subsequent solution of a series of nonlinear convex minimization problems. The global optimization method,BB, is implemented in C and tested on a variety of example problems.     

Perturbation theory and backward error forAX−XB=C

Because of the special structure of the equationsAX–XB=C the usual relation for linear equations backward error = relative residual does not hold, and application of the standard perturbation result forAx=b yields a perturbation bound involving sep (A, B)^–1 that is not always attainable. An expression is derived for the backward error of an approximate solutionY; it shows that the backward error can exceed the relative residual by an arbitrary factor. A sharp perturbation bound is derived and it is shown that the condition number it defines can be arbitrarily smaller than the sep(A, B)^–1-based quantity that is usually used to measure sensitivity. For practical error estimation using the residual of a computed solution an LAPACK-style bound is shown to be efficiently computable and potentially much smaller than a sep-based bound. A Fortran 77 code has been written that solves the Sylvester equation and computes this bound, making use of LAPACK routines.Nuffield Science Research Fellow. This work was carried out while the author was a visitor at the Institute for Mathematics and its Applications, University of Minnesota.     

Minimizing a quasi-concave function subject to a reverse convex constraint

Any constraintg(x)0 is called a reverse convex constraint ifg: R ⁿ R ¹ is a continuous convex function. This paper establishes a finite method for finding an optimal solution to a concave program with an additional reverse convex constraint. The method presented is a new approach to global optimization problems since it combines the idea of the branch and bound method with the idea of the cutting plane method.This paper is dedicated to Professor A. Pelczar     

Finite element analysis of exponentially fitted Lumped schemes for time-dependent convection-diffusion problems

Summary In the paper we consider a singularly perturbed linear parabolic initialboundary value problem in one space variable. Two exponential fitted schemes are derived for the problem using Petrov-Galerkin finite element methods with various choices of trial and test spaces. On rectangular meshes which are either arbitrary or slightly restricted, we derive global energy norm andL ² norm and localL error bounds which are uniform in the diffusion parameter. Numerical results are also persented.     

Error bounds for infinite systems of convex inequalities without Slater’s condition

The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints. We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do not assume that the Slater condition holds which has been required in almost all earlier papers. Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000     

Negatively Correlated Random Variables and Mason’s Conjecture for Independent Sets in Matroids

Mason’s Conjecture asserts that for an m-element rank r matroid the sequence is logarithmically concave, in which I _k is the number of independent k-sets of . A related conjecture in probability theory implies these inequalities provided that the set of independent sets of satisfies a strong negative correlation property we call the Rayleigh condition. This condition is known to hold for the set of bases of a regular matroid. We show that if ω is a weight function on a set system that satisfies the Rayleigh condition then is a convex delta-matroid and ω is logarithmically submodular. Thus, the hypothesis of the probabilistic conjecture leads inevitably to matroid theory. We also show that two-sums of matroids preserve the Rayleigh condition in four distinct senses, and hence that the Potts model of an iterated two-sums of uniform matroids satisfies the Rayleigh condition. Numerous conjectures and auxiliary results are included. Research supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.     

Finding all solutions of nonlinearly constrained systems of equations

A new approach is proposed for finding all-feasible solutions for certain classes of nonlinearly constrained systems of equations. By introducing slack variables, the initial problem is transformed into a global optimization problem (P) whose multiple global minimum solutions with a zero objective value (if any) correspond to all solutions of the initial constrained system of equalities. All-globally optimal points of (P) are then localized within a set of arbitrarily small disjoint rectangles. This is based on a branch and bound type global optimization algorithm which attains finite-convergence to each of the multiple global minima of (P) through the successive refinement of a convex relaxation of the feasible region and the subsequent solution of a series of nonlinear convex optimization problems. Based on the form of the participating functions, a number of techniques for constructing this convex relaxation are proposed. By taking advantage of the properties of products of univariate functions, customized convex lower bounding functions are introduced for a large number of expressions that are or can be transformed into products of univariate functions. Alternative convex relaxation procedures involve either the difference of two convex functions employed in BB [23] or the exponential variable transformation based underestimators employed for generalized geometric programming problems [24]. The proposed approach is illustrated with several test problems. For some of these problems additional solutions are identified that existing methods failed to locate.     

Invariance of asymptotic stability of perturbed linear systems on Hilbert space

The questions of stabilizability of structurally perturbed or uncertain linear systems in Hilbert space of the form are considered. The operatorA is assumed to be the infinitesimal generator of aC ₀-semigroup of contractionsT(t),t0, in a Hilbert spaceX;B is a bounded linear operator from another Hilbert spaceU toX; and {P(r),r } is a family of bounded or unbounded perturbations ofA inX, where is an arbitrary set, not necessarily carrying any topology. Sufficient conditions are presented that guarantee controllability and stabilizability of the perturbed system, given that the unperturbed system has similar properties. In particular, it is shown that, for certain classes of perturbations, weak and strong stabilizability properties are preserved for the same state feedback operator.This work was supported in part by the Natural Science and Engineering Research Council of Canada under Grant No. A7109.     

An inexact spectral bundle method for convex quadratic semidefinite programming

We present an inexact spectral bundle method for solving convex quadratic semidefinite optimization problems. This method is a first-order method, hence requires much less computational cost in each iteration than second-order approaches such as interior-point methods. In each iteration of our method, we solve an eigenvalue minimization problem inexactly, and solve a small convex quadratic semidefinite program as a subproblem. We give a proof of the global convergence of this method using techniques from the analysis of the standard bundle method, and provide a global error bound under a Slater type condition for the problem in question. Numerical experiments with matrices of order up to 3000 are performed, and the computational results establish the effectiveness of this method.     

Generalized solutions to semilinear hyperbolic systems

In this article semilinear hyperbolic first order systems in two variables are considered, whose nonlinearity satisfies a global Lipschitz condition. It is shown that these systems admit unique global solutions in the Colombeau algebraG(²). In particular, this provides unique generalized solutions for arbitrary distributions as initial data. The solution inG(²) is shown to be consistent with the locally integrable or the distributional solutions, when they exist.     

Sensitivity analysis for generalized linear-quadratic problems

In this paper, we study simple necessary and sufficient conditions for the stability of generalized linear-quadratic programs under perturbations of the data. The concept of generalized linear-quadratic problem was introduced by Rockafellar and Wets and consists of solving saddle points of a linear-quadratic convex concave functionJ onU×V, whereU andV are polyhedral convex sets in ⁿ and ^m . This paper also establishes results on the closedness and the uniform boundedness of the saddle-point solution sets. These properties are then used to obtain results on the continuity and the directional derivative of the perturbed saddle value.The research of the first author was supported by the CEE, Grant No. CI1-CT92-0046.     

An error bound concerning Howard's Value Determination Equation

For a discrete Markovian Decision Process with finite state space an error bound is given for an arbitrary approximate solutionv of the Value Determination Equation.