Take the 2-minute tour ×
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.

My question is about the following paper:

http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf

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|improve this question
6  
Maybe it's better if you rewrite your question in a concrete and self-contained way. –  MCH Aug 19 '11 at 18:29
3  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.