Bounded linear regularity of convex sets in Banach spaces and its applications

This paper deals with bounded linear regularity, linear regularity and the strong conical hull intersection property (CHIP) of a collection of finitely many closed convex intersecting sets in Banach spaces. It is shown that, as in finite dimensional space setting (see [6]), the standard constraint qualification implies bounded linear regularity, which in turn yields the strong conical hull intersection property, and that the collection of closed convex sets {C ₁, . . . ,C _n } is bounded linearly regular if and only if the tangent cones of {C ₁, . . . ,C _n } has the CHIP and the normal cones of {C ₁, . . . ,C _n } has the property (G)(uniformly on a neighborhood in the intersection C). As applications, we study the global error bounds for systems of linear and convex inequalities. The work of this author was partially supported by the National Natural Sciences Grant (No. 10471032) and the Excellent Young Teachers Program of MOE, P.R.C The authors thank professor K.F.Ng for his helpful discussion and the referee for their helpful suggestions on improving the first version of this paper     

Time-periodic Stokes equations with inhomogeneous Dirichlet boundary conditions in a half-space

The time-periodic Stokes problem in a half-space with fully inhomogeneous right-hand side is investigated. Maximal regularity in a time-periodic L^p setting is established. A method based on Fourier multipliers is employed that leads to a decomposition of the solution into a steady-state and a purely oscillatory part in order to identify the suitable function spaces.     

Regularization in Sobolev Spaces with Fractional Order

We study the minimization of a quadratic functional where the Tichonov regularization term is an H ^s -norm with a fractional s > 0. Moreover, pointwise bounds for the unknown solution are given. A multilevel approach as an equivalent norm concept is introduced. We show higher regularity of the solution of the variational inequality. This regularity is used to show the existence of regular Lagrange multipliers in function space. The theory is illustrated by two applications: a Dirichlet boundary control problem and a parameter identification problem.     

An interior point multiplicative method for optimization under positivity constraints

We analyze an algorithm for the problem minf(x) s.t.x 0 suggested, without convergence proof, by Eggermont. The iterative step is given by x _j ^k+1 =x _j ^k (1-_kf(x ^k)_j) with _k > 0 determined through a line search. This method can be seen as a natural extension of the steepest descent method for unconstrained optimization, and we establish convergence properties similar to those known for steepest descent, namely weak convergence to a KKT point for a generalf, weak convergence to a solution for convexf and full convergence to the solution for strictly convexf. Applying this method to a maximum likelihood estimation problem, we obtain an additively overrelaxed version of the EM Algorithm. We extend the full convergence results known for EM to this overrelaxed version by establishing local Fejér monotonicity to the solution set.Research for this paper was partially supported by CNPq grant No 301280/86.     

Maximal L p regularity for nonautonomous parabolic equations in extrapolation spaces1

