Questions tagged [dual-cone]
Use this tag for questions involving dual cones. In convex analysis, the "dual cone" to a set is the collection of all elements that form a "positive angle" with every element in the set. That is, given a set $S$ in a vector space $V$, we define the dual cone by $S^* = \{y:\langle x,y \rangle \geq 0 \text{ for all } x \in S\}$ (the precise meaning of $\langle \cdot,\cdot\rangle$ depends on the context).
110 questions
0
votes
1
answer
66
views
What Optimization Methods Are Suitable for Solving This Problem? [closed]
am new to the field of optimization and have encountered the following optimization problem. I am curious to know what type of optimization problem this is and what methods are appropriate for solving ...
1
vote
0
answers
23
views
Intersection of Bouligand tangent cones is the tangent cone of the intersection.
I am reading the book "Set-Valued analysis" by Jean-Pierre Aubin and Hèlène Frankowska. On page 152, table 4.4, statement 5b), we read:
If $K_1$ and $K_2$ are closed derivable subsets ...
- 109
0
votes
1
answer
41
views
Two definitions of normal cone of a closed convex cone
I am studying problems of the form
$$\text{minimize } \quad f(x) \quad \text{subject to} \quad G (x) \in \mathcal{K},\tag{1}$$
where $f:\mathbb{R}^{n} \rightarrow \mathbb{R}$ and $G:\mathbb{R}^{n} \...
- 881
1
vote
1
answer
27
views
Do positive functionals on a self-dual cone extend to the whole space?
Let $\mathcal H$ be a Hilbert space with self-dual cone $\mathcal H^+ = \{\,\xi\in\mathcal H \mid \langle\xi|\mathcal H^+\rangle \ge 0\,\}$. Suppose we have a function $f\colon \mathcal H^+ \to [0,+\...
- 758
1
vote
0
answers
51
views
Duality Results for Convex SDP Programming
Suppose we have an SDP program with a convex (but nonlinear) objective $f(X)$, where $X$ is a positive semidefinite matrix. All other constraints are linear. Does there exist a dual program for such a ...
0
votes
1
answer
73
views
Describe all cones in $\mathbb R^n$ that are simplicial and cosimplicial.
For any finite set of vectors $(v_1, \ldots, v_k \in \mathbb{R}^n)$, let's define:
$Cone(v_1,…,v_k)= \{λ_1v_1+…+λ_kv_k,∣,λ_1,…,λ_k \ge 0\}$ and $Poly(v_1,…,v_k)= \{ x \in \mathbb{R}^n ∣(v_i, x) \ge 0, ...
- 1
0
votes
0
answers
41
views
Why is the Cartesian product of second-order cones self-dual?
I came upon a paper regarding conic programming (CP) where a constraint is an inequality defined on Cartesian product of second-order cones, named $K$. And he derived the dual problem of this CP with ...
- 1
4
votes
2
answers
194
views
What Toric Variety does this fan correspond to?
Let $\Sigma$ be the fan defined by $\{\sigma_1,\sigma_2,\sigma_3,\sigma_4,\star\}$, where $\sigma_1=\operatorname{cone}(e_1)$, $\sigma_2=\operatorname{cone}(e_2)$, $\sigma_3=-\sigma_1$, $\sigma_4=-\...
- 4,163
0
votes
0
answers
37
views
Basis of the intersection of a cone and its dual.
Let $a_1,\dots, a_m$ be vectors in $\mathbb R^n$, let $A\in\mathbb R^{n\times m}$ whose columns are $a_i$s. The cone generated by $A$ (denoted $\operatorname{cone}A$) is $C=\{ Aw: 0\leq w \}$, its ...
- 6,032
1
vote
1
answer
179
views
Questions related to Cones and Subspaces of Euclidean Space
Cone: A subset $ S \subseteq \mathbb{R}^n$ is a cone if $\alpha \geq 0 \implies \alpha S \subseteq S.$
Polar: A Polar $K^*$ of a cone $K$ is a closed convex cone such that
$$K^*=\{y \in \mathbb{R}^n \...
- 11
1
vote
1
answer
129
views
Polar cone of a closed convex cone in $R^4$ defined by a convex inequality constraint
Let $c>1$ be a constant. Consider points in four dimension with coordinates $(x,y,z,p)\in R_{\ge 0} \times R_{\ge 0} \times R \times R_{\ge 0}$
and the cone
$$K = \{ (x,y,z,p)\in R_{\ge 0} \times ...
- 2,207
1
vote
3
answers
356
views
intuition behind deriving the equation of a double-napped cone
I know the equation of a double-napped cone is $\frac{x^2}{a^2} + \frac{y^2}{b^2} = \frac{z^2}{c^2}$ but don't fully understand how this is derived. For a right circular cone centered at the origin, ...
- 135
1
vote
1
answer
300
views
Cone dual and orthogonal projection
Let $K \subset \mathbb{R}^{n}$ be a closed cone (not necessarily convex) and $y \in K^{*}$, then the orthogonal projection of $y$ onto $K$ is unique and equal to zero.
$K^{*} = \{d \in \mathbb{R}^{n}\...
- 173
0
votes
0
answers
40
views
why the inner product with an element that does not belong to a convex cone is negative
Let us consider a set with an infinite number of vectors $\{v_k \mid k \in \mathbb{N} \}$ with $n$ cordinates, and if we consider the conned convex set containing all theses vectors, denoted by $K$.
...
- 169
1
vote
1
answer
129
views
Geometric interpretation of dual generalized inequalities in 2D using proper cone and its dual cone.
This question is based on section 2.6.2 of the textbook Convex Optimization by Boyd. The specific mathematical statement I am referring to is the following:
$$ x \prec_{K} y \iff \lambda^{T}x < \...
- 21
0
votes
0
answers
473
views
Dual of a norm Cone.
Problem
[Example 2.25 Taken from Convex Optimization By Stephen Boyd, Lieven Vandenberghe]
In this example, it proves that the dual of a norm cone is the cone of ...
1
vote
0
answers
339
views
Describe Dual Cones in $R^2$
I'm trying to find the dual cones for each of the following cones: $K=\left\{\left(x_{1}, x_{2}\right)\mid \left| x_{1}\right| \leq x_{2}\right\}$ and $K=\left\{\left(x_{1}, x_{2}\right) \mid x_{1} +...
- 392
1
vote
1
answer
417
views
Farkas' Lemma and Theorem of Alternatives
Let's define the DUAL CONE of a subset Y of $\mathbb{R}^n$ as follows: $$Y^*=\{x\in\mathbb{R}^n\mid \langle x,y\rangle \ge 0\quad\forall y\in Y\}.$$ If $Y$ is a finite subset of $\mathbb{R}^n$, i.e. ...
- 685
3
votes
1
answer
1k
views
Finding dual cone for a set of copositive matrices
This is a question from the textbook Convex Optimization by Stephen Boyd and Lieven Vandenberghe (2.35). I did read through the solution manual but I couldn't figure out why it is written the way it ...
- 59
4
votes
0
answers
57
views
Dual norm only for a part of matrix
A dual norm $\|\cdot\|^\circ$ of norm $\|\cdot\|$ can be given in terms of inner product
$$\|A\|^\circ=\max_B |\text{Tr}(AB)|,$$
with the constraint $\|B\|\leq1$. This can be re-expressed, for ...
- 1,150
1
vote
2
answers
1k
views
Dual cone's dual cone is the closure of primal cone's convex hull
Assume $K$ is a cone and its dual cone is $K^* = \{y:x^Ty \geq 0,\, \forall x \in K\}$. Then we have $K^{**} = \text{cl}(\text{conv}\ K)$, where cl means closure, conv means convex hull.
How to prove ...
- 147
1
vote
0
answers
113
views
Dual problem to SDP problem
I'm having problem with formulating dual problem to Semidefinite programing problem:
$$\max\;\;tr(X)$$
$$s.t.\;\; \left[ \begin{array}{cc}
A & X \\
X & B
\end{array} \right]\succeq0$$
where ...
- 11
0
votes
1
answer
298
views
Uniqueness of dual variable for convex optimization problem
recently, I have the following problem when designing the generalized benders decomposition.
Given the primal solution of a strict convex (nonlinear) optimization, is the dual variable computed from ...
0
votes
1
answer
109
views
For full-dimensional cone $K$, $x\in int(K)$, can you take arb. vector $y$ and for some $t$ small enough have that $x-ty\in int(K)$
I'm working on the proof of the following theorem:
$K$ full-dimensional, closed, convex cone. $x\in int(K) \iff y^Tx>0 \quad \forall y\in K^*-{0}$
And we're pretty set with the $\Leftarrow$ ...
- 446
0
votes
1
answer
319
views
Given a closed, convex, full-dimensional cone $K$, how do I show that $u\in int(K) \iff u^tx>0 \quad \forall x\in K^*-\{0\}$?
Given a closed, convex, full-dimensional cone $K$, how do I show that $x\in int(K) \iff y^Tx>0 \quad \forall y\in K^*- \{0\} $ ?
I've thought about applying the Hahn-Banach separation theorem
...
- 446
5
votes
2
answers
379
views
Characterizing the dual cone of the squares of skew-symmetric matrices
Let $X$ be the set of all real $n \times n$ diagonal matrices $D$ satisfying $\langle D,B^2 \rangle \le 0$ for any (real) skew-symmetric matrix $B$. (I am using the Frobenius Euclidean product here).
...
- 25.6k
1
vote
3
answers
419
views
A cone in $\mathbb{R}^n$ containing n linearly independent vectors has a non empty interior
I need a help with proving, that if a cone $K \subseteq \mathbb{R}^n$ contains $n$ linearly independent vectors, then the interior of $K$ is non empty.
Lets say $b_1,\dots,b_n \in K$ are the ...
- 323
0
votes
0
answers
362
views
Volume cut off from the sphere by the cone using cylindrical polar coordinates
Find the volume cut off from the sphere ${x^2}+{y^2}+{z^2}={a^2} $ by the cone ${x^2 }+{y^2} ={z^2}$ using cylindrical polar coordinates?
I know there will be a dual cone but I am not able to write ...
- 1
2
votes
1
answer
811
views
Find the dual cone $K^*_{m+}$ of $K_{m+} = \{ x \in \mathbb{R}^n \mid x_1 \ge x_2 \ge \dots \ge x_n \ge 0\}$
We define the monotone nonnegative cone as
$$K_{m+} = \{ x \in \mathbb{R}^n \mid x_1 \ge x_2 \ge \dots \ge x_n \ge 0\}$$
i.e. all nonnegative vectors with components sorted in nonincreasing order.
...
- 441
4
votes
3
answers
2k
views
Dual of a polyhedral cone
A general polyhedral cone $\mathcal{P} \subseteq \mathbb{R}^n$ can be represented as either $\mathcal{P} = \{x \in \mathbb{R}^n : Ax \geq 0 \}$ or $\mathcal{P} = \{V x : x \in \mathbb{R}_+^k , V \in \...
- 2,728
7
votes
1
answer
3k
views
Dual of a positive semidefinite cone
The PSD cone is the set of all positive semidefinite matrices. The dual is the set of all matrices $A$ such that tr($A^T X$) $\geq 0$ for all positive semidefinite matrices $X$.
How to prove that ...
- 2,728
0
votes
1
answer
868
views
Closure of a cone
Suppose a set $\mathcal{X}$ is closed and bounded, and define $\mathcal{K}_\mathcal{X} = \{(x,t) : t > 0, \frac{x}{t} \in \mathcal{X} \}$. Show that:
$$\bar{\mathcal{K}}_\mathcal{X} = \mathcal{K}_\...
- 2,728
1
vote
0
answers
64
views
Prooving the property of a polyhedral cone
Let me introduce some definitions. Poly$(v_1, v_2,\ldots, v_k) = \{ x \in \mathbb{R}^n \ | \ (x, v_i) \geq 0 \ \ \forall i \}$ called a polyhedral cone. For any cone $C$, $ \ C^{\lor} = \{ x \in \...
- 53
4
votes
1
answer
253
views
Epigraphical Cones, Fenchel Conjugates, and Duality
I'm trying to derive a result relating cones conceived as epigraphs of convex functions, duality, and Fenchel conjungates. Let me state exactly what I'm looking for:
Let $\mathbb{E}$ be an Euclidean ...
- 504
2
votes
1
answer
178
views
Is the dual of a conic program $\min_{x\in K} c^T x$ subject to $Ax=b$ also a conic program?
Let $A$ be an $m \times n$ matrix (over $\mathbb{R}$), $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$ and $K \subseteq \mathbb{R}^n $ is a closed, convex, pointed cone with non-empty interior. We define a ...
- 151
0
votes
1
answer
365
views
Derive the implicit cone equation from the implicit circle equation
Is it possible to derive the implicit equation of a cone $x^2+y^2-z^2=0$ from the circle equation $x^2+y^2=1$, which is the intersection between the cone and the hyperplane $\{(x,y,z)\in\Bbb R^3\,|\,z=...
1
vote
1
answer
743
views
Prove that a cone C is full-dimensional if and only if its dual cone $C^*$ is pointed.
A cone with apex $0$ is said to be pointed if it does not contain any non-trivial subspace. Let C be a closed convex cone with apex $0$. Show that $C$ is full-dimensional if and only if its dual cone $...
user533068
0
votes
1
answer
154
views
Minkowski sum of duals
I'm really struggling to prove the following statement:
Let $\mathbb{E}$ be an Euclidean space, let $K,K_p,S\subseteq\mathbb{E}$ be a proper cone, a polyhedral cone and a subspace, respectively. If ...
- 504
2
votes
0
answers
278
views
Is the nonnegative orthant isometric to itself under orthogonal mapping?
Problem description:
(Informal). I simply want to know if there exists a necessary and (or at least) sufficient condition for an orthogonal matrix to map every point of the nonnegative orthant (say ...
- 537
1
vote
0
answers
254
views
Tangent cone to $\ell_1$ norm constraint
We are given the $\ell_1$-constrained convex set $\mathcal{C} = \{ x \in \mathbb{R}^n : \| x \|_1 \leq 1 \}$, involved in a convex optimization problem. Moreover, we know that the optimal solution $x^{...
- 4,025
2
votes
1
answer
322
views
The dual of a regular polyhedral cone is regular
A rational polyhedral cone in $\mathbb{R}^n$ is a set of the form
$$\sigma=\{\lambda_1x_1+\dots+\lambda_kx_k\in \mathbb{R}^n\mid \lambda_i\in \mathbb{R}_{\geq 0} \; \;\forall \, 1\leq i\leq k\}$$
for ...
- 653
0
votes
0
answers
130
views
How to fix this dual cone?
Consider the following cone:
$$\mathbb{G}_n=\Bigg\{\,(x\oplus\theta\oplus\kappa) \in\mathbb{R}^n\oplus\mathbb{R}_+\oplus\mathbb{R}_+\,\colon \theta\sum_{i\in [n]}\exp\bigg(\frac{-x_i}{\theta}\bigg)\...
- 504
3
votes
1
answer
511
views
Dual of the relative entropy cone
I've been trying to calculate the dual cone of the relative entropy cone, which is given by:
$$\mathbb{H}_n = \Bigg\{\,(\theta\oplus \kappa\oplus x)\in\mathbb{R}^n_+\oplus\mathbb{R}_+^n\oplus\mathbb{...
- 504
0
votes
1
answer
208
views
Linear image of a dual cone
Let $\mathbb{E}$ and $\mathbb{Y}$ are Euclidean spaces, $K\subseteq\mathbb{E}$ is a proper cone and $A\colon\mathbb{E}\to\mathbb{Y}$ is a linear transformation, what is the relation between $A(K)^\ast$...
- 504
1
vote
0
answers
179
views
Dual of epigraph-type cones
I am trying to calculate the dual of some cones that I don't know 'a priori'.
For example, looking at MOSEK https://docs.mosek.com/MOSEKModelingCookbook-letter.pdf it seems that he already know the ...
- 504
0
votes
0
answers
60
views
Calculating the dual of a conic problem
I am struggling to calculate the dual of the following conic problem:
$$\inf\{a\lambda_a+b\lambda_b\,\colon w_1,w_2,\lambda_a,\lambda_b\in\mathbb{R}, (1,\lambda_a,w_2-w_1)\in\mathbb{G}_1 \text{, and} ...
- 504
1
vote
1
answer
188
views
What is the graph of a hyperbola where the two cones are split through the middle?
So If you have two cones stacked on top of each other like you see in a normal conic section, and the cones are split perfectly in two (1/2 of the diameter of the cone's base), how would you graph the ...
- 231
0
votes
1
answer
85
views
P normal cone of a cone metric space, given $\epsilon > 0$, can we choose c interior point of P ($c \gg 0$) s.t $\|c\| < \epsilon/K$ [closed]
I get this statment from paper "Cone metric spaces and fixed point theorems
of contractive mappings
Huang Long-Guang, Zhang Xian", i failed to understand why there is a guarantee that we can choose an ...
0
votes
1
answer
1k
views
How to prove that the dual of any set is a closed convex cone?
In page 3 of https://link.springer.com/content/pdf/10.1007%2Fs10107-005-0690-4.pdf . It is stated that "The dual of any set is a closed convex cone". I want to know how to prove this. We formulate the ...
- 2,963
1
vote
0
answers
301
views
KKT conditions for general conic optimization problem
From reading the literature, it seems that if we have a general conic optimization problem given by,
\begin{equation}
\begin{aligned}
& \underset{x}{\text{min}}
& & c^T x \\
& \text{s....
