Stability of the Feasible Set Mapping of Linear Systems with an Exact Constraint Set

This paper deals with the stability of the feasible set mapping of linear systems of an arbitrary number (possibly infinite) of equations and inequalities such that the variable x ranges on a certain fixed constraint set X?? ⁿ (X could represent the solution set of a given constraint system, e.g., the positive cone of ? ⁿ in the case of sign constraints). More in detail, the paper provides necessary as well as sufficient conditions for the lower and upper semicontinuity (in Berge sense), and the closedness, of the set-valued mapping which associates, with any admissible perturbation of the given (nominal) system its feasible set. The parameter space is formed by all the systems having the same structure (i.e., the same number of variables, equations and inequalities) as the nominal one, and the perturbations are measured by means of the pseudometric of the uniform convergence.     

Optimal multiway split trees

A class of multiway split trees is defined. Given a set of n weighted keys and a node capacity m, an algorithm is described for constructing a multiway split tree with minimum access cost. The algorithm runs in time O(mn⁴) and requires O(mn³) storage locations. A further refinement of the algorithm enables the factor m in the above costs to be reduced to log m.     

A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids

We call a set system of feasible sets hereditary if every (k+1)-element feasible set contains a k-element feasible subset (k≥0). We characterize hereditary set systems for which a modified greedy algorithm is optimal. This will involve an algorithmic characterization of strong map relations between matroids. The set systems that come up are special greedoids which were introduced by B. Korte and L. Lovász [8–10].     

Robust H∞ nonlinear modeling and control via uncertain fuzzy systems

In theory, an Algebraic Riccati Equation (ARE) scheme applicable to robust H^∞ quadratic stabilization problems of a class of uncertain fuzzy systems representing a nonlinear control system is investigated. It is proved that existence of a set of solvable AREs suffices to guarantee the quadratic stabilization of an uncertain fuzzy system while satisfying H^∞-norm bound constraint. It is also shown that a stabilizing control law is reminiscent of an optimal control law found in linear quadratic regulator, and a linear control law can be immediately discerned from the stabilizing one. In practice, the minimal solution to a set of parameter dependent AREs is somewhat stringent and, instead, a linear matrix inequalities formulation is suggested to search for a feasible solution to the associated AREs. The proposed method is compared with the existing fuzzy literature from various aspects.     

Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: properties and algorithms

The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation (LR_u) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0–1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicity enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order O(n³).     

On Metric Regularity and the Boundary of the Feasible Set in Linear Optimization

This paper deals with semi-infinite linear inequality systems in ? ⁿ and studies the stability of the boundary of their feasible sets. We analyze the equivalence between the metric regularity of the inverse of the boundary set mapping, $\mathcal{N}$ , and the stability of the feasible set mapping in the sense of the maintenance of the consistency. In doing this we provide operational formulae for distances from points to some useful sets. We also include relationships between the regularity moduli corresponding to the mappings $\mathcal{N}$ and the inverse, $\mathcal{M}$ , of the feasible set mapping, and prove their equality for finite systems and some special cases in the semi-infinite framework. Moreover, we provide conditions to assure that the metric regularity of $\mathcal{N}$ is equivalent to the lower semi-continuity of the boundary set mapping, which is important because the latter property has many characterizations. Since the boundary of a feasible set may not be convex, we cannot make use of the general theory for mappings with convex graph, as for example, the Robinson–Ursescu theorem.     

Inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow x⁰, an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x⁰ form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n · m²).     

Primal-dual interior-point methods for PDE-constrained optimization

This paper provides a detailed analysis of a primal-dual interior-point method for PDE-constrained optimization. Considered are optimal control problems with control constraints in L ^p . It is shown that the developed primal-dual interior-point method converges globally and locally superlinearly. Not only the easier L ^∞-setting is analyzed, but also a more involved L ^q -analysis, q < ∞, is presented. In L ^∞, the set of feasible controls contains interior points and the Fréchet differentiability of the perturbed optimality system can be shown. In the L ^q -setting, which is highly relevant for PDE-constrained optimization, these nice properties are no longer available. Nevertheless, a convergence analysis is developed using refined techniques. In parti- cular, two-norm techniques and a smoothing step are required. The L ^q -analysis with smoothing step yields global linear and local superlinear convergence, whereas the L ^∞-analysis without smoothing step yields only global linear convergence.     

