# Relax equality into inequality in convex problem

Let $\mathbf{x}, \mathbf{z}, \underline{\mathbf{x}}, \overline{\mathbf{x}} \in \mathbb{R}^{I}$, where the first two are variables and the last two are given data. I have the following problem:

$$\begin{array}{cll} \displaystyle \min_{ \mathbf{x}, \mathbf{z} } & & \displaystyle f(\mathbf{x}) \\ \mathrm{s.t.} & & \mathbf{x} \in \mathcal{Q} \\ & & \mathrm{diag} (\mathbf{z}) \underline{\mathbf{x}} \leq \mathbf{x} \leq \mathrm{diag} (\mathbf{z}) \overline{\mathbf{x}} \\ & & z_{i} = g_{i}(x_{i}), \quad i=1, \ldots, I. \end{array}$$

with $\mathcal{Q}$ closed and convex, $f(\mathbf{x})$ convex, and $g_{i}(x_{i})$ concave, $i=1, \ldots, I$.

Based on the information provided, can I relax the equality constraints into inequalities (i.e., $z_{i} \leq g_{i}(x_{i}), \; i=1, \ldots, I$), thus making the problem convex, while ensuring that the optimal $\mathbf{x}$ doesn't change?

If yes, how can I demonstrate it?

Thanks

• If $g_i$ is merely concave, your equality constraint problem is not convex. In convex programs, only affine equality constraints are allowed. – gerw Feb 25 '14 at 11:44
• Sorry, I meant that the problem would be convex if there was an inequality. Let me correct that. – TheDon Feb 25 '14 at 13:23

No, this is not possible. The easiest counterexample is $$\text{Minimize } x^2 \text{ s.t. } -1 = -x^2$$ with minimum $1$ and the relaxation would be $$\text{Minimize } x^2 \text{ s.t. } -1 \le -x^2$$ with minimum $0$.