Adding the constraint "at least one entry of $x$ is $100$" to a convex program

Question

I have the following optimization problem in $x \in \mathbb R^p$

$$\begin{array}{ll} \text{minimize} & a^\top x\\ \text{subject to} & x \geq 0\end{array}$$

where $x \geq 0$ means that $x_1, x_2, \dots, x_p \geq 0$. To add the condition "at least one entry of $x$ is $100$", one option is to use the following

$$(x_1−100) (x_2−100) \cdots (x_p−100)=0$$

But how do I represent this in matrix form?

---

I used the example from the posted link. But looks like $$(x_1−100)(x_2−100) \cdots (x_p−100)=0$$ is difficult to express in matrix multiplication as it is not linear. The alternate solution, does not guarantee that value of 100 will be achieved.

Answer 1

Not sure if this is what you are looking for, but an alternative approach is to use binary variables:

$$\begin{align} & 100 \delta_i \le x_i \le 100 \delta_i + U_i (1-\delta_i) \\ & \sum_i \delta_i = 1\\ & \delta_i \in \{0,1\} \\ & 0 \le x_i \le U_i \end{align}$$

Here $U_i$ is an upper bound on $x_i$. This formulation would make your model a MIP (Mixed Integer Programming) model. Some MIP solvers allow socalled indicator constraints. For those solvers you can write:

$$\begin{align} & \delta_i = 1 \Rightarrow x_i = 100 \\ & \sum_i \delta_i = 1\\ & \delta_i \in \{0,1\} \\ & x_i \ge 0 \end{align}$$

Binary variables are often used to "bypass" non-convexities.

Of course this is mainly interesting if you have other linear constraints in your model. I believe as stated we can solve it just by sorting.

Answer 2

If $p$ is not too large, you could solve the $p$ separate reduced problems where each $x_i$ is forced to $100$. (Actually reduce them. Set $x_i = 100$ and eliminate it from the rest of your system.)