Quadratic Programming

A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming

  • David Ek
  • Anders Forsgren
    • Categories Quadratic Programming Tags , , , ,

    The focus in this work is interior-point methods for quadratic optimization problems with linear inequality constraints where the system of nonlinear equations that arise are solved with Newton-like methods. In particular, the concern is the system of linear equations to be solved at each iteration. Newton systems give high quality solutions but there is an … Read more

    Largest small polygons: A sequential convex optimization approach

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal area of a small polygon with $n=2m$ vertices is not known when $m\ge 7$. Finding the largest small $n$-gon for a given number $n\ge 3$ can be formulated as a nonconvex quadratically constrained quadratic optimization problem. We propose to solve this problem with a … Read more

    Routing and Wavelength Assignment with Protection: A Quadratic Unconstrained Binary Optimization Approach

  • Merve Bodur
  • Hamed Pouya
  • Oylum Şeker
    • Categories 0-1 Programming, Quadratic Programming, Telecommunications

    The routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant maximum number of requests by assigning lightpaths at minimum network resource usage level, while ensuring the provided services remain functional in case of a … Read more

    On the Complexity of Finding a Local Minimizer of a Quadratic Function over a Polytope

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Quadratic Programming Tags , , ,

    We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a … Read more

    Necessary and sufficient conditions for rank-one generated cones

  • C.J. Argue
  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Quadratic Programming, Semi-definite Programming

    A closed convex conic subset $\cS$ of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of $\cS$ is closely related to the exactness of SDP relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to $\cS$. We consider the case … Read more

    Mathematical Programming formulations for the Alternating Current Optimal Power Flow problem

  • Daniel Bienstock
  • Mauro Escobar
  • Claudio Gentile
  • Leo Liberti
    • Categories Energy, Global Optimization Applications, Quadratic Programming Tags , ,

    Power flow refers to the injection of power on the lines of an electrical grid, so that all the injections at the nodes form a consistent flow within the network. Optimality, in this setting, is usually intended as the minimization of the cost of generating power. Current can either be direct or alternating: while the … Read more

    Cycle-based formulations in Distance Geometry

  • Gabriele Iommazzo
  • Carlile Lavor
  • Leo Liberti
  • Nelson Maculan
    • Categories Biomedical Applications, Global Optimization Applications, Quadratic Programming Tags , ,

    The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension K, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision … Read more

    Proximity in Concave Integer Quadratic Programming

  • Alberto Del Pia
  • Mingchen Ma
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming

    A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n∆ on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, n is the number of variables and ∆ denotes the maximum of the absolute values of the subdeterminants of the … Read more

    On monotonicity and search traversal in copositivity detection algorithms

  • Leocadio G Casado
  • Eligius M.T. Hendrix
  • Boglárka Tóth
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , , ,

    Matrix copositivity has an important theoretical background. Over the last decades, the use of algorithms to check copositivity has made a big progress. Methods are based on spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the … Read more

    Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems

  • Giampaolo Liuzzi
  • Marco Locatelli
  • Veronica Piccialli
  • Stefan Rass
    • Categories Game Theory, Global Optimization Applications, Quadratic Programming

    In this paper we address a game theory problem arising in the context of network security. In traditional game theory problems, given a defender and an attacker, one searches for mixed strategies which minimize a linear payoff functional. In the problem addressed in this paper an additional quadratic term is added to the minimization problem. … Read more