How to express L1 / L2 regularization as a constraint for the simplex solver?
When optimizing functions with linear relationships, one common method is the simplex solver.
If there are several optimal solutions, the solver stops when it reaches the first. I am looking at a case where there are several solutions that are good and I would like to penalize giving large weights to any one solution.
In e.g. OLS, L1 or L2 regularization would be used to achieve this but I am not sure how to include such a constraint so that it has the desired effect.
Take for example that we are minimizing the following $$ 10 x + 0.5 y + 0.5 z $$ with the constraints $$ x + y <= 0.9 $$ $$ x + y + z = 1 $$
Solving this leads to either y or z = 0.9. How to enforce a constraint that penalizes large variables? (I.e. still prevents y - 0.9 when the relation is $10x + 0.55y + 0.5 x$)
Add a term that penalizes the largest value $x_i$. I.e.
$$ \begin{align} & \min c^Tx + p \cdot z\\ & z \ge x_i \>\> \forall i\\ \end{align} $$