Kurt M. Anstreicher

Solving Nonconvex Optimization Problems using Outer Approximations of the Set-Copositive Cone

  • Kurt M. Anstreicher
  • MarkusGabl
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Global Optimization Theory Tags , ,

    We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with conic constraints and cutting planes. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a … Read more

    Solving Two-Trust-Region Subproblems using Semidefinite Optimization with Eigenvector Branching

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    Semidefinite programming (SDP) problems typically utilize the constraint that X-xx’ is PSD to obtain a convex relaxation of the condition X=xx’, where x is an n-vector. In this paper we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx’. This branching technique is related to previous work of Saxeena, … Read more

    Convex Hull Representations for Bounded Products of Variables

  • Kurt M. Anstreicher
  • Samuel Burer
  • Kyungchan Park
    • Categories Convex Optimization, Global Optimization Theory, Second-Order Cone Programming Tags , , ,

    It is well known that the convex hull of {(x,y,xy)}, where (x,y) is constrained to lie in a box, is given by the Reformulation-Linearization Technique (RLT) constraints. Belotti et al. (2010) and Miller et al. (2011) showed that if there are additional upper and/or lower bounds on the product z=xy, then the convex hull can … Read more

    Testing Copositivity via Mixed-Integer Linear Programming

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory Tags , ,

    We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. Citation Dept. of Business … Read more

    Efficient Solution of Maximum-Entropy Sampling Problems

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Statistics Tags , ,

    We consider a new approach for the maximum-entropy sampling problem (MESP) that is based on bounds obtained by maximizing a function of the form ldet M(x) over linear constraints, where M(x)is linear in the n-vector x. These bounds can be computed very efficiently and are superior to all previously known bounds for MESP on most … Read more

    Maximum-Entropy Sampling and the Boolean Quadric Polytope

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , ,

    We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean Quadric Polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the … Read more

    Kronecker Product Constraints for Semidefinite Optimization

  • Kurt M. Anstreicher
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , ,

    We consider semidefinite optimization problems that include constraints that G(x) and H(x) are positive semidefinite (PSD), where the components of the symmetric matrices G(x) and H(x) are affine functions of an n-vector x. In such a case we obtain a new constraint that a matrix K(x,X) is PSD, where the components of K(x,X) are affine … Read more

    Quadratic Programs with Hollows

  • Kurt M. Anstreicher
  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Let $\F$ be a quadratically constrained, possibly nonconvex, bounded set, and let $\E_1, \ldots, \E_l$ denote ellipsoids contained in $\F$ with non-intersecting interiors. We prove that minimizing an arbitrary quadratic $q(\cdot)$ over $\G := \F \setminus \cup_{k=1}^\ell \myint(\E_k)$ is no more difficult than minimizing $q(\cdot)$ over $\F$ in the following sense: if a given semidefinite-programming … Read more

    Second-Order-Cone Constraints for Extended Trust-Region Subproblems

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. In this paper, we consider extensions of TRS having extra constraints. When two parallel cuts are added to TRS, we show that the resulting nonconvex problem has an exact representation as a semidefinite program with additional linear and second-order-cone constraints. For … Read more