Skip to main content

Semidefinite programming

Awaiting user input

Comments

2 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    The SDP plugin should be able to solve non mixed-integer SDPs as well, since it uses Mosek, DSDP, or SDPA as subsolver, which are able to solve continuous SDPs. Did you have a change to try it out?

    0
  • Aron Zingler
    Conversationalist
    Gurobi-versary
    First Question

    A cutting-plane approach can be quite beneficial in certain scenarios. This method involves iteratively formulating Mixed-Integer Linear Programs (MILPs) and solving them using tools like Gurobi.

    While more advanced methods exist, a fundamental approach begins by initially disregarding the Semidefinite Programming (SDP) constraints imposed by matrix semidefiniteness. Instead, it solves the resulting MILP. If the solution satisfies the SDP constraints, it provides a valid solution, thereby completing the process. If not, constraints are added for each matrix \( A \) supposed to be positive definite, specifically requiring that \( \mathbf{v}^T A \mathbf{v} \geq 0 \), where \( \mathbf{v} \) is the eigenvector corresponding to the most negative eigenvalue of \( A \).

    In general, it's important to note that this method does not guarantee obtaining a truly feasible solution, but each iteration typically produces a solution that is slightly less infeasible. However, it is advisable only when dedicated solvers specifically designed for solving mixed integer linear SDP problems are not available.

    0

Please sign in to leave a comment.