1
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ Maybe it's better if you rewrite your question in a concrete and self-contained way. $\endgroup$ – MCH Aug 19 '11 at 18:29
  • 3
    $\begingroup$ 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. $\endgroup$ – Artem Kaznatcheev Aug 20 '11 at 1:45
2
$\begingroup$

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.

$\endgroup$

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.