Constraint Relax Then Tighten

---
name: constraint-relax-then-tighten
description: 约束先放后紧的方法论。核心思想：先放宽约束条件证明解的存在性，然后逐步收紧约束，逼近原始问题。适用于复杂约束系统的控制和规划问题。触发词：约束放松、约束收紧、feasibility、存在性证明、约束控制、constraint relaxation、progressive tightening、约束规划。
---

# 约束先放后紧方法论

## Description

通过放松-收紧策略处理复杂约束问题：先放宽约束证明可行性，再逐步收紧至原问题。

## Activation Keywords

- 约束放松
- 约束收紧
- feasibility
- 存在性证明
- 约束控制
- constraint relaxation
- progressive tightening
- 约束规划
- 先放后紧

## Tools Used

- exec
- read
- write

## Instructions for Agents

当用户遇到复杂约束优化问题时，按以下步骤引导：

1. **识别约束类型**：分析等式/不等式约束，判断凸性
2. **选择放松策略**：惩罚函数、容忍度放宽或软约束替代
3. **证明存在性**：在放松条件下验证解的存在
4. **逐步收紧**：使用收紧因子 γ 迭代逼近原问题
5. **验证收敛**：确认最终解满足原始约束

## Examples

User: 我有一个机器人路径规划问题，障碍物约束太多导致无法求解。

Agent: 这是典型的复杂约束问题，建议使用先放后紧策略：
1. 先将障碍物硬约束放松为软约束（惩罚函数），找到初始可行路径
2. 逐步增大惩罚系数，使路径远离障碍物
3. 最终收紧到满足安全距离要求

## 核心思想

复杂约束问题往往难以直接求解：
1. **可行域可能为空** - 约束相互冲突
2. **最优性难以保证** - 非凸、非光滑
3. **计算复杂度高** - NP-hard 约束

**策略**：放宽 → 存在性证明 → 逐步收紧 → 原问题

## 方法框架

### 1. 约束放松策略

将原问题：
```
min  f(x)
s.t. g_i(x) ≤ 0, i = 1, ..., m
     h_j(x) = 0, j = 1, ..., p
```

转化为放松问题：
```
min  f(x) + Σ_i ρ_i * max(0, g_i(x))
s.t. h_j(x) = 0  (或放松为 ||h_j(x)|| ≤ δ)
```

或更激进的放松：
```
min  f(x)
s.t. g_i(x) ≤ ε_i, ε_i > 0  (放宽容忍度)
```

### 2. 存在性证明

放松后需要证明：
- **可行解存在**: 找到 x_0 使得放松约束成立
- **解的连续性**: 放松参数 → 0 时解收敛
- **稳定性**: 小扰动不破坏解

常用技术：
- **Weierstrass 定理**: 紧集上连续函数必有极值
- **Leray-Schauder 不动点**: 证明方程解存在
- **变分方法**: 证明泛函极小值存在

### 3. 逐步收紧算法

```
输入: 原问题 P, 初始放松参数 ε_0, 收紧因子 γ ∈ (0,1)
输出: 近似可行解 x*

初始化: ε = ε_0, x = x_0 (放松问题的解)

while ε > ε_min:
    # 收紧放松参数
    ε = γ * ε
    
    # 在更紧约束下求解
    x = solve_relaxed_problem(P, ε)
    
    # 验证可行性
    if not feasible(x, ε):
        # 回退或调整策略
        ε = ε / γ  # 回退
        γ = γ * 0.9  # 减缓收紧速度
        continue

return x* = x
```

### 4. Reflected MFG 示例

来源论文中的约束处理：

原问题包含反射边界条件：
```
dX_t = b(t, X_t, μ_t) dt + σ dW_t - dK_t
X_t ∈ D  (状态约束)
```

放松策略：
```
# 软约束替代硬约束
L(x) = penalty * distance(x, D^c)
min E[∫ L(X_t) dt]
```

逐步收紧：
- 初始: penalty = P_0
- 每轮: penalty = λ * penalty, λ > 1
- 终止: penalty ≥ P_max 或 解收敛

## 应用场景

| 场景 | 放松策略 | 收紧方式 |
|------|----------|----------|
| 机器人避障 | 软约束 + 惩罚函数 | 增大惩罚系数 |
| 资源分配 | 容忍超量分配 | 减小容忍度 |
| 路径规划 | 放宽时间窗约束 | 收紧时间限制 |
| 能源调度 | 允许功率波动 | 减小波动范围 |
| 投资组合 | 放宽风险约束 | 收紧风险上限 |

## 实现要点

### 惩罚函数选择

```python
# 外点惩罚函数
def penalty_exterior(g, rho):
    """g(x) ≤ 0 的外点惩罚"""
    return rho * max(0, g)**2

# 内点障碍函数
def barrier_interior(g, mu):
    """g(x) ≤ 0 的内点障碍"""
    return -mu * log(-g)

# 混合策略
def hybrid_penalty(g, rho, mu):
    """结合外点和内点"""
    return penalty_exterior(g, rho) + barrier_interior(g, mu)
```

### 收敛性分析

**定理**: 设放松问题 P_ε 的解为 x(ε)。若：
1. 原问题 P 有唯一解 x*
2. f 和 g_i Lipschitz 连续
3. Slater 条件成立

则当 ε → 0 时：
- x(ε) → x*
- f(x(ε)) → f(x*)

### 数值稳定性

```python
# 避免 penalty 爆炸
def stable_penalty(g, rho, max_penalty=1e10):
    p = rho * max(0, g)**2
    return min(p, max_penalty)

# 自适应收紧
def adaptive_tightening(current_violation, rho):
    """根据当前违反程度调整收紧速度"""
    if current_violation < 0.1 * target:
        return rho * 2.0  # 加快收紧
    elif current_violation > target:
        return rho * 1.1  # 减慢收紧
    return rho * 1.5
```

## 参数调优指南

| 参数 | 推荐范围 | 影响 |
|------|----------|------|
| 初始放松 ε_0 | 0.1 ~ 1.0 | 太大导致偏离，太小可能不可行 |
| 收紧因子 γ | 0.5 ~ 0.9 | 太快导致不收敛，太慢效率低 |
| 惩罚系数 ρ | 10 ~ 1000 | 需逐步增大 |
| 收敛阈值 | 1e-4 ~ 1e-6 | 平衡精度和计算成本 |

## 与其他方法的对比

| 方法 | 适用问题 | 优点 | 缺点 |
|------|----------|------|------|
| 直接求解 | 简单凸约束 | 简单直接 | 不可行域失败 |
| 罚函数法 | 一般约束 | 无需可行初始点 | 罚系数敏感 |
| 内点法 | 凸约束 | 收敛快 | 需要严格内点 |
| 先放后紧 | 复杂非凸 | 保证存在性 | 多次迭代 |

## 参考文献

- Reflected Mean-Field Games and Constrained Optimization (2024)
- Progressive Constraint Tightening for MPC
- Augmented Lagrangian Methods for Constrained Optimization