Constructing uniform designs: A heuristic integer programming method

In this paper, the wrap-around _L2$L_2$-discrepancy (WD) of asymmetrical design is represented as a quadratic form, thus the problem of constructing a uniform design becomes a quadratic integer programming problem. By the theory of optimization, some theoretic properties are obtained. Algorithms for constructing uniform designs are then studied. When the number of runs n$n$ is smaller than the number of all level-combinations m$m$, the construction problem can be transferred to a zero–one quadratic integer programming problem, and an efficient algorithm based on the simulated annealing is proposed. When n≥m$n\ge m$, another algorithm is proposed. Empirical study shows that when n$n$ is large, the proposed algorithms can generate designs with lower WD compared to many existing methods. Moreover, these algorithms are suitable for constructing both symmetrical and asymmetrical designs.     

A distance-based point-reassignment heuristic for the k-hyperplane clustering problem

We consider the k-Hyperplane Clustering problem where, given a set of m   points in Rⁿ${\mathbb{R}}^n$, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many “critical” points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%.     

A Simplicial Branch-and-Bound Method for Solving Nonconvex All-Quadratic Programs

In this paper we present an algorithm for solving nonconvex quadratically constrained quadratic programs (all-quadratic programs). The method is based on a simplicial branch-and-bound scheme involving mainly linear programming subproblems. Under the assumption that a feasible point of the all-quadratic program is known, the algorithm guarantees an -approximate optimal solution in a finite number of iterations. Computational experiments with an implementation of the procedure are reported on randomly generated test problems. The presented algorithm often outperforms a comparable rectangular branch-and-bound method.     

Asymptotic resurgences for ideals of positive dimensional subschemes of projective space

Recent work of Ein–Lazarsfeld–Smith and Hochster–Huneke raised the containment problem of determining which symbolic powers of an ideal are contained in a given ordinary power of the ideal. Bocci–Harbourne defined a quantity called the resurgence to address this problem for homogeneous ideals in polynomial rings, with a focus on zero-dimensional subschemes of projective space. Here we take the first steps toward extending this work to higher dimensional subschemes. We introduce new asymptotic versions of the resurgence and obtain upper and lower bounds on them for ideals I$I$ of smooth subschemes, generalizing what is done in Bocci and Harbourne (2010)  [5]. We apply these bounds to ideals of unions of general lines in P^N${\mathbb{P}}^N$. We also pose a Nagata type conjecture for symbolic powers of ideals of lines in P³${\mathbb{P}}^3$.     

Fixed points of Mizoguchi–Takahashi contraction on a metric space with a graph and applications

In this paper we extend Mizoguchi–Takahashi's fixed point theorem for multi-valued mappings on a metric space endowed with a graph. As an application, we establish a fixed point theorem on an ε  -chainable metric space for mappings satisfying Mizoguchi–Takahashi contractive condition uniformly locally. Also, we establish a result on the convergence of successive approximations for certain operators (not necessarily linear) on a Banach space as another application. Consequently, this result yields the Kelisky–Rivlin theorem on iterates of the Bernstein operators on the space C[0,1]$C[0,1]$ and also enables us study the asymptotic behaviour of iterates of some nonlinear Bernstein type operators on C[0,1]$C[0,1]$.     

Reformulation of mathematical programming problems as linear complementarity problems and investigation of their solution methods

A family of complementarity problems is defined as extensions of the well-known linear complementarity problem (LCP). These are:

Convergence of generalized AOR iterative method for linear systems with strictly diagonally dominant matrices

In this paper, some improvements on Darvishi and Hessari [On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Appl. Math. Comput. 176 (2006) 128–133] are presented for bounds of the spectral radius of _lω,r$l_{\omega ,r}$, which is the iterative matrix of the generalized AOR (GAOR) method. Subsequently, some new sufficient conditions for convergence of GAOR method will be given, which improve some results of Darvishi and Hessari [On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Appl. Math. Comput. 176 (2006) 128–133].     

