如何为单纯形求解器添加正则化？如何将L1/L2正则化表示为约束？

Awesome question—this is a common scenario when dealing with linear programming and multiple optimal solutions, and framing it through the lens of OLS regularization is a great way to approach it! Let’s break down how to adapt these penalty ideas to work with a simplex solver (or adjust your approach if needed):

1. L1 (Lasso-like) Penalty: Keep It Linear for Simplex #

L1 regularization penalizes the absolute sum of weights, which pushes solutions toward sparsity (fewer large variables). Since simplex solvers only handle linear problems, we need to eliminate the absolute value by splitting variables:

• For each variable x_i, split it into two non-negative components: x_i = x_i^+ - x_i^- where x_i^+ ≥ 0 and x_i^- ≥ 0
• The L1 penalty becomes λ * Σ(x_i^+ + x_i^-) (this avoids absolute values while capturing the same penalty effect)
• Update your original objective function to:

  Minimize: c^T x + λ * Σ(x_i^+ + x_i^-)
  Subject to:
    Ax = b
    x_i = x_i^+ - x_i^-  for all i
    x_i^+, x_i^- ≥ 0
    x ≥ 0 (if your original variables are non-negative)
  

This transformed problem is fully linear, so a standard simplex solver can handle it. Tweak the λ parameter to control penalty strength—bigger λ means more pressure to keep individual weights small.

2. L2 (Ridge-like) Penalty: Know When to Switch Tools #

L2 regularization adds a squared term (λ * Σx_i²) to the objective, which makes the problem a quadratic program (QP) instead of linear. Simplex solvers aren’t built for QPs, so you have two paths:

Option A: Use a Quadratic Programming Solver #

If you can switch from a pure simplex solver to a QP solver (most modern optimization libraries support both), you can directly add the L2 term:

Minimize: c^T x + λ * Σx_i²
Subject to:
  Ax = b
  x ≥ 0

QP solvers handle convex quadratic objectives efficiently, and this will penalize large individual weights exactly like ridge regression.

Option B: Linear Approximation (Workaround) #

If you must stick with simplex, you can approximate the squared term with piecewise linear segments. This is a hack, though—you’ll lose precision, and it gets messy with many variables. Only use this if switching solvers isn’t an option.

3. Alternative: Lexicographic Optimization (No Penalty Term Needed) #

If you don’t want to add a penalty term at all, you can use lexicographic ordering to prioritize balanced solutions:

1. First, solve your original linear program to get the optimal objective value f*
2. Then solve a second LP where you minimize the sum (or maximum) of your variables, while forcing the original objective to stay at f*:

Minimize: Σx_i  # Or use max(x_i) (linearize with an auxiliary variable if needed)
Subject to:
  Ax = b
  c^T x = f*
  x ≥ 0

This finds the optimal solution that also has the smallest possible total weight (or smallest individual weight), which achieves your goal of avoiding lopsided solutions without adding a regularization parameter.

Quick Tips #

• Pick L1 if you want sparsity (some variables go to zero), L2 if you just want all weights to stay small, or lexicographic if you prefer avoiding penalty tuning.
• Test λ values carefully—too big, and the penalty will override your original objective; too small, and you won’t see any change in the solutions.

内容的提问来源于stack exchange，提问作者Edgar H