1
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

Your 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.

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

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).

$\endgroup$
5
  • $\begingroup$ Convex but not affine is not equivalent to strictly convex. $\endgroup$ Oct 1, 2023 at 22:42
  • $\begingroup$ @MarkL.Stone you are correct. Fixed this. If you see anything else, let me know. $\endgroup$
    – mhdadk
    Oct 1, 2023 at 23:44
  • $\begingroup$ @mhdadk, would you please, say what you mean by all of $f$'s sublevels set? Is it equal to subspace? $\endgroup$
    – A.Omidi
    Oct 2, 2023 at 4:15
  • 1
    $\begingroup$ @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$. $\endgroup$
    – mhdadk
    Oct 2, 2023 at 13:17
  • $\begingroup$ @mhdadk, thanks for clarification. $\endgroup$
    – A.Omidi
    Oct 3, 2023 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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