Month: October 2015

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Evaluation complexity for convexly constrained optimization is considered and it is shown first that the complexity bound of $O(\epsilon^{-3/2})$ proved by Cartis, Gould and Toint (IMAJNA 32(4) 2012, pp.1662-1695) for computing an $\epsilon$-approximate first-order critical point can be obtained under significantly weaker assumptions. Moreover, the result is generalized to the case where high-order derivatives are … Read more

    A composition projection method for convex feasibility problems

  • Chen Jiawei
    • Categories Convex and Nonsmooth Optimization

    In this article, we propose a composition projection algorithm for solving feasibility problem in Hilbert space. The convergence of the proposed algorithm are established by using gap vector which does not involve the nonempty intersection assumption. Moreover, we provide the sufficient and necessary condition for the convergence of the proposed method. Article Download View A … Read more

    Combinatorial Optimal Control of Semilinear Elliptic PDEs

  • Christoph Buchheim
  • Renke Kuhlmann
  • Christian Meyer
    • Categories Cutting Plane Approaches, Semi-infinite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    Optimal control problems (OCP) containing both integrality and partial differential equation (PDE) constraints are very challenging in practice. The most wide-spread solution approach is to first discretize the problem, it results in huge and typically nonconvex mixed-integer optimization problems that can be solved to proven optimality only in very small dimensions. In this paper, we … Read more

    On Solving General Two-Stage Stochastic Programs

  • Manish Bansal
  • Sanjay Mehrotra
    • Categories Cutting Plane Approaches, Stochastic Programming

    We study general two-stage stochastic programs and present conditions under which the second stage programs can be convexified. This allows us to relax the restrictions, such as integrality, binary, semi-continuity, and many others, on the second stage variables in certain situations. Next, we introduce two-stage stochastic disjunctive programs (TSS-DPs) and extend Balas’s linear programming equivalent … Read more

    An improved DSATUR-based Branch and Bound for the Vertex Coloring Problem

  • Fabio Furini
  • Virginie Gabrel
  • Ternier Ian-Christopher
    • Categories Integer Programming, Network Optimization Tags , ,

    Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR based Branch and Bound (DSATUR) is an effective exact algorithm for the … Read more

    Coercive polynomials: Stability, order of growth, and Newton polytopes

  • Tomas Bajbar
  • Oliver Stein
    • Categories Global Optimization Theory, Polyhedra Tags , , , , ,

    In this article we introduce a stability concept for the coercivity of multivariate polynomials $f \in \mathbb{R}[x]$. In particular, we consider perturbations of $f$ by polynomials up to the so-called degree of stable coercivity, and we analyze this stability concept in terms of the corresponding Newton polytopes at infinity. For coercive polynomials $f \in \mathbb{R}[x]$ … Read more

    Robust Multicriteria Risk-Averse Stochastic Programming Models

  • Simge Küçükyavuz
  • Nilay Noyan
  • Xiao Liu
    • Categories Stochastic Programming

    In this paper, we study risk-averse models for multicriteria optimization problems under uncertainty. We use a weighted sum-based scalarization and take a robust approach by considering a set of scalarization vectors to address the ambiguity and inconsistency in the relative weights of each criterion. We model the risk aversion of the decision makers via the … Read more

    A Cutting Plane Method for Risk-constrained Traveling Salesman Problem with Random Arc Costs

  • Vladimir Boginski
  • Qipeng Zheng
  • Zhouchun Huang
  • Tao Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Transportation

    This paper considers the risk-constrained stochastic traveling salesman problem with random arc costs. In the context of stochastic arc costs, the deterministic traveling salesman problem’s optimal solutions would be ineffective because the selected route might be exposed to a greater risk where the actual cost can exceed the resource limit in extreme scenarios. We present … Read more

    On the Lovasz Theta Function and Some Variants

  • Laura Galli
  • Adam N. Letchford
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    The Lovasz theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovasz and the other to Groetschel et al. The former SDP is often thought to be preferable … Read more

    High Throughput Computing for Massive Scenario Analysis and Optimization to Minimize Cascading Blackout Risk

  • Eric Anderson
  • Jeff Linderoth
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Optimization of Simulated Systems

    We describe a simulation-based optimization method that allocates additional capacity to transmission lines in order to minimize the expected value of the load shed due to a cascading blackout. Estimation of the load-shed distribution is accomplished via the ORNL-PSerc-Alaska (OPA) simulation model, which solves a sequence of linear programs. Key to achieving an effective algorithm … Read more