如何线性化二次目标函数？含线性约束的优化问题咨询

Nice question! Let's walk through how to linearize your quadratic objective function step by step. First, let's restate your goal clearly: you want to maximize Max ∑(k=1 to K) ∑(t=1 to T) [r_k(t)]², with all constraints being linear in the r_k(t) variables.

Key Background #

The sum of squares is a convex function, and maximizing a convex function over a convex feasible region (defined by linear constraints) means the optimal solution will lie at an extreme point of the feasible region. But to convert this into a linear problem, we need to handle the squared terms—here are the most practical approaches:

Approach 1: Approximate Linearization (Continuous Variables Only) #

If you can tolerate a small amount of approximation (and don’t want to use integer variables), a piecewise linear approximation works well:

1. Define variable bounds: First, find the lower bound L_{k,t} and upper bound U_{k,t} for each r_k(t). You can get these by solving two quick linear programs for each variable:
   • Minimize r_k(t) (under your linear constraints) to get L_{k,t}
   • Maximize r_k(t) (under your linear constraints) to get U_{k,t}
2. Split the interval into segments: Divide [L_{k,t}, U_{k,t}] into n segments (more segments = higher accuracy). Let the split points be x₀ = L_{k,t}, x₁, x₂, ..., xₙ = U_{k,t}.
3. Introduce auxiliary variables:
   • For each k,t, define s_{k,t} to represent [r_k(t)]²
   • Define weight variables λ_{k,t,i} ≥ 0 for each segment point x_i
4. Add linear constraints:
   • r_k(t) = ∑_{i=0}^n λ_{k,t,i} * x_i
   • ∑_{i=0}^n λ_{k,t,i} = 1
   • s_{k,t} = ∑_{i=0}^n λ_{k,t,i} * x_i²
5. Update the objective: Your new linear objective is Maximize ∑(k=1 to K) ∑(t=1 to T) s_{k,t}

This approximates the squared term using a convex combination of the squared split points—perfect for getting a close enough solution without integer complexity.

Approach 2: Exact Linearization (Mixed-Integer Linear Programming) #

If you need an exact optimal solution, you’ll need to introduce 0-1 integer variables to model the piecewise linear relationship precisely:

1. Same first step as above: Get bounds L_{k,t} and U_{k,t} for each r_k(t), and split [L_{k,t}, U_{k,t}] into segments [x₀,x₁], [x₁,x₂], ..., [xₙ₋₁,xₙ].
2. Add integer and auxiliary variables:
   • For each segment i of r_k(t), add a 0-1 variable z_{k,t,i} (1 if r_k(t) lies in segment i, 0 otherwise)
   • Add a continuous variable θ_{k,t,i} to represent the position within segment i
3. Add linear constraints:
   • ∑_{i=0}^{n-1} z_{k,t,i} = 1 (only one segment is active per variable)
   • r_k(t) = x_i + θ_{k,t,i} * (x_{i+1} - x_i) for each segment i
   • 0 ≤ θ_{k,t,i} ≤ z_{k,t,i} (θ is only non-zero if the segment is active)
   • s_{k,t} = x_i² + θ_{k,t,i} * (x_{i+1}² - x_i²) for each segment i
4. Linear objective: Again, use Maximize ∑(k=1 to K) ∑(t=1 to T) s_{k,t}

This setup exactly captures the squared term by forcing the model to pick the correct segment and compute the square linearly within that segment.

Special Case: Non-Negative r_k(t) #

If your problem guarantees r_k(t) ≥ 0, the squared function is monotonic increasing over its domain. You can simplify the above approaches by only considering non-negative split points, but the core logic remains the same.

Important Note #

You must have bounds for each r_k(t) to use either method—without knowing the variable’s range, you can’t create valid linear constraints to represent the squared term.

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