Convex cones

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 14: Line 14:
===proof===
===proof===
-
<math>\,d_v(x)\,</math> is the optimal value of a conic program:
+
<math>\,d_v(x)\,</math> is the optimal objective value of a conic program:
-
<math>\,\begin{array}{rl}\mathrm{maximize}&t\\
+
<math>\,\begin{array}{cl}\mathrm{maximize}&t\\
\mathrm{subject~to}&x-t^{}v\in\mathcal{K}\end{array}</math>
\mathrm{subject~to}&x-t^{}v\in\mathcal{K}\end{array}</math>
 +
 +
Because the dual geometry of this problem is easier to visualize,
 +
we instead interpret the dual conic program:
 +
 +
<math>\,\begin{array}{cl}\mathrm{minimize}_\lambda&\lambda^{\rm T}x\\
 +
\mathrm{subject~to}&\lambda\in\mathcal{K}^*\\
 +
&\lambda^{\rm T}v=1\end{array}</math>
 +
 +
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 20:10, 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 every extreme direction LaTeX: \,v\, of LaTeX: \,\mathcal{K}\,.

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

proof

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

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

Because the dual geometry of this problem is easier to visualize, we instead interpret the dual conic program:

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}

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

Personal tools