# Relaxing non-affine equality constraints in convex optimization

Consider the convex function $$f$$. In section 4.2.1 in these lecture notes, the author writes:

### 4.2.1 Relaxing non-affine equality constraints

For functions $$g_i(x)$$, $$i \in \{1,\dots,d\}$$ that are convex but not affine, we relax \begin{aligned} \min \quad & f(x), \\ \textrm{s.t.} \quad & {\color{blue}{g_i(x) = 0, \ i \in \{1,\dots,d\}}} \\ \quad & Ax = b \\ \quad & h_i(x) \leq 0 \end{aligned} \implies_{\!\!\!\text{relax}} \begin{aligned} \min \quad & f(x), \\ \textrm{s.t.} \quad & {\color{blue}{g_i(x) \leq 0, \ i \in \{1,\dots,d\}}} \\ \quad & Ax = b \\ \quad & h_i(x) \leq 0 \end{aligned} as the original formulation is a non-convex problem (non-affine equalities are not convex). The relaxed formulation turns affine equalities into affine inequalities, so thus has more feasible points and is now convex.

I'm not sure why the author converted the constraint "$$g_i(x) = 0, \ i \in \{1,\dots,d\}$$" to "$$g_i(x) \leq 0, \ i \in \{1,\dots,d\}$$" rather than "$$g_i(x) \geq 0, \ i \in \{1,\dots,d\}$$", since both kinds of relaxations have the original constraint $$g_i(x) = 0$$ as a subset. One reason would be that the constraint $$g_i(x) \leq 0$$ is a convex subset of the epigraph of the convex functions $$g_i(x)$$. Therefore, $$g_i(x) \leq 0$$ defines a convex set, while $$g_i(x) \geq 0$$ may not. However, I'm not sure if this reasoning is correct.

If $$g(x)$$ is a jointly convex function of $$x$$, then $$g(x) \le 0$$ is a convex constraint. However, if, as stated, $$g(x)$$ is not affine, then except for some trivial cases, $$g(x) \ge 0$$ is a non-convex constraint.

That said, in general there is no particular reason why the relaxation of $$g(x) = 0$$ to $$g(x) \le 0$$ should be any good. If the solution to the relaxed problem does not satisfy the original constraint, $$g(x) = 0$$, all that will have been accomplished is gaining the knowledge that the optimal objective value of the relaxed problem constitutes a lower bound for the optimal objective value of the original problem.

• You mean "...some trivial cases, $g(x) \geq 0$...", and not "...some trivial cases, $g(x) \leq 0$..." right? Commented Oct 1, 2023 at 21:33
• Yes. I just fixed the typo. Commented Oct 1, 2023 at 22:40

Just want to refine my reasoning: Given a convex function $$f : X \to \mathbb R$$, where $$X \subseteq \mathbb R^n$$ is a convex set, all of $$f$$'s sublevel sets, including the set $$\{x \in X \mid f(x) \leq 0\}$$, are convex. This is straightforward to prove: for $$\alpha \in \mathbb R$$, let $$C_\alpha = \{x \in X \mid f(x) \leq \alpha\}$$ and fix any $$x_1,x_2 \in C_\alpha$$, such that $$f(x_1) \leq \alpha$$ and $$f(x_2) \leq \alpha$$, and fix any $$t \in [0,1]$$. Then, because $$f$$ is convex, we have \begin{align} f(tx_1 + (1-t)x_2) &\leq tf(x_1) + (1-t)f(x_2) \\ &\leq t\alpha + (1-t)f(x_2) \\ &\leq t\alpha + (1-t)\alpha \\ &= \alpha \end{align} and so $$tx_1 + (1-t)x_2 \in C_\alpha$$. See section 3.1.6 in the book Convex Optimization by Boyd and Vandenberghe for more information.

Moreover, if $$f$$ is a convex but not affine function, and if the sublevel set $$\{x \in X \mid f(x) \leq 0\}$$ is not empty, then its complement in $$X$$, which is $$\{x \in X \mid f(x) > 0\}$$, is a non-convex subset of $$\mathbb R^n$$ (see here for a sketch of a proof of this).

• Convex but not affine is not equivalent to strictly convex. Commented Oct 1, 2023 at 22:42
• @MarkL.Stone you are correct. Fixed this. If you see anything else, let me know. Commented Oct 1, 2023 at 23:44
• @mhdadk, would you please, say what you mean by all of $f$'s sublevels set? Is it equal to subspace? Commented Oct 2, 2023 at 4:15
• @A.Omidi the $\alpha$-sublevel set of $f$ is $C_\alpha = \{x \in X \mid f(x) \leq \alpha\}$. All of $f$’s sublevel sets is $C_\alpha$ for each $\alpha \in \mathbb R$. Commented Oct 2, 2023 at 13:17
• @mhdadk, thanks for clarification. Commented Oct 3, 2023 at 6:06