The solution of Euclidean norm trust region SQP subproblems via second order cone programs, an overview and elementary introduction

  • Florian Jarre
  • Felix Lieder
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming Tags , ,

    It is well known that convex SQP subproblems with a Euclidean norm trust region constraint can be reduced to second order cone programs for which the theory of Euclidean Jordan-algebras leads to efficient interior-point algorithms. Here, a brief and self-contained outline of the principles of such an implementation is given. All identities relevant for the … Read more

    Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Weihong Hu
  • Alejandro Toriello
    • Categories 0-1 Programming, Dynamic Programming Tags , ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

    SDDP for multistage stochastic programs: Preprocessing via scenario reduction

  • Jitka Dupacova
  • Vaclav Kozmik
    • Categories Stochastic Programming Tags , , ,

    Even with recent enhancements, computation times for large-scale multistage problems with risk-averse objective functions can be very long. Therefore, preprocessing via scenario reduction could be considered as a way to significantly improve the overall performance. Stage-wise backward reduction of single scenarios applied to a fixed branching structure of the tree is a promising tool for … Read more

    How to Reach his Desires: Variational Rationality and the Equilibrium Problem on Hadamard Manifolds

  • Glaydston Bento
  • João Xavier da Cruz Neto
  • Antoine Soubeyran
  • Pedro A. Soares Jr.
    • Categories Generalized Convexity/Monoticity Tags , , , , ,

    In this paper we present a sufficient condition for the existence of a solution for an \mbox{equilibrium} problem on an Hadamard manifold and under suitable assumptions on the sectional curvature, we \mbox{propose} a framework for the convergence analysis of a proximal point algorithm to solve this equilibrium \mbox{problem}. Finally, we offer an application to the … Read more

    Borwein-Preiss Variational Principle Revisited

  • Alexander Y. Kruger
  • Somyot Plubtieng
  • Thidaporn Seangwattana
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    In this article, we refine and slightly strengthen the metric space version of the Borwein–Preiss variational principle due to Li, Shi, J. Math. Anal. Appl. 246, 308–319 (2000), clarify the assumptions and conclusions of their Theorem 1 as well as Theorem 2.5.2 in Borwein, Zhu, Techniques of Variational Analysis, Springer (2005) and streamline the proofs. … Read more

    A polynomially solvable case of the pooling problem

  • Natashia Boland
  • Thomas Kalinowski
  • Fabian Rigterink
    • Categories Constrained Nonlinear Optimization

    Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border … Read more

    Quantifying Double McCormick

  • Jon Lee
  • Emily Speakman
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , , , ,

    When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the … Read more

    Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming

  • Deren Han
  • Defeng Sun
  • Liwei Zhang
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , ,

    In this paper, we aim to provide a comprehensive analysis on the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a certain error bound condition, we establish the global linear rate of convergence for a more general semi-proximal ADMM with the dual steplength … Read more

    Robust Dual Response Optimization

  • Dick den Hertog
  • Jack P.C. Kleijnen
  • Ihsan Yanıkoğlu
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Robust Optimization

    This article presents a robust optimization reformulation of the dual response problem developed in response surface methodology. The dual response approach fits separate models for the mean and the variance, and analyzes these two models in a mathematical optimization setting. We use metamodels estimated from experiments with both controllable and environmental inputs. These experiments may … Read more

    Duality in Two-stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds

  • Dimitris Bertsimas
  • Frans J.C.T. de Ruiter
    • Categories Applications - OR and Management Sciences, Robust Optimization

    In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the … Read more