2
$\begingroup$

Update:

Linear programming problems (LP) have a convex space, precisely vector space, such as a convex feasible region as pointed out by @prubin. Also, they may have either unique or multiple solutions. (there are already other types).

On the other hand, there is still a concept named strictly convex that interprets:

a strictly convex space is a normed vector space (X, || ||) for which the closed unit ball is a strictly convex set. Put another way, a strictly convex space is one for which, given any two distinct points x and y on the unit sphere ∂B (i.e. the boundary of the unit ball B of X), the segment joining x and y meets ∂B only at x and y. Strict convexity is somewhere between an inner product space (all inner product spaces being strictly convex) and a general normed space in terms of structure. It also guarantees the uniqueness of the best approximation to an element in X (strictly convex) out of a convex subspace Y, provided that such an approximation exists.

The distinction between these two concepts comes in the following (for more details please, see this link):

A function $f: \mathbb{R} \to \mathbb{R}$ is convex if for all $x,y > \in \mathbb{R}$ and for all $\lambda \in (0,1)$ the following holds: $$f(\lambda x +(1-\lambda)y) \leq \lambda f(x) +(1-\lambda) f(y)$$

Geometrically this means that the line through two points $f(x)$ and $f(y)$ on the graph is always above the graph between $x$ and $y$.

We say that $f$ is strictly convex if the above inequality holds strictly, i.e. $$f(\lambda x +(1-\lambda)y) < \lambda f(x) > +(1-\lambda) f(y)$$

Since I would like to know, 1) What does exactly it mean? 2) Is there any simple example, in the context of LP and MIP, to illustrate that? 3)If an LP has a such space, might it have only a unique solution?

$\endgroup$
2
  • 2
    $\begingroup$ Two straight lines (in Euclidean geometry) can intersect in multiple points if the lines are equivalent. So in the realm of LP, strict convexity is just saying that no two constraints are equivalent (because if they are, then you cannot determine which of the two constraints is slack, with slack = 0, and which is a member of the binding constraint set). $\endgroup$
    – Ben Voigt
    Commented Sep 16, 2022 at 20:00
  • $\begingroup$ @BenVoigt, Many thanks for the exolanation. $\endgroup$
    – A.Omidi
    Commented Sep 20, 2022 at 8:49

1 Answer 1

3
$\begingroup$

I think you are confusing two things here. A linear program has a convex feasible region. The term "convex space" refers to an entire vector space, not to a particular region (such as an LP feasible region) within the space. It basically imposes a restriction on the nature of the norm used in defining the space.

Update:

Can we refer to the feasible set of linear programming as strictly convex?

The term "strictly convex" only applies to functions, not to sets.

Can we say any subset of a convex set/space would be a convex set/space?

No. Consider the triangle $T$ defined by $x \geq 0$, $y \geq 0$, $x + y \leq 1$, which is convex. The subset consisting of the vertices, $\{(0,0), (0,1), (1,0)\}$ is not convex. Neither is the set $\{(x,y) \in T : x^2 + y^2 \geq 1/2\}$.

$\endgroup$

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.