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{equation} \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} \end{equation}

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?


  • $\begingroup$ If $g_i$ is merely concave, your equality constraint problem is not convex. In convex programs, only affine equality constraints are allowed. $\endgroup$ – gerw Feb 25 '14 at 11:44
  • $\begingroup$ Sorry, I meant that the problem would be convex if there was an inequality. Let me correct that. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.