A note on constrained degree reduction of polynomials in Bernstein–Bézier form over simplex domain

In the paper [H.S. Kim, Y.J. Ahn, Constrained degree reduction of polynomials in Bernstein–Bézier form over simplex domain, J. Comput. Appl. Math. 216 (2008) 14–19], Kim and Ahn proved that the best constrained degree reduction of a polynomial over d$d$-dimensional simplex domain in _L2$L_2$-norm equals the best approximation of weighted Euclidean norm of the Bernstein–Bézier coefficients of the given polynomial. In this paper, we presented a counterexample to show that the approximating polynomial of lower degree to a polynomial is virtually non-existent when d≥2$d\ge 2$. Furthermore, we provide an assumption to guarantee the existence of solution for the constrained degree reduction.     

Branch-and-reduce algorithm for convex programs with additional multiplicative constraints

This article presents a branch-and-reduce algorithm for globally solving for the first time a convex minimization problem (P) with p?1$p?1$ additional multiplicative constraints. In each of these p   additional constraints, the product of two convex functions is constrained to be less than or equal to a positive number. The algorithm works by globally solving a 2p$2p$-dimensional master problem (MP) equivalent to problem (P). During a typical stage k of the algorithm, a point is found that minimizes the objective function of problem (MP) over a nonconvex set F^k$F^k$ that contains the portion of the boundary of the feasible region of the problem where a global optimal solution lies. If this point is feasible in problem (MP), the algorithm terminates. Otherwise, the algorithm continues by branching and creating a new, reduced nonconvex set F^k+1$F^{k+1}$ that is a strict subset of F^k$F^k$. To implement the algorithm, all that is required is the ability to solve standard convex programming problems and to implement simple algebraic steps. Convergence properties of the algorithm are given, and results of some computational experiments are reported.     

Canonical Duality Theory and Solutions to Constrained Nonconvex Quadratic Programming

This paper presents a perfect duality theory and a complete set of solutions to nonconvex quadratic programming problems subjected to inequality constraints. By use of the canonical dual transformation developed recently, a canonical dual problem is formulated, which is perfectly dual to the primal problem in the sense that they have the same set of KKT points. It is proved that the KKT points depend on the index of the Hessian matrix of the total cost function. The global and local extrema of the nonconvex quadratic function can be identified by the triality theory [11]. Results show that if the global extrema of the nonconvex quadratic function are located on the boundary of the primal feasible space, the dual solutions should be interior points of the dual feasible set, which can be solved by deterministic methods. Certain nonconvex quadratic programming problems in {\open {R}}^{n} can be converted into a dual problem with only one variable. It turns out that a complete set of solutions for quadratic programming over a sphere is obtained as a by-product. Several examples are illustrated.     

A feasible SQP-GS algorithm for nonconvex, nonsmooth constrained optimization

The gradient sampling (GS) algorithm for minimizing a nonconvex, nonsmooth function was proposed by Burke et al. (SIAM J Optim 15:751–779, 2005), whose most interesting feature is the use of randomly sampled gradients instead of subgradients. In this paper, combining the GS technique with the sequential quadratic programming (SQP) method, we present a feasible SQP-GS algorithm that extends the GS algorithm to nonconvex, nonsmooth constrained optimization. The proposed algorithm generates a sequence of feasible iterates, and guarantees that the objective function is monotonically decreasing. Global convergence is proved in the sense that, with probability one, every cluster point of the iterative sequence is stationary for the improvement function. Finally, some preliminary numerical results show that the proposed algorithm is effective.     

Extendability of quadratic modules over a polynomial extension of an equicharacteristic regular local ring

