A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing

We present a new recovery analysis for a standard compressed sensing algorithm, Iterative Hard Thresholding (IHT) (Blumensath and Davies, 2008), which considers the fixed points of the algorithm. In the context of arbitrary measurement matrices, we derive a sufficient condition for convergence of IHT to a fixed point and a necessary condition for the existence … Read more

A pseudo-polynomial size formulation for 2-stage two-dimensional knapsack problems

Two dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum … Read more

Primal-dual methods for solving infinite-dimensional games

In this paper we show that the infinite-dimensional differential games with simple objective functional can be solved in a finite-dimensional dual form in the space of dual multipliers for the constraints related to the end points of the trajectories. The primal solutions can be easily reconstructed by the appropriate dual subgradient schemes. The suggested schemes … Read more

Rounding on the standard simplex: regular grids for global optimization

Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all $\ell^p$-norms for $p\ge 1$. We show that the minimal $\ell^p$-distance to the regular grid on the standard simplex can exceed one, even for very fine … Read more

Existence of Competitive Equilibrium in Piecewise Linear and Concave Exchange Economies and the non-symmetric Nash Bargaining Solution

In this paper we show that for concave piecewise linear exchange economies every competitive equilibrium satisfies the property that the competitive allocation is a non-symmetric Nash bargaining solution with weights being the initial income of individual agents evaluated at the equilibrium price vector. We prove the existence of competitive equilibrium for concave piecewise linear exchange … Read more

Data-Driven Chance Constrained Stochastic Program

Chance constrained programming is an effective and convenient approach to control risk in decision making under uncertainty. However, due to unknown probability distributions of random parameters, the solution obtained from a chance constrained optimization problem can be biased. In addition, instead of knowing the true distributions of random parameters, in practice, only a series of … Read more

Strengthened Bounds for the Probability of k-Out-Of-n Events

Abstract: Given a set of n random events in a probability space, represented by n Bernoulli variables (not necessarily independent,) we consider the probability that at least k out of n events occur. When partial distribution information, i.e., individual probabilities and all joint probabilities of up to m (m< n) events, are provided, only an ... Read more

Trust-Region Problems with Linear Inequality Constraints: Exact SDP Relaxation, Global Optimality and Robust Optimization

The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having … Read more

On the use of iterative methods in cubic regularization for unconstrained optimization

In this paper we consider the problem of minimizing a smooth function by using the Adaptive Cubic Regularized framework (ARC). We focus on the computation of the trial step as a suitable approximate minimizer of the cubic model and discuss the use of matrix-free iterative methods. Our approach is alternative to the implementation proposed in … Read more