Month: May 2017

Integrated Generator Maintenance and Operations Scheduling under Uncertain Failure Times

  • Shabbir Ahmed
  • Nagi Gebraeel
  • Murat Yildirim
  • Beste Basciftci
    • Categories Applications - Science and Engineering, Stochastic Programming Tags , ,

    Planning maintenances and operations is an important concern in power systems. Although optimization based joint maintenance and operations scheduling is studied in the literature, sudden disruptions due to random generator failures are not considered. In this paper we propose a stochastic mixed-integer programming approach for integrated condition-based maintenance and operations scheduling problem for a fleet … Read more

    Exact penalty decomposition method for zero-norm minimization based on MPEC formulation

  • Xiaolan Liu
  • Shaohua Pan
  • Shujun Shujun
    • Categories Applications - OR and Management Sciences Tags , , ,

    We reformulate the zero-norm minimization problem as an equivalent mathematical program with equilibrium constraints and establish that its penalty problem, induced by adding the complementarity constraint to the objective, is exact. Then, by the special structure of the exact penalty problem, we propose a decomposition method that can seek a global optimal solution of the … Read more

    Error bounds for rank constrained optimization problems and applications

  • Shaohua Pan
  • Shujun Shujun
    • Categories Applications - OR and Management Sciences Tags , , ,

    This paper is concerned with the rank constrained optimization problem whose feasible set is the intersection of the rank constraint set $\mathcal{R}=\!\big\{X\in\mathbb{X}\ |\ {\rm rank}(X)\le \kappa\big\}$ and a closed convex set $\Omega$. We establish the local (global) Lipschitzian type error bounds for estimating the distance from any $X\in \Omega$ ($X\in\mathbb{X}$) to the feasible set and … Read more

    How to Compute a M-stationary point of the MPCC

  • Jean-Pierre Dussault
  • Tangi Migot
  • Mounir Haddou
  • Abdeslam Kadrani
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization

    We discuss here the convergence of relaxation methods for MPCC with approximate sequence of stationary points by presenting a general framework to study these methods. It has been pointed out in the literature, \cite{kanzow2015}, that relaxation methods with approximate stationary points fail to give guarantee of convergence. We show that by defining a new strong … Read more

    The New Butterfly Relaxation Methods for Mathematical Program with Complementarity Constraints

  • Jean-Pierre Dussault
  • Tangi Migot
  • Mounir Haddou
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags

    We propose a new family of relaxation schemes for mathematical program with complementarity constraints that extends the relaxations of Kadrani, Dussault, Bechakroun from 2009 and the one of Kanzow \& Schwartz from 2011. We discuss the properties of the sequence of relaxed non-linear program as well as stationarity properties of limiting points. A sub-family of … Read more

    Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

  • Yichen Chen
  • Mengdi Wang
    • Categories Dynamic Programming, Linear Programming Tags ,

    We study the computational complexity of the infinite-horizon discounted-reward Markov Decision Problem (MDP) with a finite state space $\cS$ and a finite action space $\cA$. We show that any randomized algorithm needs a running time at least $\Omega(\carS^2\carA)$ to compute an $\epsilon$-optimal policy with high probability. We consider two variants of the MDP where the … Read more

    A pattern search and implicit filtering algorithm for solving linearly constrained minimization problems with noisy objective functions

  • Maria A. Diniz-Ehrhardt
  • Sandra Augusta Santos
  • D. G. Ferreira
    • Categories Constrained Nonlinear Optimization

    PSIFA -Pattern Search and Implicit Filtering Algorithm- is a derivative-free algorithm that has been designed for linearly constrained problems with noise in the objective function. It combines some elements of the pattern search approach of Lewis and Torczon (2000) with ideas from the method of implicit filtering of Kelley (2011) enhanced with a further analysis … Read more

    Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization

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

    Necessary conditions for high-order optimality in smooth nonlinear constrained optimization are explored and their inherent intricacy discussed. A two-phase minimization algorithm is proposed which can achieve approximate first-, second- and third-order criticality and its evaluation complexity is analyzed as a function of the choice (among existing methods) of an inner algorithm for solving subproblems in … Read more

    On the complexity of the Unit Commitment Problem

  • Pascale Bendotti
  • Pierre Fouilhoux
  • Cécile Rottner
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization

    This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods.A classical reduction from the knapsack problem shows that the UCP is NP-hard in the ordinary sense even for T=1. The UCP is proved to be strongly NP-hard.When either a unitary cost … Read more

    Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper establishes the iteration-complexity of a Jacobi-type non-Euclidean proximal alternating direction method of multipliers (ADMM) for solving multi-block linearly constrained nonconvex programs. The subproblems of this ADMM variant can be solved in parallel and hence the method has great potential to solve large scale multi-block linearly constrained nonconvex programs. Moreover, our analysis allows the … Read more