help-glpk
[Top][All Lists]

## [Help-glpk] Re: sensitivity analysis

 From: Yingjie Lan Subject: [Help-glpk] Re: sensitivity analysis Date: Sat, 16 Jan 2010 17:03:07 -0800 (PST)

```> > I'm looking forward to it. In
> the example you have given, the
> > params are linearly dependent on t -- what if the
> dependence is
> > non-linear?
>
> Non-linear dependence leads to a non-linear program, so in
> this case
> the simplex method cannot be applied.
>

No, I am not saying it is non-linear program, it is still
a linear program, but the parameters may be a non-linear
function of scaler t. In a more general case, t could be
a vector. A little bit like the confidence region in
statistic analysis, we could have a simultaneous region
of all the right-hand sides, for example. Such a region
could be a polytope with the single parameter bounds as
its extreme points (a good paper could be produced on
this, if not yet done), I think, but this is just an initial
conjecture. Then you could have a curve/shape parametrized
on t (t could be a vector). All you need is to find out the
intersection of the curve/shape thing with the conjectured
polytope thing. This is certainly a very difficult problem,
I am not talking about analytical solution, I am only talking
about numerical -- it is still very difficult.

> > When the params (not just rhs, coefs, but also any
> entry in the
> > contraint matrix) depends nonlinearly on scaler t, I
> wonder if there
> > are some efficient algorithms. This problem seems
> extremely hard,
>
> Harder, but not extremely, because you have only one
> parameter, so
> some one-dimensional methods can be used, even a brute
> force technique.

True, even for one scaler t, but it is much harder than
solving for all the roots of a polynomial (for, even if all
the parameters depend polynomially on t, you still have
a boundary region at least as complicated as a polytope).

>
> >  as
> > the set of t that shares the same optimal basis might
> be many disjoint
> > intervals. We might just be satisfied with identifying
> one particular
> > interval of t that contains some initial t_0.
>
> Could you provide an example of the dependence?
>

A simple form could be polynomial dependence on scaler t.

```