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

Categories Finance and Economics, Game Theory Tags , , , ,

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

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

Categories Linear Programming Tags , ,

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

Data-Driven Chance Constrained Stochastic Program

Categories Stochastic Programming

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

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

Categories Nonlinear Optimization Tags , , ,

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

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

Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

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

A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially

Categories Linear Programming, Polyhedra Tags , , , ,

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

Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization

Categories Convex and Nonsmooth Optimization, Statistics, Stochastic Approaches Tags , , , ,

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

Ambiguous Probabilistic Programs

Categories Robust Optimization, Stochastic Programming Tags , , ,

Probabilistic programs are widely used decision models. When implemented in practice, however, there often exists distributional ambiguity in these models. In this paper, we model the ambiguity using the likelihood ratio (LR) and use LR to construct various ambiguity sets. We consider ambiguous probabilistic programs which optimize under the worst case. Ambiguous probabilistic programs can … Read more

A Convex Optimization Approach for Computing Correlated Choice Probabilities with Many Alternatives

Categories Applications - OR and Management Sciences, Robust Optimization, Semi-definite Programming Tags , ,

A popular discrete choice model that incorporates correlation information is the Multinomial Probit (MNP) model where the random utilities of the alternatives are chosen from a multivariate normal distribution. Computing the choice probabilities is challenging in the MNP model when the number of alternatives is large and simulation is used to approximate the choice probabilities. … Read more