extreme

Purpose

Compute extremal point of a polyhedron in a given direction.

Syntax

sol = P.extreme(y)

Description

P.extreme(y) solves the following problem:

../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme6.png

and returns the optimizer / extreme point ../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme1.png.

Input Arguments

P

Polyhedron in any format.

Class: Polyhedron

y

Direction to compute the extreme point.

Class: double

Output Arguments

sol

Support of ../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme2.png in ../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme3.png.

Class: struct

sol.exitflag

Integer value informing about the termination status of the optimization.

Class: double

sol.x

An optimizer of ../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme4.png

Class: double

sol.supp

Optimal value of ../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme5.png

Class: double

Example(s)

Example 1

Create random polytope:
P = Polyhedron('H', [randn(20,2) ones(20,1)])
Polyhedron in R^2 with representations:
    H-rep (redundant)   : Inequalities  20 | Equalities   0
    V-rep               : Unknown (call computeVRep() to compute)
Functions : none
Compute extreme point in random direction
y = randn(2,1); sol = P.extreme(y);
Plot the point sol.x and the supporting hyperplane 
plot(P, 'alpha', 0.2);  hold on;
		plot(sol.x(1),sol.x(2),'ro','markersize',10);
		Polyhedron('He', [y' sol.supp], 'lb', -[1;1], 'ub', [1;1]).plot;
		

../../../../../../fig/mpt/modules/geometry/sets/@Polyhedron/extreme_img_1.png

References

[1] Fukuda: PolyFaq


© 2010-2013 Colin Neil Jones: EPF Lausanne, colin.jones@epfl.ch