<p>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.</p>

CC BY-SA 3.0
2011-08-19T20:02:23.927Z
2011-08-19T20:02:23.927Z
Mahdi Cheraghchi
<p>My question is about the following paper:</p>

<p><a href="http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf" rel="nofollow">http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf</a></p>

<p>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?</p>

<p>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 <em>finite</em> set of vectors in $R^d$.
Consider the following optimization problem:</p>

<p>$\min_{w,\xi} ||w||_2^2 + \sum_i \xi_i$</p>

<p>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)$</p>

<p>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?</p>

CC BY-SA 3.0
2011-08-19T18:29:53.750Z
Maybe it's better if you rewrite your question in a concrete and self-contained way.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-20T01:45:51.803Z
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
<ds.algorithms><optimization><convex-optimization>
why are the constraints in the following paper tight?
gmmodeler
# why are the constraints in the following paper tight?

(Asked by: username_0 on 2011-08-19)

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?

**Tags:** ds.algorithms, optimization, convex-optimization

> **Comments:**
> **username_1**: Maybe it's better if you rewrite your question in a concrete and self-contained way.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_1 on 2011-08-19. Score: 2

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.


---

