Calculating optimal conditions for alloy and process design using thermodynamic and property databases, the FactSage software and the Mesh Adaptive Direct Search algorithm

During alloy and process design, it is often desired to identify regions of design or process variables for which certain calculated functions have optimal values under various constraints, for example: compositions of minimum liquidus temperature in an N-component alloy; compositions where the amount of precipitate in a given phase is maximized or minimized during annealing … Read more

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

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

Complexity bounds for second-order optimality in unconstrained optimization

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

The central curve in linear programming

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

Optimal adaptive control of cascading power grid failures

We describe experiments with parallel algorithms for computing adaptive controls for attenuating power grid cascading failures. Citation Columbia University, 2010 Article Download View Optimal adaptive control of cascading power grid failures

Inexact Dynamic Bundle Methods

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

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

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

A Continuous Dynamical Newton-Like Approach to Solving Monotone Inclusions

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

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

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