This paper deals with a parabolic problem u′ (t)=A (t) u (t)+f (t), u (0)=x, on a Banach space X. We establish maximal L^p regularity, p ∈[1,+∞[, on a suitable extrapolation space of X. As a consequence we obtain weak solutions that have the same regularity of the mild solutions in the autonomous case. Dedicated to Giuseppe Da Prato on the occasion of his 70th birthday     

Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow*

This paper presents two fast cycle canceling algorithms for the submodular ow problem. The rst uses an assignment problem whose optimal solution identies most negative node-disjoint cycles in an auxiliary network. Canceling these cycles lexicographically makes it possible to obtain an optimal submodular ow in O(n ⁴ h log(nC)) time, which almost matches the current fastest weakly polynomial time for submodular flow (where n is the number of nodes, h is the time for computing an exchange capacity, and C is the maximum absolute value of arc costs). The second algorithm generalizes Goldbergs cycle canceling algorithm for min cost flow to submodular flow to also get a running time of O(n ⁴ h log(nC)).. We show how to modify these algorithms to make them strongly polynomial, with running times of O(n ⁶ h log n), which matches the fastest strongly polynomial time bound for submodular flow. We also show how to extend both algorithms to solve submodular flow with separable convex objectives. * An extended abstract of a preliminary version of part of this paper appeared in [22]. Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan. Research supported by an NSERC Operating Grant. Part of this research was done during a sabbatical leave at Cornell SORIE.§ Research supported in part by a Grant-in-Aid of the Ministry of Education, Science, Sports and Culture of Japan.     

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.     

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.     

Antiweb-wheel inequalities and their separation problems over the stable set polytopes

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of finding a maximum weight stable set is one of the most basic ℕℙ-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets. Since it is impossible (unless ℕℙ=coℕℙ) to obtain a “concise” characterization of STAB(G) as the solution set of a system of linear inequalities, it is a more realistic goal to find large classes of valid inequalities with the property that the corresponding separation problem (given a point x ^*, find, if possible, an inequality in the class that x ^* violates) is efficiently solvable.?Some known large classes of separable inequalities are the trivial, edge, cycle and wheel inequalities. In this paper, we give a polynomial time separation algorithm for the (t)-antiweb inequalities of Trotter. We then introduce an even larger class (in fact, a sequence of classes) of valid inequalities, called (t)-antiweb-s-wheel inequalities. This class is a common generalization of the (t)-antiweb inequalities and the wheel inequalities. We also give efficient separation algorithms for them. Received: June 2000 / Accepted: August 2001?Published online February 14, 2002     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

Asymptotic analysis of the exponential penalty trajectory in linear programming

We consider the linear program min{cx: Axb} and the associated exponential penalty functionf _r(x) = cx + rexp[(A _ix – b_i)/r]. Forr close to 0, the unconstrained minimizerx(r) off _r admits an asymptotic expansion of the formx(r) = x ^* + rd^* + (r) wherex ^* is a particular optimal solution of the linear program and the error term(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectory(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to : the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.Corresponding author. Both authors partially supported by FONDECYT.     

On the symmetry function of a convex set

We attempt a broad exploration of properties and connections between the symmetry function of a convex set S ${S \subset\mathbb{R}^n}We attempt a broad exploration of properties and connections between the symmetry function of a convex set S and other arenas of convexity including convex functions, convex geometry, probability theory on convex sets, and computational complexity. Given a point , let sym(x,S) denote the symmetry value of x in S: , which essentially measures how symmetric S is about the point x, and define x ^* is called a symmetry point of S if x ^* achieves the above maximum. The set S is a symmetric set if sym (S)=1. There are many important properties of symmetric convex sets; herein we explore how these properties extend as a function of sym (S) and/or sym (x,S). By accounting for the role of the symmetry function, we reduce the dependence of many mathematical results on the strong assumption that S is symmetric, and we are able to capture and otherwise quantify many of the ways that the symmetry function influences properties of convex sets and functions. The results in this paper include functional properties of sym (x,S), relations with several convex geometry quantities such as volume, distance, and cross-ratio distance, as well as set approximation results, including a refinement of the L?wner-John rounding theorems, and applications of symmetry to probability theory on convex sets. We provide a characterization of symmetry points x ^* for general convex sets. Finally, in the polyhedral case, we show how to efficiently compute sym(S) and a symmetry point x ^* using linear programming. The paper also contains discussions of open questions as well as unproved conjectures regarding the symmetry function and its connection to other areas of convexity theory. Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.     

Radial Fourier multipliers in high dimensions

Given a fixed p≠2, we prove a simple and effective characterization of all radial multipliers of FL^p( \mathbbR^d ) \mathcal{F}{L^p}\left( {{\mathbb{R}^d}} \right) , provided that the dimension d is sufficiently large. The method also yields new L ^q space-time regularity results for solutions of the wave equation in high dimensions.     

A globally and superlinearly convergent trust region method for LC 1 optimization problems

Abstract. A new trust region algorithm for solving convex LC1 optimization problem is present-ed. It is proved that the algorithm is globally convergent and the rate of convergence is superlin-ear under some reasonable assumptions.     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

An O(n 2) active set algorithm for the solution of a parametric quadratic program

In this paper, an O(n ²) active set method is presented for minimizing the parametric quadratic function (1/2)x′Dx-a′x + λmax(c - γ x,0) subject to l ⩽ x ⩽ b, for all nonnegative values of the parameter γ. Here, D is a positive diagonal n x n matrix, a and γ are arbitrary N-vectors, c is an arbitrary scalar, l and b are arbitrary n-vectors, such thatl ⩽ b. An extension of this algorithm is presented for minimizing the parametric function (1/2)x′Dx-a ^′ x + λ |γ′x - c| subject to l ⩽ x ⩽ b. It is also shown that these problems arise naturally in a tax programming problem. This revised version was published online in August 2006 with corrections to the Cover Date.     

Generalized K-T conditions and penalty functions for quasidifferentiable programming

In this paper,a quasidifferentiable programming problem with inequality constraintsis considered. First,a general form of optimality conditions for this problem is glven,which contains the results of Luderer,Kuntz and Scholtes. Next,a new generalized K-T condition is derived. The new optimality condition doesn‘t use Luderer‘s regularity assumption and ita Lagrangian multipliers don‘t depend on the particular elements in the superdifferentials of the object function and constraint functions, Finally,a penalty function for the prohlem is studied. Sufficient conditions of the penalty function attaining a global minimum are obtained.     

MAXIMUM CYCLE-MEANS OF WEIGHTED DIGRAPHS

Abstract. Computing the maximum cycle-mean of a weighted digraph is relevant to a number of applications, and combinatorial algorlthnls of complexity 0(n) are known.We present a new algorithm, with computational evidence to suggest an expected run-time growth rate below O(n^3）     

Metric regularity and subdifferential calculus in Banach spaces

In this paper we give verifiable conditions in terms of limiting Fréchet subdifferentials ensuring the metric regularity of a multivalued functionF(x)=–g(x)+D. We apply our results to the study of the limiting Fréchet subdifferential of a composite function defined on a Banach space.