This paper gives a straightforward implementation of simulated annealing for solving maximum cut problems and compares its performance to that of some existing heuristic solvers. The formulation used is classical, dating to a 1989 paper of Johnson, Aragon, McGeoch, and Schevon. This implementation uses no structure peculiar to the maximum cut problem, but its low … Read more
By using an axiomatic approach we formalize the concept of size index for closed convex cones in the Euclidean space $\mathbb{R}^n$. We review a dozen of size indices disseminated through the literature, commenting on the advantages and disadvantages of each choice. Citation To appear in Journal of Convex Analysis (2015) Article Download View On measures … Read more
The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this … Read more
In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS-epsilon) and least squares boosting (LS-Boost-epsilon), can be viewed as subgradient descent to minimize the loss function defined … Read more
In this paper we introduce an inexact proximal point algorithm using proximal distances for solving variational inequality problems when the mapping is pseudomonotone or quasimonotone. Under some natural assumptions we prove that the sequence generates by the algorithm is convergent for the pseudomonotone case and weakly convergent for the quasimonotone ones. This approach unifies the … Read more
In this paper, we develop a risk-averse two-stage stochastic program (RTSP) which explicitly incorporates the distributional ambiguity covering both discrete and continuous distributions. Starting from a set of historical data samples, we construct a confidence set for the ambiguous probability distribution through nonparametric statistical estimation of its density function. We then formulate RTSP from the … Read more
In this article, we study and compare two approaches to solving stochastic optimal control problems with an expectation constraint on the final state. The case of a probability constraint is included in this framework. The first approach is based on a dynamic programming principle and the second one uses Lagrange relaxation. These approaches can be … Read more
The traditional two-stage stochastic program approach is to minimize the total expected cost with the consideration of parameter uncertainty, and the distribution of the random parameters is assumed to be known. However, in most practices, the actual distribution of the random parameters is not known, and only a certain amount of historical data are available. … Read more
In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more
This paper describes an algorithm for solving structured nonsmooth convex optimization problems using OSGA, a first-order method with the complexity $O(\eps^{-2})$ for Lipschitz continuous nonsmooth problems and $O(\eps^{-1/2})$ for smooth problems with Lipschitz continuous gradient. If the nonsmoothness of the problem is manifested in a structured way, we reformulate the problem in a form that … Read more