An optimum multivariate stratified double sampling design in presence of non-response

In stratified sampling when strata weights are unknown double sampling technique may be used to estimate them. At first a large simple random sample from the population without considering the stratification is drawn and sampled units belonging to each stratum are recorded to estimate the unknown strata weights. A stratified random sample is then obtained comprising of simple random subsamples out of the previously selected units of the strata. If the problem of non-response is there, then these subsamples may be divided into classes of respondents and non-respondents. A second subsample is then drawn out of non-respondents and an attempt is made to obtain the information. This procedure is called Double Sampling for Stratification (DSS). Okafor (Aligarh J Statist 14:13–23, 1994) derived DSS estimators based on the subsampling of non-respondents. Najmussehar and Bari (Aligarh J Statist 22:27–41, 2002) discussed an optimum double sampling design by formulating the problem as a mathematical programming problem and used the dynamic programming technique to solve it. In the present paper a multivariate stratified population is considered with unknown strata weights and an optimum sampling design is proposed in the presence of non-response to estimate the unknown population means using DSS strategy. The problem turns out to be a multiobjective integer nonlinear programming problem. A solution procedure is developed using Goal Programming technique. A numerical example is presented to illustrate the computational details.     

Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in Bailey et al. (Am. Math. Mon. 115:383–404, 2008; J. Agron. Crop Sci. 165:121–130, 1990), Morgan (Latin squares and related experimental designs. Wiley, New York, 2008) and Vaughan (Electron. J. Comb. 16, 2009). On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m≠n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables—variables with the same value in all the solutions of an instance—and hardness of GSP.     

Computing multiple-output regression quantile regions from projection quantiles

In the multiple-output regression context, Hallin et al. (Ann Statist 38:635–669, 2010) introduced a powerful data-analytical tool based on regression quantile regions. However, the computation of these regions, that are obtained by considering in all directions an original concept of directional regression quantiles, is a very challenging problem. Paindaveine and Šiman (Comput Stat Data Anal 2011b) described a first elegant solution relying on linear programming techniques. The present paper provides another solution based on the fact that the quantile regions can also be computed from a competing concept of projection regression quantiles, elaborated in Kong and Mizera (Quantile tomography: using quantiles with multivariate data 2008) and Paindaveine and Šiman (J Multivar Anal 2011a). As a by-product, this alternative solution further provides various characteristics useful for statistical inference. We describe in detail the algorithm solving the parametric programming problem involved, and illustrate the resulting procedure on simulated data. We show through simulations that the Matlab implementation of the algorithm proposed in this paper is faster than that from Paindaveine and Šiman (Comput Stat Data Anal 2011b) in various cases.     

On the Shape Sensitivity of the First Dirichlet Eigenvalue for Two-Phase Problems

We consider a two-phase problem in thermal conductivity: inclusions filled with a material of conductivity σ ₁ are layered in a body of conductivity σ ₂. We address the shape sensitivity of the first eigenvalue associated with Dirichlet boundary conditions when both the boundaries of the inclusions and the body can be modified. We prove a differentiability result and provide the expressions of the first and second order derivatives. We apply the results to the optimal design of an insulated body. We prove the stability of the optimal design thanks to a second order analysis. We also continue the study of an extremal eigenvalue problem for a two-phase conductor in a ball initiated by Conca et al. (Appl. Math. Optim. 60(2):173–184, 2009) and pursued in Conca et al. (CANUM 2008, ESAIM Proc., vol. 27, pp.  311–321, EDP Sci., Les Ulis, 2009).     

A new fictitious domain method in shape optimization

The present paper is concerned with investigating the capability of the smoothness preserving fictitious domain method from Mommer (IMA J. Numer. Anal. 26:503–524, 2006) to shape optimization problems. We consider the problem of maximizing the Dirichlet energy functional in the class of all simply connected domains with fixed volume, where the state equation involves an elliptic second order differential operator with non-constant coefficients. Numerical experiments in two dimensions validate that we arrive at a fast and robust algorithm for the solution of the considered class of problems. The proposed method can be applied to three dimensional shape optimization problems.     

Bézier variant of Baskakov-Beta-Stancu operators

