2
$\begingroup$

I'm a physicist and I'm working on a problem that can be reduced to a SDP problem. My problem is: is there a theorem that assures that the result of an optimization saturates the constraint instead of only satisfying it? An example is the elliptope of $x$, $y$, $z$ variables and maximize a linear functional of these variables. Can we assure that we will always saturate the constraint that yields the elliptope?

$\endgroup$
  • 1
    $\begingroup$ Consider the 1D SDP, minimize $(x-1)^2$, subject to $x \ge 0$. The optimal solution is x = 1, and the constraint is not active there. So please clarify your question to exclude this counterexample. More generally, the optimal solution of an SDP might be strictly in the interior of the feasible region. $\endgroup$ – Mark L. Stone Apr 9 at 15:30
  • $\begingroup$ Unlike your case I want to maximize/minimize linear functionals with non-linear constraints given by a semi-definite positive condition. So I would exclude you example. $\endgroup$ – bethe_ansatz Apr 9 at 15:34
  • $\begingroup$ Do you exclude minimize $- x$ subject to $x \ge 0$, which is unbounded? How about minimize $x$ subject to $x \ge 0, x = 1$, which has optimal solution $x = 1$. at which the SDP constraint $x \ge 0$ is not active? There are of course less trivial examples for 2 or more dimensional problems. $\endgroup$ – Mark L. Stone Apr 9 at 15:52
  • 1
    $\begingroup$ @bethe_ansatz Like Jose said, welcom to MSE! Could you edit your question to give the explicit type of problem you are looking at (an example is fine). I assume when you say 'saturates the contraint,' you mean 'equality is achieved, right? $\endgroup$ – Strants Apr 9 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.