Month: December 2010

Calculating all local minima on liquidus surfaces using the FactSage software and databases and the Mesh Adaptive Direct Search algorithm

  • Charles Audet
  • Aïmen E. Gheribi
  • Sébastien Le Digabel
  • Arthur D. Pelton
  • Christian Robelin
    • Categories Applications - Science and Engineering

    It is often of interest, for a multicomponent system, to identify the low melting compositions at which local minima of the liquidus surface occur. The experimental determination of these minima can be very time-consuming. An alternative is to employ the CALPHAD approach using evaluated thermodynamic databases containing optimized model parameters giving the thermodynamic properties of … Read more

    Complexity bounds for second-order optimality in unconstrained optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis, Gould and Toint (2010) show that at most O(epsilon^{-3}) iterations may have to be performed for finding an iterate which is within epsilon of satisfying second-order optimality conditions. We first show … Read more

    Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion

  • Vitor de Matos
  • Andrew B. Philpott
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    We consider the incorporation of a time-consistent coherent risk measure into a multi-stage stochastic programming model, so that the model can be solved using a SDDP-type algorithm. We describe the implementation of this algorithm, and study the solutions it gives for an application of hydro-thermal scheduling in the New Zealand electricity system. The performance of … Read more

    The central curve in linear programming

  • Jesús A. De Loera
  • Bernd Sturmfels
  • Cynthia Vinzant
    • Categories Convex Optimization, Linear Programming, Nonlinear Optimization Tags , , , , , , , , , , ,

    The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more

    Preconditioning and Globalizing Conjugate Gradients in Dual Space for Quadratically Penalized Nonlinear-Least Squares Problems

  • Serge Gratton
  • Philippe L. Toint
  • Selime Gürol
    • Categories Nonlinear Systems and Least-Squares, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs Tags , , , , ,

    When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each … Read more

    Inexact Dynamic Bundle Methods

  • Krzysztof C. Kiwiel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    We give a proximal bundle method for minimizing a convex function $f$ over $\mathbb{R}_+^n$. It requires evaluating $f$ and its subgradients with a possibly unknown accuracy $\epsilon\ge0$, and maintains a set of free variables $I$ to simplify its prox subproblems. The method asymptotically finds points that are $\epsilon$-optimal. In Lagrangian relaxation of convex programs, it … Read more

    A Continuous Dynamical Newton-Like Approach to Solving Monotone Inclusions

  • Hédy Attouch
  • Benar Fux Svaiter
    • Categories Complementarity and Variational Inequalities, Infinite Dimensional Optimization, Systems governed by Differential Equations Optimization Tags , , , , , , , ,

    We introduce non-autonomous continuous dynamical systems which are linked to Newton and Levenberg-Marquardt methods. They aim at solving inclusions governed by maximal monotone operators in Hilbert spaces. Relying on Minty representation of maximal monotone operators as lipschitzian manifolds, we show that these dynamics can be formulated as first-order in time differential systems, which are relevant … Read more

    A note on the MIR closure and basic relaxations of polyhedra

  • Sanjeeb Dash
  • Oktay Gunluk
  • Christian Raack
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    Anderson, Cornuejols and Li (2005) show that for a polyhedral mixed integer set defined by a constraint system Ax >= b, where x is n-dimensional, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a “basic relaxation”, i.e., one defined by a subset of linearly … Read more

    Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

  • Antoine Deza
  • Tamás Terlaky
  • Anthony Vannelli
  • Chris Dickson
  • Hu Zhang
    • Categories Integer Programming, VLSI layout Tags , ,

    Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more