Assume we have this strictly convex quadratic programming:

$$f(x) = x^\top A x + b^\top x,$$ $$Ax \leq b$$ $$ 0 \leq x \leq 1$$

Where $A$ is symmetric and positive definite, and the feasible set is nonempty. Does strong duality and Slater's condition holds in this case.

  • 1
    $\begingroup$ you said the feasible set is nonempty, so I do not understand your first question (feasibility means that the optimal value is finite too) $\endgroup$ – LinAlg Jun 30 '18 at 12:25
  • $\begingroup$ you mean the second question, right, since the first one is about the duality? I removed the second question, how about the duality? $\endgroup$ – Faroq AL-Tam Jun 30 '18 at 12:30
  • $\begingroup$ Slater's condition requires a strictly feasible solution. If your linear equalities are such that (e.g.) there is a unique feasible solution then Slater's condition wouldn't be satisfied. Depending on your constraints, other constraint qualifications, such as the linear independence constraint qualification (LICQ), might hold. $\endgroup$ – Brian Borchers Jun 30 '18 at 14:19
  • $\begingroup$ @Brian Borchers All the constraints are linear, that is a constraint qualification. Slater's condition only pertains to nonlinear constraints, so you could say it is trivially satisfied in this case. $\endgroup$ – Mark L. Stone Jun 30 '18 at 15:33
  • $\begingroup$ @MarkL.Stone yes, but I was hoping that the OP could find this out for themselves... $\endgroup$ – Brian Borchers Jun 30 '18 at 15:56

The feasible set is nonempty and compact. The objective is continuous. So by Weirstrass we have a finite optimal value. The constraints and the objective are all convex functions. Finally, since the feasible set is nonempty, we have a vector which satisfies the linear inequalities. Thus we have Slater's condition (linear inequalities do not require strict feasibility). So we also have strong duality.

  • $\begingroup$ Thank you, Does this proof hold if we also have additional equality constraints $Cx = 1$. $\endgroup$ – Faroq AL-Tam Jun 30 '18 at 14:45
  • $\begingroup$ Yes. Equality constraints do not change the compactness of the feasible set nor the fact that Slater's condition holds. $\endgroup$ – Alex Shtof Jun 30 '18 at 21:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.