In the year 1994, Gupta (Approx Theory Appl (N.S.) 10(3):74–78, 1994) introduced the integral modification of well known Baskakov operators with weights of Beta basis functions and obtained better approximation over the usual Baskakov Durrmeyer operators. The rate of convergence for Bézier variant of these operators for functions of bounded variations were discussed in Gupta (Int J Math Math Sci 32(8):471–479, 2002). The present paper is the extension of the previous work, here we consider the Bézier variant of Baskakov-Beta-Stancu operators. We estimate the rate of convergence of these operators for the bounded functions. In the end of the paper we suggest an open problem.     

Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization

The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.     

Axioms for Sequential Convergence

It is of general knowledge that those (ultra)filter convergence relations coming from a topology can be characterized by two natural axioms. However, the situation changes considerable when moving to sequential spaces. In case of unique limit points Kisyński (Colloq Math 7:205–211, 1959/1960) obtained a result for sequential convergence similar to the one for ultrafilters, but the general case seems more difficult to deal with. Finally, the problem was solved by Koutnik (Closure and topological sequential convergence. In: Convergence Structures 1984 (Bechyně, 1984). Math. Res., vol. 24, pp. 199–204. Akademie-Verlag, Berlin, 1985). In this paper we present an alternative approach to this problem. Our goal is to find a characterization more closely related to the case of ultrafilter convergence. We extend then the result to characterize sequential convergence relations corresponding to Fréchet topologies, as well to those corresponding to pretopological spaces.      

Random Skew Plane Partitions with a Piecewise Periodic Back Wall

Random skew plane partitions of large size distributed according to an appropriately scaled Schur process develop limit shapes. In the present work, we consider the limit of large random skew plane partitions where the inner boundary approaches a piecewise linear curve with non-lattice slopes, describing the limit shape and the local fluctuations in various regions. This analysis is fairly similar to that in Okounkov and Reshetikhin (Commun Math Phys 269:571–609, 2007), but we do find some new behavior. For instance, the boundary of the limit shape is now a single smooth (not algebraic) curve, whereas the boundary in Okounkov and Reshetikhin (Commun Math Phys 269:571–609, 2007) is singular. We also observe the bead process introduced in Boutillier (Ann Probab 37(1):107–142, 2009) appearing in the asymptotics at the top of the limit shape.     

Implicit Iteration Scheme with Perturbed Mapping for Equilibrium Problems and Fixed Point Problems of Finitely Many Nonexpansive Mappings

We introduce an implicit iteration scheme with a perturbed mapping for finding a common element of the set of solutions of an equilibrium problem and the set of common fixed points of finitely many nonexpansive mappings in a Hilbert space. Then, we establish some convergence theorems for this implicit iteration scheme which are connected with results by Xu and Ori (Numer. Funct. Analysis Optim. 22:767–772, 2001), Zeng and Yao (Nonlinear Analysis, Theory, Methods Appl. 64:2507–2515, 2006) and Takahashi and Takahashi (J. Math. Analysis Appl. 331:506–515, 2007). In particular, necessary and sufficient conditions for strong convergence of this implicit iteration scheme are obtained. In this research, the first author was partially supported by the National Science Foundation China (10771141), Ph.D. Program Foundation of Ministry of Education of China (20070270004), and Science and Technology Commision of Shanghai Municipality Grant (075105118).     

Fully computable robust a posteriori error bounds for singularly perturbed reaction–diffusion problems

A procedure for the construction of robust, upper bounds for the error in the finite element approximation of singularly perturbed reaction–diffusion problems was presented in Ainsworth and Babuška (SIAM J Numer Anal 36(2):331–353, 1999) which entailed the solution of an infinite dimensional local boundary value problem. It is not possible to solve this problem exactly and this fact was recognised in the above work where it was indicated that the limitation would be addressed in a subsequent article. We view the present work as fulfilling that promise and as completing the investigation begun in Ainsworth and Babuška (SIAM J Numer Anal 36(2):331–353, 1999) by removing the obligation to solve a local problem exactly. The resulting new estimator is indeed fully computable and the first to provide fully computable, robust upper bounds in the setting of singularly perturbed problems discretised by the finite element method.     

Shooting methods for a PT-symmetric periodic eigenvalue problem

We present a rigorous analysis of the performance of some one-step discretization schemes for a class of PT-symmetric singular boundary eigenvalue problem which encompasses a number of different problems whose investigation has been inspired by the 2003 article of Benilov et al. (J Fluid Mech 497:201–224, 2003). These discretization schemes are analyzed as initial value problems rather than as discrete boundary problems, since this is the setting which ties in most naturally with the formulation of the problem which one is forced to adopt due to the presence of an interior singularity. We also devise and analyze a variable step scheme for dealing with the singular points. Numerical results show better agreement between our results and those obtained from small-ϵ asymptotics than has been shown in results presented hitherto.     

Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

