2
$\begingroup$

I want to find the minimum of a linear function $F$ over a domain $D \subseteq \mathbb{R}^n$ which is the intersection of $n$ sets $D_i$ of the form $f(x_{i-1}) \leq x_i \leq g(x_{i-1})$, where $f(t), g(t)$ are continuous piecewise lienar functions.

Such a domain $D$ is in general nonconvex.

I am not familiar with the field of optimization, and I hope the question is not trivial; I tried looking in the literature for similar problems, but I could not find an answer.

Since $F$ is linear, its minimum is in one of the vertices of the polytope $D$, and I claim in particular that it must lie on one of the vertices of the convex hull of $D$.

If what I claim is true, then the only difficulty would be finding the convex hull of such a domain. I would like in particular to describe the convex hull as the intersection of half spaces $A_i x \leq b_i$. Since the convex hull operation does not commute with the intersection, one cannot simply take the convex hull of $D_i$'s and intersect them.

So I have two questions:

1) Is it true that the minimum lies on one of the vertices of the convex hull?

2) How can one compute the convex hull of a domain like the one I described as the intersections of halfspaces?

EDIT: a typo and reformulated the question for clarity

$\endgroup$

1 Answer 1

2
$\begingroup$

Partial answer: about to the first question: Let's make a change of variables to aid intuition: let $y_i = x_1+...+x_i, (i=1,..., n)$, then the region $D_i$ is described as $f_i(y_{i-1}) \le y_i - y_{i-1} \le g_i(y_{i-1})$, and, taking $\tilde f_i(u) = f_i(u) + u$, etc., we can write $D_i$ condition defining $D_i $ as $\tilde f_i(y_{i-1}) \le y_i \le \tilde g_i(y_{i-1})$. I'll drop the $\tilde \; $ going foward.

Let's also assume that the linear function $f$ to be minimized is not constant. Since the condition defining $D_i$ bounds each dimension, one at a time, $D = \cap_i D_i$ is compact, so $f$ attains a minimum in $D$. Since the gradient of $f$ is not null, the point that affords the minimum cannot be in the interior of $D$, so it is a boundary point.

What you call a "vertix" can be made more precise. A point of a set is call extreme iff it is not contained in the relative interior of a segment with end-points in the set. For example, in two dimensions, consider the set $ D = \{(x_1,x_2) | -2 \le x_1 \le 2 \text{ and } -1 \le x_2 \le max(|x_1|,1-|x_1|) \}$ the point $(0,1)$ is a boundary point that is not extremal, because the segment with endpoints $(-1,1), (1,1)$ has endpoints in $D$, and contains $(0,1)$ in is relative interior.
(Note: the concept of extreme points appears in relation to convex sets. I used it as it would apply to the convex hull of the underlying set.)

Now if $f$ attains its minimum at a non-extereme point, then it must be constant along the segment containing the non-extemal point ($f$ restricted to the segment is affine, so it is minimized at the boundaries, or it is constant). Continue the segment until it hits a face of $D$ and argue by induction on the affine dimension of the polytope $D$.

Minkowski's theorem (or Krein-Milman theorem in locally convex Housdorf vector spaces) says that a compact convex is the convex hull of its extreme points, but if $K = \text{ closed convex hull of }D$, then the extreme points of $K$ must lie in $D$, else they will be convex combinations of other points in $K$.

So, to sum up:
1) $f$ attains its minimum at extreme points of $D$
2) the convex hull of $D$ is generated by the exteme points of $D$

$$ \ll \gg \fallingdotseq \doteqdot \doteqdot \doteqdot \doteqdot \risingdotseq \ll \gg$$

As for the second part (computing the convex hull of $D$), your problem is essentially 2 dimmensional, because the functions involved depend on only one variable. If $g_i^* = \text{ least concave majorant of }g_i$, i.e.:$g_i^*(u) = \inf\{h(u)| h \text{ is concave and } g_i(\zeta) \le h(\zeta) \text{ for all }\zeta\}$, then $g_i^*$ is convave. Similarly define $f_i^* = \text{ greatest convex minorant of } f_i $.
Because $g_i$ is piecewise linear, so is $g_i^*$, and because it is a least concave majorant, it can be written as
$$ g_i^*(u) = \min_t\{ b_{it} + m_{it}\; u \}$$ for a finite family of affine functions $u \mapsto b_{it} + m_{it}\:u$.

Likewise, $f_i^*$ can be written as $$ f_i^*(u) = \max_s\{ \beta_{is} + \gamma_{is}\; u \}$$ for some finite family of affine functions.

There are computer algorithms to compute the convex envelope of a finete set of points on the plain, i.e.: ponts in 2D. I suspect those algorithms can be make to work to find the concave majorant, and convex nimorants above (this is the point where my answer has a gap....).

Why looking at $f_i^*, g_i^*$? Because the convex hull of $D$ can be written in terms of these functions as: $$ f_i^*(y_{i-1}) \le y_i \le g_i^*(y_{i-1}) \;\;\;(i=1,..,n) \tag{1}, $$ and, recalling the structure of $f_i^*, g_i^*$, (1) is a description of the convex hull of $D$ in terms of hyperplanes. In all its glory, the convex hull of $D$ is: for all $i$, $$ \begin{align} y_i &\le b_{it} + m_{it}\; y_{i-1} &\text{ for all $t$}\\ \beta_{is} + \gamma_{is}\; y_{i-1} &\le y_i &\text{ for all $s$} \end{align} \\ $$.

$\endgroup$
3
  • $\begingroup$ Thank you for the answer, the first part is very clear, but I am not convinced that what you claim in the second part of your answer is true: suppose for example that it holds for a particular $f, g: [-1, 1] \rightarrow [-1, 1]$. Then, adding a new linear piece to the functions such that $f(2) = -M$ and $g(2)=M$ for a big $M$ would make the convex hull of the $D_i$'s very large by adding a set of points which will never be feasible for the solution, since $x_i \in [-1, 1]$ by our assumption on $f$ and $g$. $\endgroup$
    – mono
    Aug 31, 2016 at 8:26
  • $\begingroup$ Right. The least concave majorant should involve only the points that matter. Take $g_i^*(u) = \inf\{h(u)| h \text{ is defined on } ccc(D_{i-1}), h \text{ is concave on $ccc(D_{i-1})$, } g_i(\zeta) \le h(\zeta) \text{ for all }\zeta \in ccc(D_{i-1}\}$ $\endgroup$ Aug 31, 2016 at 21:07
  • $\begingroup$ (where ccc = "closed convex hull") $\endgroup$ Aug 31, 2016 at 21:08

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.