Convergence Conditions for Newton-type Methods Applied to Complementarity Systems with Nonisolated Solutions

  • Andreas Fischer
  • Alexey F. Izmailov
  • Markus Herrich
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , , , ,

    We consider a class of Newton-type methods for constrained systems of equations that involve complementarity conditions. In particular, at issue are the constrained Levenberg–Marquardt method and the recently introduced Linear Programming-Newton method, designed for the difficult case when solutions need not be isolated, and the equation mapping need not be differentiable at the solutions. We … Read more

    A Semidefinite Opimization Approach to the Target Visitation Problem

  • Philipp Hungerländer
    • Categories Production and Logistics, Semi-definite Programming

    We propose an exact algorithm for the Target Visitation Problem (TVP). The (TVP) is a composition of the Linear Ordering Problem and the Traveling Salesman Problem. It has several military and non-military applications, where two important, often competing factors are the overall distance traveled (e.g. by an unmanned aerial vehicle) and the visiting sequence of … Read more

    The impact of wind uncertainty on the strategic valuation of distributed electricity storage

  • Pedro Crespo Del Granado
  • Zhan Pang
  • Stein W. Wallace
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , , , ,

    The intermittent nature of wind energy generation has introduced a new degree of uncertainty to the tactical planning of energy systems. Short-term energy balancing decisions are no longer (fully) known, and it is this lack of knowledge that causes the need for strategic thinking. But despite this observation, strategic models are rarely set in an … Read more

    A Polyhedral Investigation of Star Colorings

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories Polyhedra Tags , , , ,

    Given a weighted undirected graph~$G$ and a nonnegative integer~$k$, the maximum~$k$-star colorable subgraph problem consists of finding an induced subgraph of~$G$ which has maximum weight and can be star colored with at most~$k$ colors; a star coloring does not color adjacent nodes with the same color and avoids coloring any 4-path with exactly two colors. … Read more

    Extended Formulations in Mixed Integer Conic Quadratic Programming

  • Iain Dunning
  • Joey Huchette
  • Juan Pablo Vielma
  • Miles Lubin
    • Categories (Mixed) Integer Nonlinear Programming

    In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on … Read more

    On the Iteration Complexity of Some Projection Methods for Monotone Linear Variational Inequalities

  • Caihua Chen
  • Xiaoling Fu
  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Complementarity and Variational Inequalities Tags , , ,

    Projection type methods are among the most important methods for solving monotone linear variational inequalities. In this note, we analyze the iteration complexity for two projection methods and accordingly establish their worst-case O(1/t) convergence rates measured by the iteration complexity in both the ergodic and nonergodic senses, where t is the iteration counter. Our analysis … Read more

    On the cone eigenvalue complementarity problem for higher-order tensors

  • Hongjin He
  • Liqun Qi
  • Chen Ling
    • Categories Complementarity and Variational Inequalities, Global Optimization Tags , , , ,

    In this paper, we consider the tensor generalized eigenvalue complementarity problem (TGEiCP), which is an interesting generalization of matrix eigenvalue complementarity problem (EiCP). First, we given an affirmative result showing that TGEiCP is solvable and has at least one solution under some reasonable assumptions. Then, we introduce two optimization reformulations of TGEiCP, thereby beneficially establishing … Read more

    Safe Approximations of Chance Constraints Using Historical Data

  • Dick den Hertog
  • Ihsan Yanıkoğlu
    • Categories Robust Optimization, Stochastic Programming

    This paper proposes a new way to construct uncertainty sets for robust optimization. Our approach uses the available historical data for the uncertain parameters and is based on goodness-of-fit statistics. It guarantees that the probability that the uncertain constraint holds is at least the prescribed value. Compared to existing safe approximation methods for chance constraints, … Read more

    New Lower Bounds for Semi-online Scheduling on Two Uniform Machines with Known Optimum

  • György Dósa
  • Armin Fügenschuh
  • Zhiyi Tan
  • Zsolt Tuza
  • Krzysztof Wesek
    • Categories Scheduling Tags , , ,

    This problem is about to schedule a number of jobs of different lengths on two uniform machines with given speeds 1 and s ≥ 1, so that the overall finishing time, i.e. the makespan, is earliest possible. We consider a semi- online variant introduced (for equal speeds) by Azar and Regev, where the jobs are … Read more

    On iteratively reweighted Algorithms for Non-smooth Non-convex Optimization in Computer Vision

  • Thomas Brox
  • Peter Ochs
  • Thomas Pock
  • Alexey Dosovitskiy
    • Categories Nonlinear Optimization Tags , , , , , ,

    Natural image statistics indicate that we should use non-convex norms for most regularization tasks in image processing and computer vision. Still, they are rarely used in practice due to the challenge of optimization. Recently, iteratively reweighed $\ell_1$ minimization (IRL1) has been proposed as a way to tackle a class of non-convex functions by solving a … Read more