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
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
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
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
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
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
In this work, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear … Read more
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
We establish that the extension complexity of the nXn correlation polytope is at least 1.5^n by a short proof that is self-contained except for using the fact that every face of a polyhedron is the intersection of all facets it is contained in. The main innovative aspect of the proof is a simple combinatorial argument … Read more
We introduce a proximal version of the stochastic dual coordinate ascent method and show how to accelerate the method using an inner-outer iteration procedure. We analyze the runtime of the framework and obtain rates that improve state-of-the-art results for various key machine learning optimization problems including SVM, logistic regression, ridge regression, Lasso, and multiclass SVM. … Read more