A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.     

Remote Sensing via ℓ 1-Minimization

We consider the problem of detecting the locations of targets in the far field by sending probing signals from an antenna array and recording the reflected echoes. Drawing on key concepts from the area of compressive sensing, we use an ? ₁-based regularization approach to solve this, generally ill-posed, inverse scattering problem. As is common in compressive sensing, we exploit randomness, which in this context comes from choosing the antenna locations at random. With n antennas we obtain n ² measurements of a vector $x \in\mathbb{C}^{N}$ representing the target locations and reflectivities on a discretized grid. It is common to assume that the scene x is sparse due to a limited number of targets. Under a natural condition on the mesh size of the grid, we show that an s-sparse scene can be recovered via ? ₁-minimization with high probability if n ²≥Cslog²(N). The reconstruction is stable under noise and when passing from sparse to approximately sparse vectors. Our theoretical findings are confirmed by numerical simulations.     

Splines with maximal zero sets

Consider a spline s(x) of degree n with L knots of specified multiplicities R₁, …, R_L, which satisfies r sign consistent mixed boundary conditions in addition to s⁽ⁿ⁾(a) = 1. Such a spline has at most n + 1 ?r + ∑_{j = 1}^LR_j zeros in (a, b) which fulfill an interlacing condition with the knots if s(x) ? = 0 everywhere. Conversely, given a set of n ?r + ∑_{j = 1}^LR_j zeros then for any choice η₁ < ··· < η_L of the knot locations which fulfills the interlacing condition with the zeros, the unique spline s(x) possessing these knots and zeros and satisfying the boundary conditions is such that s⁽ⁿ⁾(x) vanishes nowhere and changes sign at η_j if and only if R_j is odd. Moreover there exists a choice of the knot locations, not necessarily unique, which makes $\text{¦s}{}^{\mathrm{(n)}}\text{(x)¦ ≡ 1}$. In particular, this establishes the existence of monosplines and perfect splines with knots of given multiplicities, satisfying the mixed boundary conditions and possessing a prescribed maximal zero set. An application is given to double-precision quadrature formulas with mixed boundary terms and a certain polynomial extremal problem connected with it.     

An active set feasible method for large-scale minimization problems with bound constraints

We are concerned with the solution of the bound constrained minimization problem {minf(x), l??x??u}. For the solution of this problem we propose an active set method that combines ideas from projected and nonmonotone Newton-type methods. It is based on an iteration of the form x ^k+1=[x ^k +?? ^k d ^k ]^?, where ?? ^k is the steplength, d ^k is the search direction and [?]^? is the projection operator on the set [l,u]. At each iteration a new formula to estimate the active set is first employed. Then the components $d_{N}^{k}$ of d ^k corresponding to the free variables are determined by a truncated Newton method, and the components $d_{A}^{k}$ of d ^k corresponding to the active variables are computed by a Barzilai-Borwein gradient method. The steplength ?? ^k is computed by an adaptation of the nonmonotone stabilization technique proposed in Grippo et?al. (Numer. Math. 59:779?C805, 1991). The method is a feasible one, since it maintains feasibility of the iterates x ^k , and is well suited for large-scale problems, since it uses matrix-vector products only in the truncated Newton method for computing $d_{N}^{k}$ . We prove the convergence of the method, with superlinear rate under usual additional assumptions. An extensive numerical experimentation performed on an algorithmic implementation shows that the algorithm compares favorably with other widely used codes for bound constrained problems.     

Properties of P-sets and trapped compact convex sets

