2
$\begingroup$

In lecture notes by Nemirovsky and BenTal (2023), I found the following definition of a convex optimization problem:

enter image description here

MY QUESTION: why do we need both the functions $f_i$ and the domain $G$? Apparently they serve exactly the same purpose: they define the domain in which $f_0$ should be minimized. Why not just define a convex program simply as

$$\min_{x} \{f_0(x): x\in H\}?$$

$\endgroup$
7
  • $\begingroup$ The assumptions made about the problem dictate which method you can use to solve the problem. $\endgroup$ Nov 28, 2023 at 11:00
  • $\begingroup$ @ErlingMOSEK but technically, you can formulate any problem of the first kind as a problem of the second kind, which is shorter. So why is the first kind needed? $\endgroup$ Nov 28, 2023 at 11:18
  • 2
    $\begingroup$ 1. Historical tradition. 2. $G=\mathbb{R}^n$ is a very typical case. 3. A lot of people would miss the point and ask where are the constraints. 4. Ultimately this is how it is often in practice, for instance when you want to discuss infeasible constraint subsets. 5. You have to define $H$ somewhere on the side anyway. $\endgroup$ Nov 28, 2023 at 12:06
  • 2
    $\begingroup$ Just a difference in abstraction level. Choose the best abstraction level for the analysis. I guess you will see that in the text that follows your paragraph. $\endgroup$ Nov 28, 2023 at 12:13
  • 2
    $\begingroup$ @Michal Adamaszek wrote "You don't start a lecture from the most abstract point of view on the topic." Maybe you don't, but I had some professors who did, because the good students will figure it out and the bad students shouldn't be in the class anyway. " $\endgroup$ Nov 28, 2023 at 17:16

1 Answer 1

0
$\begingroup$

In practice, it is often the case that you observe constraints of the form "$f_i(x) \leq 0$" rather than "$x \in G$". The former constraint defines a convex set if $f_i$ is convex, since every sublevel set of a convex function is convex. It is then from this former constraint that you can define the convex set $G$ in the latter constraint.

$\endgroup$
5
  • $\begingroup$ It is still not clear why you need both the $G$ and the $f_i$, if each one of them is enough $\endgroup$ Nov 28, 2023 at 17:43
  • $\begingroup$ @ErelSegal-Halevi you are right, you don’t need both. However, it is likely easier for a reader to verify that a set is convex if it is given as the sublevel set of a convex function. If I give you an arbitrary set $G \subset \mathbb R^n$, how easy would it be for you to tell whether $G$ is convex or not without using the definition of a convex set? On the other hand, if I give you the set $\{x \in \mathbb R^n \mid f(x) \leq 0\}$, it would be straightforward to check that this set is indeed convex: if $f$ is a convex function (note that the converse is not true) $\endgroup$
    – mhdadk
    Nov 28, 2023 at 22:37
  • $\begingroup$ so why do we need $G$ at all? $\endgroup$ Nov 29, 2023 at 6:14
  • $\begingroup$ @ErelSegal-Halevi $G$ is needed because $f_0$ may not even be defined on the whole $\mathbb{R}^n$. Which brings me to the point, that you can take this further and eradicate $f_0$ as well. Every convex problem can be written as $\min_{x\in H} (x_0)$ where $H$ is a convex set. Why not do that? $\endgroup$ Nov 29, 2023 at 6:51
  • 1
    $\begingroup$ @MichalAdamaszek In the notes, it is assumed that the objective and the constraints are on $\mathbb{R}^n$. By eradicating $f_0$, I think you mean introducing a new variable $x_0$, in which way the resulting problem is only equivalent to the original one, but they are not the same (it is on $\mathbb{R}^{n+1}$ rather than $\mathbb{R}^n$), so it is a different topic. $\endgroup$
    – xd y
    Nov 29, 2023 at 7:59

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.