Big M on convex optimization

66 Views Asked by At

Given the following convex optimization problem

\begin{equation} \begin{array}{rl} F(x):= \min_{x\in\mathbb{R}^n}\ &x^{T}Ax+b^{T}x\\ \text{s.t.}\ & |x| \leq M \quad (i.e., |x_1| \leq M, |x_2| \leq M, \dots, |x_m|\leq M) \end{array} \end{equation}

where $A$ is a symmetric positive-definite matrix and $M$ is a large number ensuring a valid upper bound for each $x_i$.

Suppose we replace the constraint with the following

\begin{equation} \begin{array}{rl} \text{s.t.}\ & |x| \leq M' \end{array} \end{equation}

where $M'<M$.

Suppose $x^{*}$ denotes an optimal solution for the first model, and $x^{'}\neq x^{*}$ denotes the optimal solution to the second model and $x^{'}$ is not optimal for the first model.

Assume $M'$ is not a valid upper bound for $x$ implying $F(x^{'})> F(x^{*})$.

Is it possible that $x^{'}$ be strictly within the feasible region defined by $|x|\leq M'$, or at least one of $x_i$ will hit the $M'$?