In this note we present tight lower bounds on the information-based complexity of large-scale smooth convex minimization problems. We demonstrate, in particular, that the k-step Conditional Gradient (a.k.a. Frank-Wolfe) algorithm as applied to minimizing smooth convex functions over the n-dimensional box with n ≥ k is optimal, up to an O(ln n)-factor, in terms of … Read more
We analyze the properties of the optimal portfolio policy for a multiperiod mean-variance investor facing multiple risky assets in the presence of general transaction costs such as proportional, market impact, and quadratic transaction costs. For proportional transaction costs, we find that a buy-and-hold policy is optimal: if the starting portfolio is outside a parallelogram-shaped no-trade … Read more
The paper is devoted to the study of tilt-stable local minimizers of general optimization problems in finite-dimensional spaces and its applications to classical nonlinear programs with twice continuously differentiable data. The importance of tilt stability has been well recognized from both theoretical and numerical aspects of optimization, and this notion has been extensively studied in … Read more
We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the so-called “cascade” model. The problem is to find the … Read more
The paper is devoted to full stability of optimal solutions in general settings of finite-dimensional optimization with applications to particular models of constrained optimization problems including those of conic and specifically semidefinite programming. Developing a new technique of variational analysis and generalized differentiation, we derive second-order characterizations of full stability, in both Lipschitzian and H\”olderian … Read more
The paper presents complete characterizations of Lipschitzian full stability of locally optimal solutions to problems of second-order cone programming (SOCP) expressed entirely in terms of their initial data. These characterizations are obtained via appropriate versions of the quadratic growth and strong second-order sucient conditions under the corresponding constraint quali cations. We also establish close relationships between … Read more
We study equilibrium problems with strongly pseudomonotone bifunctions in real Hilbert spaces. We show the existence of a unique solution. We then propose a generalized strongly convergent projection method for equilibrium problems with strongly pseudomonotone bifunctions. The proposed method uses only one projection without requiring Lipschitz continuity. Application to variational inequalities is discussed. CitationInstitute of … Read more
We propose a generalized proximal point algorithm (PPA), in the generic setting of finding a zero point of a maximal monotone operator. In addition to the classical PPA, a number of benchmark operator splitting methods in PDE and optimization literatures such as the Douglas-Rachford splitting method, Peaceman-Rachford splitting method, alternating direction method of multipliers, generalized … Read more
An algorithmic framework is presented for optimising general convex functions by non synchronised parallel processes. Each process greedily picks a suitable adaptive subset of coordinates and runs a bundle method on a corresponding restricted problem stopping whenever a descent step is encountered or predicted decrease is reduced sufficiently. No prior knowledge on the dependencies between … Read more
We present new results for the conditional gradient method (also known as the Frank-Wolfe method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial … Read more