Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My question is about the following paper:

In section 2 they show Equation 3 (which is just an optimization problem), which they transform into the optimization problem right before section 3. Everything is very easy to read and self-contained. However, I do not understand how they can tell so easily that the constraints in the convex program are tight (which allows them to transform the program to the one before section 3). Are they relying on some result that they are not saying, or is this a very simple argument coming from optimization?

An edit, following a request to rewrite the question in a self-contained way. Let $w \in R^d$ and $y_i \in R^d$ and $A_i$ be a finite set of vectors in $R^d$. Consider the following optimization problem:

$\min_{w,\xi} ||w||_2^2 + \sum_i \xi_i$

under the constraints that $\forall i$ we have $w^T y_i + \xi_i \ge \max_{y \in A_i} \left( w^T y \right)$

why in any solution of this optimization problem, the constraints are tight, so that we can reformulate the optimization problem by replacing $\xi_i$ with $\max_{y \in A_i} \left(w^T y \right) - w^T y_i$ and get rid of the constraints?

share|cite|improve this question
Maybe it's better if you rewrite your question in a concrete and self-contained way. – MCH Aug 19 '11 at 18:29
Another edit suggestion: a more descriptive and less ambiguous title! Something that contains words like optimization and maybe instead of 'paper' says 'RatliffBagnellZinkevic2007' to draw the attention of those familiar with the paper. – Artem Kaznatcheev Aug 20 '11 at 1:45

Well, if any constraint is loose you can just decrease the corresponding $\xi_i$ until the constraint becomes tight, in which case you are only decreasing the objective value and get a better solution.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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