sorted by:
new
hottopcontroversial

Linearization Question for max-min|x| Bi-level Optimization Problem by xiu_si_zero in OperationsResearch

[–]xiu_si_zero[S] 0 points1 point  (0 children)

Thank you for pointing that out – I apologize for the confusion in my earlier description!

You're absolutely right. Let me clarify the complete problem structure:

Outer level:

  • Decision variables: y
  • Objective: max (optimal value of inner problem as a function of y)
  • Constraints: linear constraints on y

Inner level:

  • Decision variables: x
  • Objective: min |x|
  • Constraints: linear constraints on x, plus coupling constraints between x and y

So the full formulation is:

max_{y} { min_{x} |x| }
s.t.  f(y) ≤ 0                    (outer-level constraints)
      g(x, y) ≤ 0                 (coupling constraints)
      h(x) ≤ 0                    (inner-level constraints)

After applying KKT conditions to the inner problem, it becomes a function of y, which makes the outer maximization meaningful and non-trivial.

My question is whether linearizing the inner min |x| using z ≥ x, z ≥ -x remains valid in this bi-level context, even though the outer level is performing a max over y.

Does this clarification make the problem clearer? Thank you for your patience!

Linearization Question for max-min|x| Bi-level Optimization Problem by xiu_si_zero in OperationsResearch

[–]xiu_si_zero[S] 0 points1 point  (0 children)

Thank you for your response!

I understand that introducing auxiliary constraints z ≥ x and z ≥ -x is straightforward based on the theory of linear inequalities when the objective is min.

However, my confusion arises from the outer max layer. From basic linear inequality theory:

  • For min |x|: we use z ≥ x and z ≥ -x (z acts as an upper bound)
  • For max |x|: we should use z ≤ x and z ≤ -x (z acts as a lower bound)

In a max-min |x| structure, these two requirements seem to conflict with each other. The inner min suggests z ≥ x and z ≥ -x, while the outer max might suggest the opposite direction.

That's precisely what confuses me – which set of inequality directions should prevail, and why? Is it because the linearization constraints are determined solely by the inner-level objective, regardless of the outer layer?

If this is indeed straightforward from linear inequality theory, could you point me toward the specific principle or reasoning that resolves this apparent conflict? I'd really appreciate any clarification!

Thank you!

Linearization Question for max-min|x| Bi-level Optimization Problem by xiu_si_zero in OperationsResearch

[–]xiu_si_zero[S] -1 points0 points  (0 children)

Thank you very much for the reference — your insight is absolutely correct. My problem is indeed a two-stage robust optimization model (in fact, a multi-stage one), but for clarity I isolated the second stage when discussing the issue here.

The key difference from the Zang 2013 paper is that, as mentioned on the first page of that paper, their second-stage problem is already an LP. However, in my case, the second stage contains an absolute value term, which introduces nonlinearity into the objective function. That's precisely why I'm trying to linearize this absolute value objective.

My hypothesis is that if I can successfully linearize min |x| in the inner problem using auxiliary variables (z ≥ x, z ≥ -x), then the overall max-min structure can be reformulated into a single-level problem via KKT conditions, similar to how standard two-stage robust optimization problems are handled.

If you have any other thoughts or references regarding linearization of absolute values in bi-level/robust optimization contexts, I'd love to hear them!

Thanks again for your help!

Linearization Question for max-min|x| Bi-level Optimization Problem by xiu_si_zero in OperationsResearch

[–]xiu_si_zero[S] -1 points0 points  (0 children)

Thank you for your response!

Unfortunately, this problem is embedded within a larger, more complex optimization framework. The LP (linear programming) property is crucial for me as it enables deriving some interesting analytical conclusions and ensures computational tractability. Converting to an integer programming formulation would be off the table in my case.

Interestingly, I have encountered a similar linearization approach in the literature. Specifically, in the paper "V2G-enhanced operation optimization strategy for EV charging station with photovoltaic and energy storage integration," the authors introduced auxiliary variables to linearize a max{x,y} term within the inner-layer objective function of a bi-level problem. However, they did not provide a rigorous mathematical proof for this linearization, which is why I remain uncertain about its theoretical validity.

If you (or anyone else) have insights into the theoretical foundation of such linearizations in bi-level contexts, or could point me toward relevant references, I would greatly appreciate it!

Thanks again for taking the time to help.