We prove that a quadratic A[T]$A[T]$-module Q   with Witt index (Q/TQ)?d$(Q/TQ)?d$, where d is the dimension of the equicharacteristic regular local ring A, is extended from A. This improves a theorem of the second named author who showed it when A is the local ring at a smooth point of an affine variety over an infinite field. To establish our result, we need to establish a local–global principle (of Quillen) for the Dickson–Siegel–Eichler–Roy (DSER) elementary orthogonal transformations.     

The preconditioned Gauss–Seidel method faster than the SOR method

In recent years, a number of preconditioners have been applied to linear systems [A.D. Gunawardena, S.K. Jain, L. Snyder, Modified iterative methods for consistent linear systems, Linear Algebra Appl. 154–156 (1991) 123–143; T. Kohno, H. Kotakemori, H. Niki, M. Usui, Improving modified Gauss–Seidel method for Z-matrices, Linear Algebra Appl. 267 (1997) 113–123; H. Kotakemori, K. Harada, M. Morimoto, H. Niki, A comparison theorem for the iterative method with the preconditioner (I+_Smax)$(I+S_{\mathit{max}})$, J. Comput. Appl. Math. 145 (2002) 373–378; H. Kotakemori, H. Niki, N. Okamoto, Accelerated iteration method for Z$Z$-matrices, J. Comput. Appl. Math. 75 (1996) 87–97; M. Usui, H. Niki, T.Kohno, Adaptive Gauss-Seidel method for linear systems, Internat. J. Comput. Math. 51(1994)119–125 [10]]. Since these preconditioners are constructed from the elements of the upper triangular part of the coefficient matrix, the preconditioning effect is not observed on the n$n$th row of matrix A. In the present paper, in order to deal with this drawback, we propose a new preconditioner. In addition, the convergence and comparison theorems of the proposed method are established. Simple numerical examples are also given, and we show that the convergence rate of the proposed method is better than that of the optimum SOR.     

Minimax inequalities and fixed points of expansive set-valued mappings with noncompact and nonconvex domains and ranges in topological spaces

Some minimax inequalities involving two bifunctions with noncompact and nonconvex domains are first proved in finite continuous topological spaces (in short, FC$FC$-spaces) without convexity structure. As applications some new Fan–Browder type fixed point theorems for expansive set-valued maps with noncompact and nonconvex domains and ranges are obtained in general topological spaces. These results generalize some known results in the recent literature.     

Stochastic approximations of constrained discounted Markov decision processes

We consider a discrete-time constrained Markov decision process under the discounted cost optimality criterion. The state and action spaces are assumed to be Borel spaces, while the cost and constraint functions might be unbounded. We are interested in approximating numerically the optimal discounted constrained cost. To this end, we suppose that the transition kernel of the Markov decision process is absolutely continuous with respect to some probability measure μ  . Then, by solving the linear programming formulation of a constrained control problem related to the empirical probability measure _μn${\mu }_n$ of μ, we obtain the corresponding approximation of the optimal constrained cost. We derive a concentration inequality which gives bounds on the probability that the estimation error is larger than some given constant. This bound is shown to decrease exponentially in n. Our theoretical results are illustrated with a numerical application based on a stochastic version of the Beverton–Holt population model.     

On Uniformly Finitely Extensible Banach spaces

We continue the study of Uniformly Finitely Extensible Banach spaces (in short, UFO) initiated in Moreno and Plichko (2009) [39] and Castillo and Plichko (2010) [18]. We show that they have the Uniform Approximation Property of Pe?czyński and Rosenthal and are compactly extensible. We will also consider their connection with the automorphic space problem of Lindenstrauss and Rosenthal – do there exist automorphic spaces other than _c0(I)$c_0(I)$ and _?2(I)${?}_2(I)$? – showing that a space all whose subspaces are UFO must be automorphic when it is Hereditarily Indecomposable (HI), and a Hilbert space when it is either locally minimal or isomorphic to its square. We will finally show that most HI – among them, the super-reflexive HI space constructed by Ferenczi – and asymptotically _?2${?}_2$ spaces in the literature cannot be automorphic.