Skip to main content
added 118 characters in body
Source Link
Noah Stein
  • 8.5k
  • 1
  • 34
  • 56

Edited in response to Alex Monras's correction in the comments:

The cone $\mathcal{K}^*$ is always SDR: this is just the conic / homogeneous version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

As for the proof, it consists of writing the semidefinite program: minimize $Y\bullet X$ subject to $X\in\mathcal{K}$. This is always feasible (take $X=0$) and so has optimum either $0$ or $-\infty$. Take the usual dual semidefinite program, which has. If strong duality holds (e.g. there is an $(x,y)$ pair making the same value underconstraint strictly positive definite), the various assumptions you made. This dual has zero objective and the set of $Y$ for which it is feasible defines exactly the semidefinite representation of $\mathcal{K}^*$.

To get the same resultshow $\mathcal{K} ^ * $ is SDR without imposing a constraint qualification like the assumptionsSlater condition, you need an extended dual SDP construction like the one proposed by Ramana. In either case, working through the details of the proof will (at least in principle) give the precise form of the representation for $\mathcal{K}^*$, which can be derived syntactically from the representation for $\mathcal{K}$.

The cone $\mathcal{K}^*$ is always SDR: this is just the conic / homogeneous version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

As for the proof, it consists of writing the semidefinite program: minimize $Y\bullet X$ subject to $X\in\mathcal{K}$. This is always feasible (take $X=0$) and so has optimum either $0$ or $-\infty$. Take the usual dual semidefinite program, which has the same value under the various assumptions you made. This dual has zero objective and the set of $Y$ for which it is feasible defines exactly the semidefinite representation of $\mathcal{K}^*$.

To get the same result without the assumptions, you need an extended dual SDP construction like the one proposed by Ramana. In either case, working through the details of the proof will give the form of the representation for $\mathcal{K}^*$, which can be derived syntactically from the representation for $\mathcal{K}$.

Edited in response to Alex Monras's correction in the comments:

The cone $\mathcal{K}^*$ is always SDR: this is just the conic / homogeneous version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

As for the proof, it consists of writing the semidefinite program: minimize $Y\bullet X$ subject to $X\in\mathcal{K}$. This is always feasible (take $X=0$) and so has optimum either $0$ or $-\infty$. Take the usual dual semidefinite program. If strong duality holds (e.g. there is an $(x,y)$ pair making the constraint strictly positive definite), the dual has zero objective and the set of $Y$ for which it is feasible defines exactly the semidefinite representation of $\mathcal{K}^*$.

To show $\mathcal{K} ^ * $ is SDR without imposing a constraint qualification like the Slater condition, you need an extended dual SDP construction like the one proposed by Ramana. In either case, working through the details of the proof will (at least in principle) give the precise form of the representation for $\mathcal{K}^*$.

added 793 characters in body
Source Link
Noah Stein
  • 8.5k
  • 1
  • 34
  • 56

The cone $\mathcal{K}^*$ is always SDR: this is just the conic / homogeneous version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

As for the proof, it consists of writing the semidefinite program: minimize $Y\bullet X$ subject to $X\in\mathcal{K}$. This is always feasible (take $X=0$) and so has optimum either $0$ or $-\infty$. Take the usual dual semidefinite program, which has the same value under the various assumptions you made. This dual has zero objective and the set of $Y$ for which it is feasible defines exactly the semidefinite representation of $\mathcal{K}^*$.

To get the same result without the assumptions, you need an extended dual SDP construction like the one proposed by Ramana. In either case, working through the details of the proof will give the form of the representation for $\mathcal{K}^*$, which can be derived syntactically from the representation for $\mathcal{K}$.

The cone $\mathcal{K}^*$ is always SDR: this is just the conic version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

The cone $\mathcal{K}^*$ is always SDR: this is just the conic / homogeneous version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.

As for the proof, it consists of writing the semidefinite program: minimize $Y\bullet X$ subject to $X\in\mathcal{K}$. This is always feasible (take $X=0$) and so has optimum either $0$ or $-\infty$. Take the usual dual semidefinite program, which has the same value under the various assumptions you made. This dual has zero objective and the set of $Y$ for which it is feasible defines exactly the semidefinite representation of $\mathcal{K}^*$.

To get the same result without the assumptions, you need an extended dual SDP construction like the one proposed by Ramana. In either case, working through the details of the proof will give the form of the representation for $\mathcal{K}^*$, which can be derived syntactically from the representation for $\mathcal{K}$.

Source Link
Noah Stein
  • 8.5k
  • 1
  • 34
  • 56

The cone $\mathcal{K}^*$ is always SDR: this is just the conic version of Theorem 5.57 in the new book "Semidefinite Optimization and Convex Algebraic Geometry" by Blekherman, Parrilo, and Thomas. This book is also a good source for more background about this field.