5
$\begingroup$

I am reading Nonlinear Programming by Bertsekas, and the chapter on duality starts like this: we define the primal problem as $$\begin{align*} &\min f(x)\\ &x \in X\\ &g(x) \le 0 \end{align*}$$ where $X \subseteq \mathbb{R}^n$ and $g: \mathbb{R}^n \to \mathbb{R}^m$. Then the author uses $f^*$ to denote the solution of this problem, using $\inf$ now: $$\begin{align*} &\inf f(x)\\ &x \in X\\ &g(x) \le 0 \end{align*}$$

Then the author goes on to say:

Note that the definition of $f$ and $g_i$ [the components of $g$] is immaterial outside $X$, so if in a given problem the cost function and/or some of the constraints are defined over a domain $D \subset \mathbb{R^n}$, we can introduce $D$ as part of the set $X$, and redefine these functions arbitrarily outside $D$. Unless the opposite is clearly stated, we will assume throughout this chapter the following:

Assumption 6.1.1: (Feasibility and Boundedness) There exists at least one feasible solution for the primal problem and the cost is bounded below, i.e. $- \infty < f^* < \infty.$

There are several things I don't understand here:

$1)$ Why switch from the minimum to the infimum?

$2)$ Why would we ever consider the feasible region as defined by an abstract set $X$, AND by inequalities? If we allow ourselves to use abstract sets, why don't we just cobine all the constrains into one set?

$3)$ What does it mean to "introduce $D$ as part of $X$"? I assume $X$ must already be contained in $D$, so what does it mean to make $D$ "a part" of $X$? My best guess is that we redefine $X$ as $D$. But why would we modify our domain of feasibility? We are making up a new problem, whose solution may not be the same as the original problem, in whose solution we are interested.

$4)$ Is Assumption 6.1.1 in any way connected to the discussion about $D$ above it? I don't see how it would be, but it's right below the discussion about $D$.

Thank you very much.

$\endgroup$
9
$\begingroup$
  1. Switching from minimum to infimum allows you to discuss problems where the objective value is bounded below but a minimum is never attained (such as "minimizing" $f(x)=1/x$ over the domain $x>0$).
  2. It is common to state domain limits ($x\ge 0$, $x \le 5$, $x$ integer) separately from "functional constraints" ($x_1^2 + x_2^2 - 1 \le 0$ etc.). You may want to assign Lagrange multipliers to the latter, take derivatives, or do other stuff than would not necessarily make sense for the domain limits.
  3. This is a bit opaque, but my best guess is that the author intends $D$ and $X$ to intersect without either necessarily being contained in the other. Off hand, I can't think of a suitable example. If $D \subset X$, it certainly does make sense to just change $X$ to $D$ in the problem statement.
  4. I don't think the Assumption is explicitly tied to the confusing passage, although it is connected in the sense that the assumption implies $D\cap X \neq \emptyset$.
$\endgroup$
  • $\begingroup$ Thank you so much for your answer! In regards to $2$: I see how "x is an integer" is a different type of constraint, but I thought that $x \ge 0$ or $x \le 5$ would always be considered "functional constraints". $\endgroup$ – Ovi Oct 3 '20 at 0:57
  • $\begingroup$ Variable bounds can be treated as functional constraints but often (more commonly?) are handled differently. For instance, in linear programming lower bounds of zero are "baked into" the simplex algorithm, and upper bounds on variables are handled by modifying the algorithm rather than treating them as constraints. Similarly, I think some NLP algorithms handle bounds by deflecting gradients as solutions approach the boundary of the box. $\endgroup$ – prubin Oct 3 '20 at 17:49

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.