A primal-dual homotopy algorithm for $$\ell _{1}$$-minimization with $$\ell _{\infty }$$ℓ∞-constraints

In this paper we propose a primal-dual homotopy method for \(\ell _1\)-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.     

A constrained nonlinear 0–1 program for data allocation

This paper analyzes the problem of allocating copies of relations from a global database to the sites of a geographically distributed communication network. The objective of the allocation is to minimize the total cost due to transmissions generated by queries from the various sites, including queries that access multiple relations. This allocation problem is modeled as a constrained nonlinear 0–1 subproblems generated during subgradient optimization are solved as optimization. Some of the unconstrained quadratic 0–1 subproblems generated during subgradient optimization are solved as maximum flow problems, while the others require implicit enumeration, depending on the nature of the objective function coefficients of the subproblems. Our solution approach is tested extensively on data allocation problems with as many as 100 sites and 20 relations. On a set of randomly generated test problems our approach was close to two orders of magnitude faster than the general purpose integer programming code OSL.     

On the convergence of an inexact Gauss–Newton trust-region method for nonlinear least-squares problems with simple bounds

We introduce an inexact Gauss–Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. Some numerical illustration is also presented.     

The convergence of the modified Gauss–Seidel methods for consistent linear systems

In this paper we present a convergence analysis for the modified Gauss–Seidel methods given in Gunawardena et al. (Linear Algebra Appl. 154–156 (1991) 125) and Kohno et al. (Linear Algebra Appl. 267 (1997) 113) for consistent linear systems. We prove that the modified Gauss–Seidel method converges for some values of the parameters in the preconditioned matrix.     

A Lagrange–Newton algorithm for sparse nonlinear programming

Mathematical Programming - The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning and finance, etc. However, the computational...     

On the spectrum of the Cesàro operator C 1 on b\bar v_0 \cap \ell _\infty

In this paper we have investigated the spectrum of the Cesàro operator C ₁ which is regarded as an operator on the sequence space $b\bar v_0 \cap \ell _\infty $ the space of statistically null bounded variation sequences.     

A compact variant of the QCR method for quadratically constrained quadratic 0–1 programs

Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0–1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In this paper, we focus on the case of quadratically constrained quadratic 0–1 programs. The variant of QCR previously proposed for this case involves the addition of a quadratic number of auxiliary continuous variables. We show that, in fact, at most one additional variable is needed. Some computational results are also presented.     

An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the Dynamic Programming algorithm COMBO (Martello et al., Manag Sci 45(3):414–424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175–187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.     

A weak version of the Lipman–Zariski conjecture

Markushevich and Tikhomirov provided a construction of an irreducible symplectic V-manifold of dimension 4, the relative compactified Prym variety of a family of curves with involution, which is a Lagrangian fibration with polarization of type (1,2). We give a characterization of the dual Lagrangian fibration. We also identify the moduli space of Lagrangian fibrations of this type and show that the duality defines a rational involution on it.     

A constructive version of the Sylvester–Gallai theorem

The Sylvester–Gallai Theorem, stated as a problem by James Joseph Sylvester in 1893, asserts that for any finite, noncollinear set of points on a plane, there exists a line passing through exactly two points of the set. First, it is shown that for the real plane \({{\mathbb{R}^{2}}}\) the theorem is constructively invalid. Then, a well-known classical proof is examined from a constructive standpoint, locating the nonconstructivities. Finally, a constructive version of the theorem is established for the plane \({{\mathbb{R}^{2}}}\); this reveals the hidden constructive content of the classical theorem. The constructive methods used are those proposed by Errett Bishop.     

A Stereological Version of the Gauss–Bonnet Formula

We give a stereological version of the Gauss–Bonnet formula in order to compute the Euler characteristic of a domain with boundary in a smooth orientable surface in ³, by looking at contacts with a 'sweeping' plane.     

Bases of Feigin–Stoyanovsky’s type subspaces for $$C_\ell ^{(1)}$$

In this paper, we construct combinatorial bases of Feigin–Stoyanovsky’s type subspaces of standard modules for level k affine Lie algebra \(C_\ell ^{(1)}\). We prove spanning by using annihilating field \(x_\theta (z)^{k+1}\) of standard modules. In the proof of linear independence, we use simple currents and intertwining operators whose existence is given by fusion rules.     

A continuous version of the Hausdorff–Banach–Tarski paradox

We come up with a simple proof for a continuous version of the Hausdorff–Banach–Tarski paradox, which does not make use of Robinson’s method of compatible congruences and fits in the case of finite and countable paradoxical decompositions. It is proved that there exists a free subgroup whose rank is of the power of the continuum in a rotation group of a three-dimensional Euclidean space. We also argue that unbounded subsets of Euclidean space containing inner points are denumerably equipollent.     

A finite-volume version of Aizenman–Higuchi theorem for the 2d Ising model

In the late 1970s, in two celebrated papers, Aizenman and Higuchi independently established that all infinite-volume Gibbs measures of the two-dimensional ferromagnetic nearest-neighbor Ising model at inverse temperature ${\beta\geq 0}$ are of the form ${\alpha\mu^{+}_\beta + (1-\alpha)\mu^{-}_\beta}$ , where ${\mu^{+}_\beta}$ and ${\mu^{-}_\beta}$ are the two pure phases and ${0\leq\alpha\leq 1}$ . We present here a new approach to this result, with a number of advantages: (a) We obtain an optimal finite-volume, quantitative analogue (implying the classical claim); (b) the scheme of our proof seems more natural and provides a better picture of the underlying phenomenon; (c) this new approach might be applicable to systems for which the classical method fails.     

Polyhedral analysis and a new algorithm for the length constrained K–drones rural postman problem

Computational Optimization and Applications - The low-rank matrix completion problem can be solved by Riemannian optimization on a fixed-rank manifold. However, a drawback of the known approaches...     

Conditional contractivity of Runge–Kutta methods for nonlinear differential equations with many variable delays

This paper deals with conditional contractivity properties of Runge–Kutta (RK) methods with variable step-size applied to nonlinear differential equations with many variable delays (MDDEs). The concepts of CRN_m(ω, H)- and BN_f(μ, ?)-stability are introduced. It is shown that the numerical solution produced by a BN_f(μ, ?)-stable Runge–Kutta method with an appropriate interpolation is contractive. In particular, these results are also novel for nonlinear differential equations with many constant delays or single variable delay. To obtain BN_f(μ, ?)-stable methods, (k, l)-algebraically stable Runge–Kutta methods are also investigated.     

A nonmonotone derivative-free algorithm for nonlinear complementarity problems based on the new generalized penalized Fischer–Burmeister merit function

In this paper, we propose a new generalized penalized Fischer–Burmeister merit function, and show that the function possesses a system of favorite properties. Moreover, for the merit function, we establish the boundedness of level set under a weaker condition. We also propose a derivative-free algorithm for nonlinear complementarity problems with a nonmonotone line search. More specifically, we show that the proposed algorithm is globally convergent and has a locally linear convergence rate. Numerical comparisons are also made with the merit function used by Chen (J Comput Appl Math 232:455–471, 2009), which confirm the superior behaviour of the new merit function.