Month: October 2009

Solving Constrained Total-Variation Image Restoration and Reconstruction Problems via Alternating Direction Methods

  • Michael K. Ng
  • Xiao-Ming Yuan
  • Pierre Weiss
    • Categories Applications - Science and Engineering Tags , ,

    In this paper, we study alternating direction methods for solving constrained total-variation image restoration and reconstruction problems. Alternating direction methods can be implementable variants of the classical augmented Lagrangian method for optimization problems with separable structures and linear constraints. The proposed framework allows us to solve problems of image restoration, impulse noise removal, inpainting and … Read more

    Easy distributions for combinatorial optimization problems with probabilistic constraints

  • Bernard Fortz
  • Michael Poss
    • Categories Combinatorial Optimization, Stochastic Programming Tags , ,

    We show how we can linearize probabilistic linear constraints with binary variables when all coefficients are distributed according to either $\mathcal{N}(\mu_i,\lambda \mu_i)$, for some $\lambda >0$ and $\mu_i>0$, or $\Gamma(k_i,\theta)$ for some $\theta >0$ and $k_i>0$. The constraint can also be linearized when the coefficients are independent and identically distributed if they are, besides, either … Read more

    A Computational Framework for Uncertainty Quantification and Stochastic Optimization in Unit Commitment with Wind Power Generation

  • Mihai Anitescu
  • Emil M. Constantinescu
  • Victor M. Zavala
  • S. Lee
  • M. Rocklin
    • Categories Control Applications, Scheduling, Stochastic Programming Tags , , ,

    We present a computational framework for integrating a state-of-the-art numerical weather prediction (NWP) model in stochastic unit commitment/energy dispatch formulations that account for wind power uncertainty. We first enhance the NWP model with an ensemble-based uncertainty quantification strategy implemented in a distributed-memory parallel computing architecture. We discuss computational issues arising in the implementation of the … Read more

    On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Unconstrained Optimization Tags , ,

    It is shown that the steepest descent and Newton’s method for unconstrained nonconvex optimization under standard assumptions may be both require a number of iterations and function evaluations arbitrarily close to O(epsilon^{-2}) to drive the norm of the gradient below epsilon. This shows that the upper bound of O(epsilon^{-2}) evaluations known for the steepest descent … Read more

    Stopping rules and backward error analysis for bound-constrained optimization

  • Serge Gratton
  • Philippe L. Toint
  • Mélodie Mouffe
    • Categories Bound-constrained Optimization, Optimization Software Design Principles Tags , , , ,

    Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria … Read more

    Algorithms and Software for Convex Mixed Integer Nonlinear Programs

  • Pierre Bonami
  • Mustafa Kılınç
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming

    This paper provides a survey of recent progress and software for solving mixed integer nonlinear programs (MINLP) wherein the objective and constraints are defined by convex functions and integrality restrictions are imposed on a subset of the decision variables. Convex MINLPs have received sustained attention in very years. By exploiting analogies to the case of … Read more

    A heuristic to generate rank-1 GMI cuts

  • Sanjeeb Dash
  • Marcos Goycoolea
    • Categories Cutting Plane Approaches Tags , ,

    Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of an MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts … Read more

    Two-Stage Robust Unit Commitment Problem

  • Yongpei Guan
  • Muhong Zhang
    • Categories Robust Optimization Tags , , ,

    As an energy market transforms from a regulated market to a deregulated one, the demands for a power plant are highly uncertain. In this paper, we study a two-stage robust optimization formulation and provide a tractable solution approach for the problem. The computational experiments show the effectiveness of our approach. Article Download View Two-Stage Robust … Read more

    Quadratic factorization heuristics for copositive programming

  • Immanuel M. Bomze
  • Florian Jarre
  • Franz Rendl
    • Categories (Mixed) Integer Linear Programming, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone … Read more