Decision Variables becoming Constraints

Question

Consider a convex optimization problem with decision variable x. Though I'm interested in answers for any kind of convex optimization problem, let's say it's an LP, so we have something like:

\begin{equation*} \begin{array}{ll@{}ll} \text{min} & \displaystyle c^\text{T}x \\ \text{s.t.} & \displaystyle Ax\geq b \\ & x \geq 0 \end{array} \end{equation*}

Now let's say I have a second linear program where the constraint variables are defined by the decision variables of the first, i.e. the $x$ in what follows is the argmin of the preceding problem:

\begin{equation*} \begin{array}{ll@{}ll} \text{min} & \displaystyle d^\text{T}y \\ \text{s.t.} & \displaystyle By\geq x \\ \end{array} \end{equation*}

You could continue this chain of dependencies ad nauseam. This looks like it could be a common situation, where the decisions you make for one problem influence the feasible solutions of another, but I'm having a hard time finding examples in the literature. Possible examples that spring to mind include inventory management where you buy x units of something, and then use those x units to achieve some other goal $d^\text{T}y$, or optimal control where $c^Tx$ is a decision made at timestep $t$ and $d^Ty$ is a decision made a timestep $t+1$. But again I can't find any problems in this specific form.

Can anyone point me to some previously studied (class of) optimization problem where this setup arises?

Answer 1

This structure can arise in multi-objective optimization problems. While it is common for multi-objective problems to express each objective function directly in terms of the same variables, there can be instances where the objectives are computed via secondary / chained problems.

It also arises in stochastic programming with recourse, where the first stage model makes decisions in the face of uncertainty and the second stage model figures out how to handle the consequences of the first stage decisions. For instance, the first stage model might make production decisions in the face of uncertainty about demand, and the second stage problem might figure out the best way to deal with any shortfalls or overproduction.

Although I suspect this will not be helpful in your case, the structure you mention is similar (when things are linear) but not identical to Benders decomposition and the recent extensions of Benders. The fundamental difference is that with Benders decomposition the solution to the second problem is used to modify the first model (adding constraints), after which the first problem is solved again.