We present global convergence rates for a line-search method which is based on random first-order models and directions whose quality is ensured only with certain probability. We show that in terms of the order of the accuracy, the evaluation complexity of such a method is the same as its counterparts that use deterministic accurate models; … Read more
We present a new algorithm for optimizing a linear function over the set of efficient solutions of a multiobjective integer program MOIP. The algorithm’s success relies on the efficiency of a new algorithm for enumerating the nondominated points of a MOIP, which is the result of employing a novel criterion space decomposition scheme which (1) … Read more
Constraint reduction is an essential method because the computational cost of the interior point methods can be effectively saved. Park and O’Leary proposed a constraint-reduced predictor-corrector algorithm for semidefinite programming with polynomial global convergence, but they did not show its superlinear convergence. We first develop a constraint-reduced algorithm for semidefinite programming having both polynomial global … Read more
A key step in solving minimax distributionally robust optimization (DRO) problems is to reformulate the inner maximization w.r.t. probability measure as a semiinfinite programming problem through Lagrange dual. Slater type conditions have been widely used for zero dual gap when the ambiguity set is defined through moments. In this paper, we investigate effective ways for … Read more
Non-convex quadratic programming with box constraints is a fundamental problem in the global optimization literature, being one of the simplest NP-hard nonlinear programs. We present a new heuristic for this problem, which enables one to obtain solutions of excellent quality in reasonable computing times. The heuristic consists of four phases: binarisation, convexification, branch-and-bound, and local … Read more
In a Hilbert space setting, we study the stability properties of the regularized continuous Newton method with two potentials, which aims at solving inclusions governed by structured monotone operators. The Levenberg-Marquardt regularization term acts in an open loop way. As a byproduct of our study, we can take the regularization coefficient of bounded variation. These … Read more
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. CitationTo appear in Journal of Convex Analysis (2015) ArticleDownload View PDF
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 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