New properties of P-sets, which constitute a large class of convex compact sets in ? ⁿ that contains all convex polyhedra and strictly convex compact sets, are obtained. It is shown that the intersection of a P-set with an affine subspace is continuous in the Hausdorff metric. In this theorem, no assumption of interior nonemptiness is made, unlike in other known intersection continuity theorems for set-valued maps. It is also shown that if the graph of a set-valued map is a P-set, then this map is continuous on its entire effective set rather than only on the interior of this set. Properties of the so-called trapped sets are also studied; well-known Jung’s theorem on the existence of a minimal ball containing a given compact set in ? ⁿ is generalized. As is known, any compact set contains n + 1 (or fewer) points such that any translation by a nonzero vector takes at least one of them outside the minimal ball. This means that any compact set is trapped in the minimal ball. Compact sets trapped in any convex compact sets, rather than only in norm bodies, are considered. It is shown that, for any compact set A trapped in a P-set M ? ? ⁿ , there exists a set A ⁰ ? A trapped in M and containing at most 2n elements. An example of a convex compact set M ? ? ⁿ for which such a finite set A ⁰ ? A does not exist is given.     

Hybrid approaches to attribute reduction based on indiscernibility and discernibility relation

Attribute reduction is one of the key issues in rough set theory. Many heuristic attribute reduction algorithms such as positive-region reduction, information entropy reduction and discernibility matrix reduction have been proposed. However, these methods are usually computationally time-consuming for large data. Moreover, a single attribute significance measure is not good for more attributes with the same greatest value. To overcome these shortcomings, we first introduce a counting sort algorithm with time complexity O(∣C∣ ∣U∣) for dealing with redundant and inconsistent data in a decision table and computing positive regions and core attributes (∣C∣ and ∣U∣ denote the cardinalities of condition attributes and objects set, respectively). Then, hybrid attribute measures are constructed which reflect the significance of an attribute in positive regions and boundary regions. Finally, hybrid approaches to attribute reduction based on indiscernibility and discernibility relation are proposed with time complexity no more than max(O(∣C∣²∣U/C∣), O(∣C∣∣U∣)), in which ∣U/C∣ denotes the cardinality of the equivalence classes set U/C. The experimental results show that these proposed hybrid algorithms are effective and feasible for large data.     

A tutorial proof that extreme points are basic feasible solutions

Given a set of m linear equations in n unknowns with the requirement that the solution space be nonnegative, a simple, heuristic proof is offered which shows that the extreme points of the set of feasible solutions are also basic feasible solutions. This proof can be used in many text treatments of Linear Programming which omit the proof on the grounds that it is too difficult to prove.     

Bilevel optimization: on the structure of the feasible set

We consider bilevel optimization from the optimistic point of view. Let the pair (x, y) denote the variables. The main difficulty in studying such problems lies in the fact that the lower level contains a global constraint. In fact, a point (x, y) is feasible if y solves a parametric optimization problem L(x). In this paper we restrict ourselves to the special case that the variable x is one-dimensional. We describe the generic structure of the feasible set M. Moreover, we discuss local reductions of the bilevel problem as well as corresponding optimality criteria. Finally, we point out typical problems that appear when trying to extend the ideas to higher dimensional x-dimensions. This will clarify the high intrinsic complexity of the general generic structure of the feasible set M and corresponding optimality conditions for the bilevel problem U.     

DIFFEOMORPHISMS WITH VARIOUS C1 STABLE PROPERTIES

Let M be a smooth compact manifold and Λ be a compact invariant set.In this article,we prove that,for every robustly transitive set Λ,f|Λ satisfies a C1-genericstable shadowable property (resp.,C1-gene...     

Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

Two spectral characterizations of regular, bipartite graphs with five eigenvalues

Graphs with a few distinct eigenvalues usually possess an interesting combinatorial structure. We show that regular, bipartite graphs with at most six distinct eigenvalues have the property that each vertex belongs to the constant number of quadrangles. This enables to determine, from the spectrum alone, the feasible families of numbers of common neighbors for each vertex with other vertices in its part. For particular spectra, such as [6,2⁹,0⁶,-2⁹,-6] (where exponents denote eigenvalue multiplicities), there is a unique such family, which makes it possible to characterize all graphs with this spectrum.Using this lemma we also to show that, for r?2, a graph has spectrum if and only if it is a graph of a 1-resolvable transversal design TD(r,r), i.e., if it corresponds to the complete set of mutually orthogonal Latin squares of size r in a well-defined manner.