2
$\begingroup$

This question already has an answer here:

The generalized inequality defined by a proper cone $K$ is that $x \ge_{K} y$ if $x-y \in K$ for $x,y \in K$. Does this means that for any $x \in K$, we have $x \ge_{K} 0$ since $x - 0 = x \in K$ ?

EDIT: My definitions of cones and proper cones follow the ones in "Convex Optimization" by S. Boyd, in which 0 is contained in cones. On page 53 of the book, there is a statement about generalized inequalities:

$x \le_{K} y$ if and only if $\lambda^T x \le \lambda^T y$ for all $\lambda \ge_{K^*} 0$

where $K^*$ is the dual cone of the proper cone $K$, so $K^*$ is also a proper cone.

The reason I ask this question is that if for any $\lambda \in K^*$, we have $\lambda \ge_{K^*} 0$, why not just using $\lambda \in K^*$ instead of $\lambda \ge_{K^*} 0$ in the above statement?

$\endgroup$

marked as duplicate by Michael Grant, Claude Leibovici, martini, John Gowers, Jonas Meyer Apr 1 '15 at 13:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

From what I can tell, most of your question is adequately addressed in this other post, except perhaps for the last part:

The reason I ask this question is that if for any $\lambda \in K^*$, we have $\lambda \ge_{K^*} 0$, why not just using $\lambda \in K^*$ instead of $\lambda \ge_{K^*} 0$ in the above statement?

I can think of two good reasons to prefer the inequality notation here.

First, for aesthetic consistency. Which of these two stacks of constraints seems cleaner/easier to read (left or right)? \begin{array}{ccc} x \succeq_K y &\qquad& x\succeq_K y \\ y \succeq_K z && y\succeq_K z \\ z \succeq_K 0 && z\in K \end{array} I claim the left-hand side is cleaner. I see no reason to drop back to set notation $z\in K$ just in that last case just because the right-hand side happens to be zero.

Second, for conceptual clarity. The inequality notation $\lambda \succeq_{K^*} 0$ reminds the reader of the tie to traditional inequalities. Consider this linear program: \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x \leq b \end{array} The Lagrangian for this problem is $$L(x,z) = c^T x - \langle z, b - Ax \rangle \qquad z\geq 0.$$ Now let's replace the inequality with a generalized inequality: \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x \preceq_K b \end{array} where $K$ is a proper cone. The new Lagrangian is $$L(x,z) = c^T x - \langle z, b - Ax \rangle \qquad z \succeq_{K^*} 0.$$ where $K^*$ is the dual cone. Yes, I could have written $b-Ax\in K$ and $z\in K^*$ instead; but doing so breaks the conceptual parallels to linear programming. Why do that?

$\endgroup$
0
$\begingroup$

The answer to this question depends on how you define cones.

Wikipedia says that a cone is a subset of a vector space closed under scalar multiplication by positive constants. So a subset $K$ such that if $x \in K$ and $a > 0$ then $ax \in K$.

These cones need not contain $0$, in which case your reasoning does not hold.

However, Wikipedia also mentions:

A cone is said to be pointed if it includes the null vector (origin) $0$; otherwise it is said to be blunt. Some authors use "non-negative" instead of "positive" in this definition of "cone", which restricts the term to the pointed cones only. In other contexts, a cone is pointed if the only linear subspace contained in it is $\{0\}$.

So, according to some authors, the $>$ in the above definition should be $\ge$, from which it easily follows that $0 \in K$ and your reasoning is correct.

$\endgroup$
  • $\begingroup$ why 0 is not in $K$? $\endgroup$ – chaohuang Apr 12 '13 at 2:01
  • $\begingroup$ It might be! But you can't be sure unless you are told. $\endgroup$ – Ben Millwood Apr 12 '13 at 2:07
  • $\begingroup$ I mean from the definition of cones, we have $0 \in K$. $\endgroup$ – chaohuang Apr 12 '13 at 2:08
  • $\begingroup$ That depends on how you define cones. Wikipedia defines them so that they don't necessarily contain 0: en.wikipedia.org/wiki/Cone_(linear_algebra) $\endgroup$ – Ben Millwood Apr 12 '13 at 2:10
  • $\begingroup$ OK, my definition of cones is that for any $x \in C$ and $\alpha \ge 0$, we have $\alpha x \in C$, then $C$ is called a cone. For these (proper) cones, do we have $x \ge_{K} 0$ for any $x \in K$? $\endgroup$ – chaohuang Apr 12 '13 at 2:13

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