http://www.convexoptimization.com/wikimization/index.php?title=Presolver&offset=20110823075104&limit=20&action=history&feed=atomPresolver - Revision history2024-03-29T04:58:46ZRevision history for this page on the wikiMediaWiki 1.11.0http://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=3111&oldid=prevRanjelin: /* Assumptions */2016-10-04T04:23:12Z<p><span class="autocomment">Assumptions</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 04:23, 4 October 2016</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 87:</td>
<td colspan="2" class="diff-lineno">Line 87:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The test we choose is proof by counterexample:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The test we choose is proof by counterexample:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>given matrix <math>A\,</math> having no zero columns,</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>given matrix <math>A\,</math> having no zero columns,</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><center><math>\begin{array}{rl}<del style="color: red; font-weight: bold; text-decoration: none;">\mbox</del>{find}&x\\</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><center><math>\begin{array}{rl}{<ins style="color: red; font-weight: bold; text-decoration: none;">\text </ins>find}&x\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>\mbox{subject to}&A_{}x=\mathbf{0}\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>\mbox{subject to}&A_{}x=\mathbf{0}\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&\mathbf{1}^{\rm T}x=1\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&\mathbf{1}^{\rm T}x=1\\</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 119:</td>
<td colspan="2" class="diff-lineno">Line 119:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>For full-dimensional pointed closed convex cone <math>\mathcal{K}\,</math></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>For full-dimensional pointed closed convex cone <math>\mathcal{K}\,</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>described by given matrix <math>A\,</math></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>described by given matrix <math>A\,</math></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><center><math>\begin{array}{rl}\<del style="color: red; font-weight: bold; text-decoration: none;">mbox{</del>find}_{x<del style="color: red; font-weight: bold; text-decoration: none;">\</del>,<del style="color: red; font-weight: bold; text-decoration: none;">,\;</del>y}&y<del style="color: red; font-weight: bold; text-decoration: none;">^{</del>\<del style="color: red; font-weight: bold; text-decoration: none;">!}\neq_{\!}</del>\mathbf{0}\\</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><center><math>\begin{array}{rl}<ins style="color: red; font-weight: bold; text-decoration: none;">{</ins>\<ins style="color: red; font-weight: bold; text-decoration: none;">text </ins>find}_{x,y}&y\<ins style="color: red; font-weight: bold; text-decoration: none;">not=</ins>\mathbf{0}\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>\mbox{subject to}&b^{\rm T}y=0\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>\mbox{subject to}&b^{\rm T}y=0\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&A^{\rm T}y\succeq0\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&A^{\rm T}y\succeq0\\</div></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2941&oldid=prevRanjelin: /* Introduction */2011-12-05T06:51:29Z<p><span class="autocomment">Introduction</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 06:51, 5 December 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 21:</td>
<td colspan="2" class="diff-lineno">Line 21:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ & g(x)_{\!}\in\mathcal{S}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ & g(x)_{\!}\in\mathcal{S}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ & x\succeq0</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ & x\succeq0</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div> \\ & x_{j\!}\in\mathbb{Z}<del style="color: red; font-weight: bold; text-decoration: none;">~</del>,\qquad j\in\mathcal{J}</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> \\ & x_{j\!}\in\mathbb{Z}<ins style="color: red; font-weight: bold; text-decoration: none;">\,</ins>,\qquad j\in\mathcal{J}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \end{array}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \end{array}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2940&oldid=prevRanjelin: /* Introduction */2011-12-05T06:50:37Z<p><span class="autocomment">Introduction</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 06:50, 5 December 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==Introduction==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>==Introduction==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>''Presolving'' conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>''Presolving'' conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem.</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Presented with constraints <math>a^{\rm T}x_{\!}=_{\!}0\,,<del style="color: red; font-weight: bold; text-decoration: none;">~</del>x\succeq0</math> for example,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Presented with constraints <math>a^{\rm T}x_{\!}=_{\!}0\,,<ins style="color: red; font-weight: bold; text-decoration: none;">\,\,</ins>x\succeq0</math> for example,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>a presolver is likely to check whether constant vector <math>a\,</math> is positive; for if so,</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>a presolver is likely to check whether constant vector <math>a\,</math> is positive; for if so,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>variable <math>\,x</math> can have only the trivial solution.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>variable <math>\,x</math> can have only the trivial solution.</div></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2939&oldid=prevRanjelin: /* Introduction */2011-12-05T06:44:52Z<p><span class="autocomment">Introduction</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 06:44, 5 December 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 82:</td>
<td colspan="2" class="diff-lineno">Line 82:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>It is now prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>It is now prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>(the columns of <math>A<del style="color: red; font-weight: bold; text-decoration: none;">\,</del></math>)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>(the columns of <math>A</math>)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>describe a pointed cone.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>describe a pointed cone.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A practical test for pointedness therefore attempts to establish existence of a line.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A practical test for pointedness therefore attempts to establish existence of a line.</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 92:</td>
<td colspan="2" class="diff-lineno">Line 92:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&x\succeq0.\end{array}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&x\succeq0.\end{array}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>This test says that if <math>\mathcal{K}</math> contains a line, then some conic combination of its generators can be made to point opposite in direction to another <math>(A_{}x\!=<del style="color: red; font-weight: bold; text-decoration: none;">\!</del>\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>This test says that if <math>\mathcal{K}</math> contains a line, then some conic combination of its generators can be made to point opposite in direction to another <math>(A_{}x\!=\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 125:</td>
<td colspan="2" class="diff-lineno">Line 125:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&x\succeq0\end{array}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&x\succeq0\end{array}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>this linear feasibility problem has a solution iff <math>b\!\in<del style="color: red; font-weight: bold; text-decoration: none;">\!</del>\partial\mathcal{K}\,</math>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>this linear feasibility problem has a solution iff <math>b\!\in\partial\mathcal{K}\,</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The requirement that <math>\mathcal{K}</math> be full-dimensional is equivalent to the condition that fat matrix <math>A\,</math> be full rank.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>The requirement that <math>\mathcal{K}</math> be full-dimensional is equivalent to the condition that fat matrix <math>A\,</math> be full rank.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This feasibility problem is a statement of boundary membership relation from convex analysis []...</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This feasibility problem is a statement of boundary membership relation from convex analysis []...</div></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2920&oldid=prevRanjelin at 20:49, 24 November 20112011-11-24T20:49:30Z<p></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 20:49, 24 November 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 26:</td>
<td colspan="2" class="diff-lineno">Line 26:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>where <math>A\,</math> is a real <math>m\!\times_{\!}n</math> matrix, </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>where <math>A\,</math> is a real <math>m\!\times_{\!}n</math> matrix, </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><math>\mathbb{Z}</math> represents the integers, </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><math>\mathbb{Z}</math> represents the integers, </div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><math>\<del style="color: red; font-weight: bold; text-decoration: none;">reals</del></math> the real numbers,</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><math>\<ins style="color: red; font-weight: bold; text-decoration: none;">mathbb{R}</ins></math> the real numbers,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><math>\mathcal{S}</math> is some predetermined set,</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><math>\mathcal{S}</math> is some predetermined set,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>and <math>\mathcal{J}</math> is some possibly empty index set.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>and <math>\mathcal{J}</math> is some possibly empty index set.</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 50:</td>
<td colspan="2" class="diff-lineno">Line 50:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Finite circular cones hold ice cream and block road traffic in daily life.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Finite circular cones hold ice cream and block road traffic in daily life.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Each of the great Pyramids of Egypt is a finite polyhedral cone. </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Each of the great Pyramids of Egypt is a finite polyhedral cone. </div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>The geometer defines a polyhedral (semiinfinite) cone <math>\,\mathcal{K}</math> in <math>\,\<del style="color: red; font-weight: bold; text-decoration: none;">reals</del>^m</math> as a set</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>The geometer defines a polyhedral (semiinfinite) cone <math>\,\mathcal{K}</math> in <math>\,\<ins style="color: red; font-weight: bold; text-decoration: none;">mathbb{R}</ins>^m</math> as a set</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><center><math>\mathcal{K}<del style="color: red; font-weight: bold; text-decoration: none;">\triangleq</del>\{A_{}x~|~x\succeq0\}</math></center></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><center><math>\mathcal{K}<ins style="color: red; font-weight: bold; text-decoration: none;">=</ins>\{A_{}x~|~x\succeq0\}</math></center></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>that is closed and convex but not necessarily pointed (might not have a vertex).</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>that is closed and convex but not necessarily pointed (might not have a vertex).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2919&oldid=prevRanjelin: /* Introduction */2011-11-24T20:48:15Z<p><span class="autocomment">Introduction</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 20:48, 24 November 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 17:</td>
<td colspan="2" class="diff-lineno">Line 17:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \begin{array}{rl}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \begin{array}{rl}</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div> \mbox{minimize}_{x\in_{}\mathbb{R}<del style="color: red; font-weight: bold; text-decoration: none;">^{</del>^n<del style="color: red; font-weight: bold; text-decoration: none;">}</del>} & f(x)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> \mbox{minimize}_{x\in_{}\mathbb{R}^n} & f(x)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ \mbox{subject to} & A_{}x=b</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ \mbox{subject to} & A_{}x=b</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ & g(x)_{\!}\in\mathcal{S}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div> \\ & g(x)_{\!}\in\mathcal{S}</div></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2832&oldid=prevRanjelin: /* Assumptions */2011-11-15T20:16:29Z<p><span class="autocomment">Assumptions</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 20:16, 15 November 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 92:</td>
<td colspan="2" class="diff-lineno">Line 92:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&x\succeq0.\end{array}</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&x\succeq0.\end{array}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>This test says that if <math>\mathcal{K}</math> contains a line, then <del style="color: red; font-weight: bold; text-decoration: none;">at least two </del>of its generators point <del style="color: red; font-weight: bold; text-decoration: none;">in </del>opposite <del style="color: red; font-weight: bold; text-decoration: none;">directions </del><math>(A_{}x\!=\!\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>This test says that if <math>\mathcal{K}</math> contains a line, then <ins style="color: red; font-weight: bold; text-decoration: none;">some conic combination </ins>of its generators <ins style="color: red; font-weight: bold; text-decoration: none;">can be made to </ins>point opposite <ins style="color: red; font-weight: bold; text-decoration: none;">in direction to another </ins><math>(A_{}x\!=\!\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>If there is an <math>x\,</math> solving this convex feasibility problem, then the cone described by <math>A\,</math> cannot be pointed.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
</table>Ranjelinhttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2795&oldid=prevMikesaunders at 07:20, 7 September 20112011-09-07T07:20:15Z<p></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 07:20, 7 September 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 79:</td>
<td colspan="2" class="diff-lineno">Line 79:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}.</math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}.</math></center></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This condition is necessary and sufficient to establish pointedness.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This condition is necessary and sufficient to establish pointedness.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>'''Halfspace figure as example of cone that contains line...'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">So it </del>is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">It </ins>is <ins style="color: red; font-weight: bold; text-decoration: none;">now </ins>prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>(the columns of <math>A\,</math>)</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>(the columns of <math>A\,</math>)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>describe a pointed cone.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>describe a pointed cone.</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>A practical test for pointedness therefore attempts to establish existence of a line<del style="color: red; font-weight: bold; text-decoration: none;">; a </del>proof by counterexample:</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>A practical test for pointedness therefore attempts to establish existence of a line<ins style="color: red; font-weight: bold; text-decoration: none;">.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">The test we choose is </ins>proof by counterexample:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>given matrix <math>A\,</math> having no zero columns,</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>given matrix <math>A\,</math> having no zero columns,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math>\begin{array}{rl}\mbox{find}&x\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math>\begin{array}{rl}\mbox{find}&x\\</div></td></tr>
</table>Mikesaundershttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2794&oldid=prevMikesaunders: /* Geometry of Constraints */2011-09-07T07:07:46Z<p><span class="autocomment">Geometry of Constraints</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 07:07, 7 September 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 71:</td>
<td colspan="2" class="diff-lineno">Line 71:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>====Assumptions====</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>====Assumptions====</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>'''1) <del style="color: red; font-weight: bold; text-decoration: none;"><math>\mathcal{K}</math> </del>Pointedness.'''&nbsp; </div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>'''1) Pointedness <ins style="color: red; font-weight: bold; text-decoration: none;">of cones</ins>.'''&nbsp; </div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Our presolve method applies only to pointed polyhedral cones<del style="color: red; font-weight: bold; text-decoration: none;">.</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Our presolve method applies only to pointed polyhedral cones<ins style="color: red; font-weight: bold; text-decoration: none;">,</ins></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">We invoke a definition saying </del>that <del style="color: red; font-weight: bold; text-decoration: none;">a pointed cone contains </del>no ''line''.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">namely cones </ins>that <ins style="color: red; font-weight: bold; text-decoration: none;">contain </ins>no ''line''.</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite <del style="color: red; font-weight: bold; text-decoration: none;">direction</del>.)</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite <ins style="color: red; font-weight: bold; text-decoration: none;">directions</ins>.)</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">This is equivalent to the statement that a pointed </del>cone <math>\mathcal{K}</math> and its ''polar cone'' <math>-\mathcal{K}</math> intersect only at the origin:</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">A </ins>cone <ins style="color: red; font-weight: bold; text-decoration: none;"> </ins><math>\mathcal{K}</math> <ins style="color: red; font-weight: bold; text-decoration: none;">contains no line if and only if the cone</ins></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}</math></center></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>and its ''polar cone'' <math>-\mathcal{K}</math> intersect only at the origin:</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">which </del>is necessary and sufficient to establish pointedness.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}<ins style="color: red; font-weight: bold; text-decoration: none;">.</ins></math></center></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">This condition </ins>is necessary and sufficient to establish pointedness.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>So it is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>So it is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td></tr>
</table>Mikesaundershttp://www.convexoptimization.com/wikimization/index.php?title=Presolver&diff=2793&oldid=prevMikesaunders: /* Geometry of Constraints */2011-09-07T06:36:45Z<p><span class="autocomment">Geometry of Constraints</span></p>
<table style="background-color: white; color:black;">
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr>
<td colspan='2' style="background-color: white; color:black;">←Older revision</td>
<td colspan='2' style="background-color: white; color:black;">Revision as of 06:36, 7 September 2011</td>
</tr>
<tr><td colspan="2" class="diff-lineno">Line 63:</td>
<td colspan="2" class="diff-lineno">Line 63:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>But <math>A\,</math> can have more than four columns and still describe the same Pyramid. </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>But <math>A\,</math> can have more than four columns and still describe the same Pyramid. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>For such a fat <math>A\,</math>, each additional column resides anywhere in <math>\mathcal{K}\,</math>:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>For such a fat <math>A\,</math>, each additional column resides anywhere in <math>\mathcal{K}\,</math>:</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>either interior to the cone <math>(\{A_{}x~|~x\succ0\})</math> or on one of its ''faces'' (the vertex, an edge, or facet). </div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>either interior to the cone <math>(\{A_{}x~|~x\succ0\})</math> or on one of its ''faces'' (the vertex, an edge, or <ins style="color: red; font-weight: bold; text-decoration: none;">a </ins>facet). </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid,</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid,</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>and they can have any number of edges and facets. </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>and they can have any number of edges and facets. </div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>We assume a pointed polyhedral cone throughout, so there can be only one vertex </div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>We assume a <ins style="color: red; font-weight: bold; text-decoration: none;">''</ins>pointed<ins style="color: red; font-weight: bold; text-decoration: none;">'' </ins>polyhedral cone throughout, so there can be only one vertex </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>(which resides at the origin in Euclidean space by definition).</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>(which resides at the origin in Euclidean space by definition).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>====<del style="color: red; font-weight: bold; text-decoration: none;">assumptions</del>====</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>====<ins style="color: red; font-weight: bold; text-decoration: none;">Assumptions</ins>====</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>'''1) <math>\mathcal{K}</math> Pointedness.'''&nbsp; </div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>'''1) <math>\mathcal{K}</math> Pointedness.'''&nbsp; </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Our presolve method applies only to pointed polyhedral cones.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>Our presolve method applies only to pointed polyhedral cones.</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">So it is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math>, </del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>We <ins style="color: red; font-weight: bold; text-decoration: none;">invoke </ins>a definition saying that a pointed cone contains no <ins style="color: red; font-weight: bold; text-decoration: none;">''</ins>line<ins style="color: red; font-weight: bold; text-decoration: none;">''</ins>.</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">the columns of <math>A\,</math>,</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">(Recall that a line is a 1-dimensional Euclidean body that extends infinitely in two opposite direction.)</ins></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del style="color: red; font-weight: bold; text-decoration: none;">describe a pointed cone.</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>This is equivalent to the statement that a pointed cone <math>\mathcal{K}</math> and its ''polar <ins style="color: red; font-weight: bold; text-decoration: none;">cone</ins>'' <math>-\mathcal{K}</math> intersect only at the origin<ins style="color: red; font-weight: bold; text-decoration: none;">:</ins></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>We <del style="color: red; font-weight: bold; text-decoration: none;">utilize </del>a definition saying that a pointed cone contains no line.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div></div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>This is equivalent to the statement that a pointed cone <math>\mathcal{K}</math> and its ''polar'' <math>-\mathcal{K}</math> intersect only at the origin<del style="color: red; font-weight: bold; text-decoration: none;">;</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}</math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div><center><math>\mathcal{K}\,\cap-\mathcal{K}=\{\mathbf{0}\}</math></center></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>which is necessary and sufficient to establish pointedness.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>which is necessary and sufficient to establish pointedness.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>So it is prudent to ask whether a given set of ''generators'' for <math>\mathcal{K}\,</math></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>(the columns of <math>A\,</math>)</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>describe a pointed cone.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A practical test for pointedness therefore attempts to establish existence of a line; a proof by counterexample:</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>A practical test for pointedness therefore attempts to establish existence of a line; a proof by counterexample:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>given matrix <math>A\,</math> having no zero columns,</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>given matrix <math>A\,</math> having no zero columns,</div></td></tr>
<tr><td colspan="2" class="diff-lineno">Line 85:</td>
<td colspan="2" class="diff-lineno">Line 87:</td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>\mbox{subject to}&A_{}x=\mathbf{0}\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>\mbox{subject to}&A_{}x=\mathbf{0}\\</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&\mathbf{1}^{\rm T}x=1\\</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>&\mathbf{1}^{\rm T}x=1\\</div></td></tr>
<tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>&x\succeq0\end{array}</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>&x\succeq0<ins style="color: red; font-weight: bold; text-decoration: none;">.</ins>\end{array}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div></math></center></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This test says that if <math>\mathcal{K}</math> contains a line, then at least two of its generators point in opposite directions <math>(A_{}x\!=\!\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>This test says that if <math>\mathcal{K}</math> contains a line, then at least two of its generators point in opposite directions <math>(A_{}x\!=\!\mathbf{0})</math>. Constraint <math>\mathbf{1}^{\rm T}x\!=\!1</math> precludes the trivial solution.</div></td></tr>
</table>Mikesaunders