An interior point method with a primal-dual quadratic barrier penalty function for nonlinear semidefinite programming

  • Atsushi Kato
  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we consider an interior point method for nonlinear semidefinite programming. Yamashita, Yabe and Harada presented a primal-dual interior point method in which a nondifferentiable merit function was used. By using shifted barrier KKT conditions, we propose a differentiable primal-dual merit function within the framework of the line search strategy, and prove the … Read more

    Intersection Cuts for Nonlinear Integer Programming: Convexification Techniques for Structured Sets

  • Mustafa Kilinc
  • Sina Modaresi
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming

    We study the generalization of split, k-branch split, and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Nonlinear Programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise … Read more

    Robust combinatorial optimization with cost uncertainty

  • Michael Poss
    • Categories Combinatorial Optimization, Robust Optimization Tags , , , ,

    We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates … Read more

    Decentralised Shared Resource Constraint Scheduling with Confidentiality Protection

  • Christine O'Keefe
  • Gaurav Singh
    • Categories Production and Logistics, Scheduling, Supply Chain Management Tags , , , ,

    As resources become scarce and expensive, it has become increasingly important for players in a decentralised supply chain to collaborate. One of the main challenges in collaboration is to find close to globally optimal solutions without sharing individual player’s private data. Taking a decentralised resource constrained scheduling problem as an example we present a methodology … Read more

    On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems

  • Anders Forsgren
  • Tove Odland
    • Categories Quadratic Programming, Unconstrained Optimization Tags , ,

    It is well known that the conjugate gradient method and a quasi-Newton method, using any well-defined update matrix from the one-parameter Broyden family of updates, produce identical iterates on a quadratic problem with positive-definite Hessian. This equivalence does not hold for any quasi-Newton method. We define precisely the conditions on the update matrix in the … Read more

    Extension of Completely Positive Cone Relaxation to Polynomial Optimization

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods … Read more

    Abstract Newtonian Frameworks and Their Applications

  • Alexey F. Izmailov
  • A. S. Kurennoy
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , , , ,

    We unify and extend some Newtonian iterative frameworks developed earlier in the literature, which results in a collection of convenient tools for local convergence analysis of various algorithms under various sets of assumptions including strong metric regularity, semistability, or upper-Lipschizt stability, the latter allowing for nonisolated solutions. These abstract schemes are further applied for deriving … Read more

    Attraction of Newton method to critical Lagrange multipliers: fully quadratic case

  • Alexey F. Izmailov
  • E.I. Uskov
    • Categories Constrained Nonlinear Optimization Tags , , ,

    All previously known results concerned with attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers were a posteriori by nature: they were showing that in case of convergence, the dual limit is in a sense unlikely to be noncritical. This paper suggests the first a priori result in this direction, showing that critical … Read more

    Strong local convergence properties of adaptive regularized methods for nonlinear least-squares

  • Stefania Bellavia
  • Benedetta Morini
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    This paper studies adaptive regularized methods for nonlinear least-squares problems where the model of the objective function used at each iteration is either the Euclidean residual regularized by a quadratic term or the Gauss-Newton model regularized by a cubic term. For suitable choices of the regularization parameter the role of the regularization term is to … Read more

    Equivalence of an Approximate Linear Programming Bound with the Held-Karp Bound for the Traveling Salesman Problem

  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming Tags , , ,

    We consider two linear relaxations of the asymmetric traveling salesman problem (TSP), the Held-Karp relaxation of the TSP’s arc-based formulation, and a particular approximate linear programming (ALP) relaxation obtained by restricting the dual of the TSP’s shortest path formulation. We show that the two formulations produce equal lower bounds for the TSP’s optimal cost regardless … Read more