A scenario decomposition algorithm for 0-1 stochastic programs

  • Shabbir Ahmed
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    We propose a scenario decomposition algorithm for stochastic 0-1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and … Read more

    Multiperiod Portfolio Optimization with General Transaction Costs

  • Victor DeMiguel
  • Xiaoling Mei
  • Francisco Javier Nogales
    • Categories Convex Optimization, Finance and Economics

    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

    Theoretical aspects of adopting exact penalty elements within sequential methods for nonlinear programming

  • Ademir A. Ribeiro
  • Sandra Augusta Santos
  • Mael Sachine
    • Categories Constrained Nonlinear Optimization

    In the context of sequential methods for solving general nonlinear programming problems, it is usual to work with augmented subproblems instead of the original ones, tackled by the $\ell_1$-penalty function together with the shortcut usage of a convenient penalty parameter. This paper addresses the theoretical reasoning behind handling the original subproblems by such an augmentation … Read more

    On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization

  • Cristobal Guzman
  • Arkadi Nemirovski
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    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

    RSP-Based Analysis for Sparsest and Least $\ell_1hBcNorm Solutions to Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

    Second-order Characterizations of Tilt Stability with Applications to Nonlinear Programming

  • Boris S. Mordukhovich
  • Nghia Tran
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    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

    Some notes on applying computational divided differencing in optimization

  • Stephen A. Vavasis
    • Categories Optimization Software Design Principles Tags , , ,

    We consider the problem of accurate computation of the finite difference $f(\x+\s)-f(\x)$ when $\Vert\s\Vert$ is very small. Direct evaluation of this difference in floating point arithmetic succumbs to cancellation error and yields 0 when $\s$ is sufficiently small. Nonetheless, accurate computation of this finite difference is required by many optimization algorithms for a “sufficient decrease” … Read more

    Convex relaxation for finding planted influential nodes in a social network

  • Lisa Elkin
  • Ting Kei Pong
  • Stephen A. Vavasis
    • Categories Convex Optimization, Data-Mining Tags , ,

    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

    Full Stability in Finite-Dimensional Optimization

  • Boris S. Mordukhovich
  • Tyrrell Rockafellar
  • Nghia Tran
    • Categories Convex and Nonsmooth Optimization

    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

    A practicable framework for distributionally robust linear optimization

  • Dimitris Bertsimas
  • Melvyn Sim
  • Meilin Zhang
    • Categories Applications - OR and Management Sciences Tags , ,

    We developed a modular framework to obtain exact and approximate solutions to a class of linear optimization problems with recourse with the goal to minimize the worst-case expected objective over an ambiguity set of distributions. The ambiguity set is specified by linear and conic quadratic representable expectation constraints and the support set is also linear … Read more