New approach for the nonlinear programming with transient stability constraints arising from power systems

This paper presents a new approach for solving a class of complicated nonlinear programming problems arises from optimal power flow with transient stability constraints (denoted by OTS) in power systems. By using a functional transformation technology proposed in Chen et al. (IEEE Trans. Circuits Syst. I Fundam. Theory Appl. 48:327–339, [2001]), the OTS problem is transformed to a semi-infinite programming (SIP). Then based on the KKT (Karush-Kuhn-Tucker) system of the reformulated SIP problem and the finite approximation technology, an iterative method is presented, which develops Wu-Li-Qi-Zhou’ (Optim. Methods Softw. 20:629–643, [2005]) method. In order to save the computing cost, some typical computing technologies, such as active set strategy, quasi-Newton method for the subproblems coming from the finite approximation model, are addressed. The global convergence of the proposed algorithm is established. Numerical examples from power systems are tested. The computing results show the efficiency of the new approach.     

The impact of sampling methods on bias and variance in stochastic linear programs

Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1–19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely to reduce bias.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

Well-posedness for a mean field model of Ginzburg–Landau vortices with opposite degrees

In this paper we analyze the hydrodynamic equations for Ginzburg–Landau vortices as derived by E (Phys. Rev. B. 50(3):1126–1135, 1994). In particular, we are interested in the mean field model describing the evolution of two patches of vortices with equal and opposite degrees. Many results are already available for the case of a single density of vortices with uniform degree. This model does not take into account the vortex annihilation, hence it can also be seen as a particular instance of the signed measures system obtained in Ambrosio et al. (Ann. Inst. H. Poincaré Anal. Non Linéaire 28(2):217–246, 2011) and related to the Chapman et al. (Eur. J. Appl. Math. 7(2):97–111, 1996) formulation. We establish global existence of L ^p solutions, exploiting some optimal transport techniques introduced in this context in Ambrosio and Serfaty (Commun. Pure Appl. Math. LXI(11):1495–1539, 2008). We prove uniqueness for L ^∞ solutions, as expected by analogy with the incompressible Euler equations in fluidodynamics. We also consider the corresponding Dirichlet problem in a bounded domain. Moreover, we show some simple examples of 1-dimensional dynamic.     

On integrability in elementary functions of certain classes of nonconservative dynamical systems

The results of the presented work are due to the study of the applied problem of the rigid body motion in a resisting medium; see [210, 211], where complete lists of transcendental first integrals expressed through a finite combination of elementary functions were obtained. This circumstance allowed the author to perform a complete analysis of all phase trajectories and highlight those properties of them which exhibit the roughness and preserve for systems of a more general form. The complete integrability of those systems is related to symmetries of a latent type. Therefore, it is of interest to study sufficiently wide classes of dynamical systems having analogous latent symmetries. As is known, the concept of integrability is sufficiently broad and undeterminate in general. In its construction, it is necessary to take into account in what sense it is understood (it is meant that a certain criterion according to which one makes a conclusion that the structure of trajectories of the dynamical system considered is especially “attractive and simple”), in which function classes the first integrals are sought for, etc. (see also [1, 4, 14, 17, 20–22, 35, 40–42, 47, 83–85, 117, 120]).     

The Inverse Commutant Lifting Problem. I: Coordinate-Free Formalism

It is known that the set of all solutions of a commutant lifting and other interpolation problems admits a Redheffer linear-fractional parametrization. The method of unitary coupling identifies solutions of the lifting problem with minimal unitary extensions of a partially defined isometry constructed explicitly from the problem data. A special role is played by a particular unitary extension, called the central or universal unitary extension. The coefficient matrix for the Redheffer linear-fractional map has a simple expression in terms of the universal unitary extension. The universal unitary extension can be seen as a unitary coupling of four unitary operators (two bilateral shift operators together with two unitary operators coming from the problem data) which has special geometric structure. We use this special geometric structure to obtain an inverse theorem (Theorem 8.4) which characterizes the coefficient matrices for a Redheffer linear-fractional map arising in this way from a lifting problem. The main tool is the formalism of unitary scattering systems developed in Boiko et al. (Operator theory, system theory and related topics (Beer-Sheva/Rehovot 1997), pp. 89–138, 2001) and Kheifets (Interpolation theory, systems theory and related topics, pp. 287–317, 2002)