Convex cones

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 15: Line 15:
===proof===
===proof===
We construct an injectivity argument from vector <math>\,x\,</math> to the set <math>\,\{t_i^\star\}\,</math>
We construct an injectivity argument from vector <math>\,x\,</math> to the set <math>\,\{t_i^\star\}\,</math>
-
where <math>\,t_i^\star\!=d_{v_i}(x)\,</math>.
+
where <math>\,t_i^\star\mathrel{\stackrel{\Delta}{=}}\,d_{v_i}(x)\,</math>.
In other words, we assert that there is no <math>\,x\,</math> except <math>\,x\!=\!0\,</math> that nulls all the <math>\,t_i\,</math>;
In other words, we assert that there is no <math>\,x\,</math> except <math>\,x\!=\!0\,</math> that nulls all the <math>\,t_i\,</math>;
-
''i.e.'', there is no nullspace to the operation.
+
''i.e.'', there is no nullspace to operator <math>\,d\,</math> over all <math>\,v_i\,</math>.
-
<math>\,d_v(x)\,</math> is the optimal objective value of a (primal) conic program:
+
 
 +
Function <math>\,d_v(x)\,</math> is the optimal objective value of a (primal) conic program:
<math>\,\begin{array}{cl}\mathrm{maximize}_t&t\\
<math>\,\begin{array}{cl}\mathrm{maximize}_t&t\\
-
\mathrm{subject~to}&x-t^{}v\in\mathcal{K}\end{array}</math>
+
\mathrm{subject~to}&x-t^{}v\in\mathcal{K}\end{array}\quad{\rm(p)}</math>
-
Because the dual geometry of this problem is easier to visualize,
+
Because dual geometry of this problem is easier to visualize,
-
we instead interpret the dual conic program:
+
we instead interpret its dual:
<math>\,\begin{array}{cl}\mathrm{minimize}_\lambda&\lambda^{\rm T}x\\
<math>\,\begin{array}{cl}\mathrm{minimize}_\lambda&\lambda^{\rm T}x\\
\mathrm{subject~to}&\lambda\in\mathcal{K}^*\\
\mathrm{subject~to}&\lambda\in\mathcal{K}^*\\
-
&\lambda^{\rm T}v=1\end{array}</math>
+
&\lambda^{\rm T}v=1\end{array}~\qquad{\rm(d)}</math>
where <math>\,\mathcal{K}^*\,</math> is the dual cone, which is full-dimensional, closed, pointed, and convex because <math>\,\mathcal{K}\,</math> is.
where <math>\,\mathcal{K}^*\,</math> is the dual cone, which is full-dimensional, closed, pointed, and convex because <math>\,\mathcal{K}\,</math> is.

Revision as of 22:05, 28 August 2008

Nonorthogonal projection on extreme directons of convex cone

pseudo coordinates

Let LaTeX: \mathcal{K} be a full-dimensional closed pointed convex cone in finite-dimensional Euclidean space LaTeX: \mathbb{R}^n.

For any vector LaTeX: \,v\, and a point LaTeX: \,x\!\in\!\mathcal{K}, define LaTeX: \,d_v(x)\, to be the largest number LaTeX: \,t^\star such that LaTeX: \,x-t^{}v\!\in\!\mathcal{K}\,.

Suppose LaTeX: \,x\, and LaTeX: \,y\, are points in LaTeX: \,\mathcal{K}\,.

Further, suppose that LaTeX: \,d_v(x)\!=_{\!}d_v(y)\, for each and every extreme direction LaTeX: \,v_i\, of LaTeX: \,\mathcal{K}\,.

Then LaTeX: \,x\, must be equal to LaTeX: \,y\,.

proof

We construct an injectivity argument from vector LaTeX: \,x\, to the set LaTeX: \,\{t_i^\star\}\, where LaTeX: \,t_i^\star\mathrel{\stackrel{\Delta}{=}}\,d_{v_i}(x)\,.

In other words, we assert that there is no LaTeX: \,x\, except LaTeX: \,x\!=\!0\, that nulls all the LaTeX: \,t_i\,; i.e., there is no nullspace to operator LaTeX: \,d\, over all LaTeX: \,v_i\,.


Function LaTeX: \,d_v(x)\, is the optimal objective value of a (primal) conic program:

LaTeX: \,\begin{array}{cl}\mathrm{maximize}_t&t\\ \mathrm{subject~to}&x-t^{}v\in\mathcal{K}\end{array}\quad{\rm(p)}

Because dual geometry of this problem is easier to visualize, we instead interpret its dual:

LaTeX: \,\begin{array}{cl}\mathrm{minimize}_\lambda&\lambda^{\rm T}x\\ \mathrm{subject~to}&\lambda\in\mathcal{K}^*\\ &\lambda^{\rm T}v=1\end{array}~\qquad{\rm(d)}

where LaTeX: \,\mathcal{K}^*\, is the dual cone, which is full-dimensional, closed, pointed, and convex because LaTeX: \,\mathcal{K}\, is.

The primal optimal objective value equals the dual optimal value under the sufficient Slater condition, which is well known;

i.e., we assume

LaTeX: \,t^\star=\,\lambda^{\star\rm T}x\,

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Convex_cones"
Personal tools