Linear, Cone and Semidefinite Programming

Computational and Economic Limitations of Dispatch Operations in the Next-Generation Power Grid

  • Audun Botterud
  • Emil M. Constantinescu
  • Victor M. Zavala
  • Jianhui Wang
    • Categories Dynamic Programming, Linear Programming, Production and Logistics Tags , , , , ,

    We study the interactions between computational and economic performance of dispatch operations under highly dynamic environments. In particular, we discuss the need for extending the forecast horizon of the dispatch formulation in order to anticipate steep variations of renewable power and highly elastic loads. We present computational strategies to solve the increasingly larger optimization problems … Read more

    On Doubly Positive Semidefinite Programming Relaxations

  • Dongdong Ge
  • Yinyu Ye
    • Categories Quadratic Programming, Semi-definite Programming Tags ,

    Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the … Read more

    The Approach of Moments for Polynomial Equations

  • Monique Laurent
  • Philipp Rostalski
    • Categories Semi-definite Programming Tags , , ,

    In this article we present the moment based approach for computing all real solutions of a given system of polynomial equations. This approach builds upon a lifting method for constructing semidefinite relaxations of several nonconvex optimization problems, using sums of squares of polynomials and the dual theory of moments. A crucial ingredient is a semidefinite … Read more

    Elementary optimality conditions for nonlinear SDPs

  • Florian Jarre
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags ,

    The goal of this paper is an easy and self-contained presentation of optimality conditions for nonlinear semidefinite programs concentrating on the differences between nonlinear semidefinite programs and nonlinear programs. CitationTechnical Report, Department of Mathematics, Universit\”at D\”usseldorf.ArticleDownload View PDF

    On convex relaxations for quadratically constrained quadratic programming

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

    We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let F denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on F is dominated by an alternative … Read more

    The state-of-the-art in conic optimization software

  • Hans D Mittelmann
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , ,

    This work gives an overview over the major codes available for the solution of linear semidefinite (SDP) and second-order cone (SOCP) programs. Some developments since the 7th DIMACS Challenge [9, 17] are pointed out as well as some currently under way. Instead of presenting per- formance tables, reference is made to the ongoing benchmark [19] … Read more

    On semidefinite programming relaxations of maximum k-section

  • Etienne de Klerk
  • Cristian Dobre
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We derive a new semidefinite programming bound for the maximum k-section problem. For k=2 (i.e. for maximum bisection), the new bound is least as strong as the well-known bound by Frieze and Jerrum [A. Frieze and M. Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica, 18(1): 67-81, 1997]. For k > 2 … Read more

    Relaxations of combinatorial problems via association schemes

  • Etienne de Klerk
  • Fernando Mário de Oliveira Filho
  • Dmitrii V. Pasechnik
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    In this chapter we study a class of semidefinite programming relaxations of combinatorial problems. These relaxations are derived using the theory of coherent configurations in algebraic combinatorics. CitationDraft version of a chapter for “Handbook on SDP II” (M. Anjos and J. Lasserre, eds.), Springer.ArticleDownload View PDF

    Complementarity Problems over Symmetric Cones: A Survey of Recent Developments in Several Aspects

  • Akiko Yoshise
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , ,

    The complementarity problem over a symmetric cone (that we call the Symmetric Cone Complementarity Problem, or the SCCP) has received much attention of researchers in the last decade. Most of studies done on the SCCP can be categorized into the three research themes, interior point methods for the SCCP, merit or smoothing function methods for … Read more

    SDP relaxations for some combinatorial optimization problems

  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this chapter we present recent developments on solving various combinatorial optimization problems by using semidefinite programming (SDP). We present several SDP relaxations of the quadratic assignment problem and the traveling salesman problem. Further, we show the equivalence of several known SDP relaxations of the graph equipartition problem, and present recent results on the bandwidth … Read more