We are given a quadratic (or linear) program as$$\min \limits _xx^TPx+q^Tx\qquad \text{s.t.}\quad a_i^tx\leq b_i,\quad \forall i\in \{1,\ldots ,N\}.$$In the above problem, we do not have any limit on the decision variables.
I want to find the decision variable limit for the above problem i.e. $x\in [\![x_\min ,x_\max ]\!]$ such that the optimization problem always yields a solution, even if we manually add or delete the constraints.
Please do let me know if my thought process is correct or if there is a better problem to approach this problem.
I know that the resulting solution will satisfy the KKT condition. If we suppose that only one constraint is active at a time and determine the closed form solution of the decision variable, we have the limit of the variable for the problem. As the constraints are linear in the decision variable, we can add the limit on all the constraints to ensure that the solution will always be feasible. (I am not sure if the maximum is more appropriate and correct).
Any help and guidance will be highly appreciated.
Best Answer
The objective function is irrelevant to your question, as your interest is a box feasible region of $x$.
In the case that $x$ is an univariable, you can solve the following two linear program: $$ \begin{array}{lll} x_{min} =& \min_x & x \\ &\text{s.t. } & a_i x\leq b \quad \forall i \in \{1, \dots, N\} \end{array} $$ and $$ \begin{array}{lll} x_{max} =& \min_x & -x \\ &\text{s.t. } & a_i x\leq b \quad \forall i \in \{1, \dots, N\} \end{array} $$
In the case that $x$ is a multivariable, the box feasible region is not unique. We'll need more specific feature/requirements in the interested region (such as maximizing the area) in order to narrow down options. See the following example with $x\in\mathbb{R}^2$. Consider the constraints are $$ \begin{align*} x_1 \geq 0 \\ x_2 \geq 0 \\ x_1 + x_2 \geq 1. \end{align*} $$ The box feasible region is $\begin{pmatrix} x_1 \\x_2 \end{pmatrix} \in \begin{bmatrix} \begin{pmatrix}1-k\\k \end{pmatrix}, & \begin{pmatrix}\infty \\ \infty \end{pmatrix} \end{bmatrix}$ for any $k\in [0,1]$.