feasibleSet

Purpose

Computes the feasible set of a given parametric problem.

Syntax

K = prob.feasibleSet()
K = prob.feasibleSet('method')
K = prob.feasibleSet(regions)

Description

Method for computing a feasible set of a given parametric problem. For the following formulation of a parametric problem

../../../../../fig/mpt/modules/solvers/@Opt/feasibleset4.png

the feasible set K is the polyhedron

../../../../../fig/mpt/modules/solvers/@Opt/feasibleset5.png

This method implements two procedures to compute K:
  1. if K=prob.feasibleSet('method') is called, the feasible set is calculated by a given 'method' used in projection (can be expensive)
  2. if K=prob.feasibleSet(regions) is called with "regions" being the critical regions of the parametric solution, then K is constructed as follows. For each facet of each region do:
    1. compute the center of the facet
    2. take a small step accross the facet
    3. solve the problem for the new point
    4. if the problem is infeasible, add the facet to the feasible set

Input Arguments

method

A string describing which method of projection to use for computing the feasible set. For more help of the methods type help Polyhedron/projection.

Class: char

regions

A polyhedron array for which to describe the feasible set. The polyhedra must be in the same dimension.

Class: Polyhedron

Output Arguments

K

The computed feasible set for the given parametric optimization problem.

Class: Polyhedron

Example(s)

Example 1

Create parametric LP with 3 decision variables and 2 parameters The cost function ../../../../../fig/mpt/modules/solvers/@Opt/feasibleset1.png
 f = [1; -1; 0.5]; pF = [1 -1.2; -0.8 -2.1; 3.1 0]; 
 The linear inequality constraints ../../../../../fig/mpt/modules/solvers/@Opt/feasibleset2.png
      
 A = [-11.15 -16.28 -8.09; 6.85 16.17 11.61; 10.37 2.64  5.92; 18.22 -11.28 2.42; -5.29 -5.6 2.4];

 b = [ 1.43; 3.49; 3.98; 2.2; 2.23]; 

 B = [ -0.11 0.5; -0.89 -0.83; 0.74 0.2; 1.39 -1.01; 2.47 -0.62]; 
 Provide bounds on the parameters ../../../../../fig/mpt/modules/solvers/@Opt/feasibleset3.png 
      
 Ath = [eye(2); -eye(2)]; bth = [2;2;5;5]; 
 Create the parametric optimization problem 
 problem = Opt('f',f,'A',A,'b',b,'pB',B,'pF',pF,'Ath',Ath,'bth',bth) 
-------------------------------------------------
Parametric linear program
	Num variables:                3
	Num inequality constraints:   5
	Num equality constraints:     0
	Num parameters:               2
	Solver:                     PLCP
-------------------------------------------------
We want to compute the feasible set of the parametric optimization problem.
 K = problem.feasibleSet() 
Polyhedron in R^2 with representations:
    H-rep (redundant)   : Inequalities   4 | Equalities   0
    V-rep               : Unknown (call computeVRep() to compute)
Functions : none
The feasible set represents a region where there exist a feasible set of constraints. Now compute the solution by solving the parametric optimization problem:
 res = problem.solve 
mpt_plcp: 8 regions

res = 

        xopt: [1x1 PolyUnion]
    exitflag: 1
         how: 'ok'
       stats: [1x1 struct]

The parametric solver returns regions with the optimal solution to the parametric optimization problem. The union of these regions is a subset of the feasible set K because in some parts of the feasible space the cost function can be unbounded and therefore the optimality conditions do not hold. On the figure below one can see that in this example the union of regions returned from the parametric solver is a subset of the feasible set K.
 K.plot('wire',true,'linewidth',2,'linestyle','--');
            hold on;
            res.xopt.plot
        

../../../../../fig/mpt/modules/solvers/@Opt/feasibleset_img_1.png

See Also

opt


© 2003-2013 Michal Kvasnica: STU Bratislava, michal.kvasnica@stuba.sk