Return to Answer

As (almost) always in parametric programming, you have to encode optimality of $x$ using optimality conditions.

$c + A(y)^T\lambda=0, \lambda^T(b-A(y)x)=0, \lambda\geq 0,b-A(y)x\geq 0$

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric programming is hard, and as you probably realized, parametric programming with parametric $A$ is even harder as it doesn't retain the polytopic properties of linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

Note that optimality leads us to trilinear inequalities, the discussion about QCQPs etc is thus not really relevant.

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since with these fixed values of $y$ the LP will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).

As (almost) always in parametric programming, you have to encode optimality of $x$, for a given $y$, using optimality conditions.

$c + A(y)^T\lambda=0$ (stationarity)

$\lambda^T(b-A(y)x)=0$ (complementarity)

$\lambda\geq 0,b-A(y)x\geq 0$ (dual and primal feasibility)

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, effectively solving a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric/bilevel programming is hard, and as you probably realized, with parametric $A$ is even harder as it doesn't retain the polytopic properties of parametric linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

EDIT By using the stationarity constraint in the complementarity constraint, bilinear constraints arise (still nonconvex of-course)

$c + A(y)^T\lambda=0$ (stationarity)

$\lambda^Tb + c^Tx=0$ (rewritten complementarity)

$\lambda\geq 0,b-A(y)x\geq 0$ (dual and primal feasibility)

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution in $(x,y)$ to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since with these fixed values of $y$ the LP will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, over $x$ and $y$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).

As (almost) always in parametric programming, you have to encode optimality of $x$ using optimality conditions.

$c + A(y)^T\lambda=0, \lambda^T(b-A(y)x)=0, \lambda\geq 0,b-A(y)x\geq 0$

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric programming is hard, and as you probably realized, parametric programming with parametric $A$ is even harder as it doesn't retain the polytopic properties of linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

Note that optimality leads us to trilinear inequalities, the discussion about QCQPs etc is thus not really relevant.

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since these $y$ will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).

As (almost) always in parametric programming, you have to encode optimality of $x$ using optimality conditions.

$c + A(y)^T\lambda=0, \lambda^T(b-A(y)x)=0, \lambda\geq 0,b-A(y)x\geq 0$

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric programming is hard, and as you probably realized, parametric programming with parametric $A$ is even harder as it doesn't retain the polytopic properties of linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

Note that optimality leads us to trilinear inequalities, the discussion about QCQPs etc is thus not really relevant.

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since with these fixed values of $y$ the LP will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).

As (almost) always in parametric programming, you have to encode optimality of $x$ using optimality conditions.

$c + A(y)^T\lambda=0, \lambda^T(b-A(y)x)=0, \lambda\geq 0,b-A(y)x\geq 0$

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric programming is hard, and as you probably realized, parametric programming with parametric $A$ is even harder as it doesn't retain the polytopic properties of linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

Note that optimality leads us to trilinear inequalities, the discussion about QCQPs etc is thus not really relevant.

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ for simplicity), minimize $x$ subject to $x\geq y$. The optimal solution to this problem, with the positivity requirement on any optimal $x$, is $x=y=0$ (the feasible set in $y$ is the positive orthant, since these $y$ give non-negative optimal solutions). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, the optimal solution is $x=0$ and $y$ any non-positive number. Now, plugging in this non-positive number (-2 for example) into the original problem, will lead to an infeasible $x$ (-2).

As (almost) always in parametric programming, you have to encode optimality of $x$ using optimality conditions.

$c + A(y)^T\lambda=0, \lambda^T(b-A(y)x)=0, \lambda\geq 0,b-A(y)x\geq 0$

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric programming is hard, and as you probably realized, parametric programming with parametric $A$ is even harder as it doesn't retain the polytopic properties of linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

Note that optimality leads us to trilinear inequalities, the discussion about QCQPs etc is thus not really relevant.

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since these $y$ will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).