1
$\begingroup$

my question is about functions of the following form:

$$ f(t) = \max_{\mathbf{x}}~ \mathbf{c^T x} ~ {\rm s.t. \mathbf{Ax} +t \cdot \mathbf{a} \leq \mathbf{b}}, $$ where $\mathbf{x},\mathbf{b}, $ and $\mathbf{a} $ are vectors and $\mathbf{A} $ is matrix.

Here, the evaluation of $f(t)$ requires to compute the solution of linear optimization problem. I wonder if there is literature available on such functions. In particular I would like to have information about

  • the form and properties
  • extrema

of this function. Moreover, I would like to know if there is an simple way to obtain function evaluations that do not require to solve an optimization problem.

$\endgroup$

3 Answers 3

2
$\begingroup$

Here is a well-known approach in linear parametric optimization for describing behaviors of $f$. Let us see the function $f$ in the dual form. Under some consideration, we have: $$f(t) = \min_y (b-at)^Ty ,\mbox{ s.t. } yA \ge c$$ Now, the feasible region is fixed and the objective function depend on $t$. Let $\{y_1,\ldots,y_k\}$ be the set of extreme point of the feasible region and suppose that the feasible region is bounded. Then, we have $$f(t) = \min_i (b-at)^Ty_i$$ So, $f(t)$ is a piecewise linear function.

$\endgroup$
1
$\begingroup$

Parametric Programming, also known as Multi-Parametric Programming https://en.wikipedia.org/wiki/Parametric_programming is the name of the field you're looking for. It is particularly well developed for Linear (the case you presented) and Convex Quadratic Programming.

A good introduction to the field is Multiā€Parametric Programming: Volume 1: Theory, Algorithms, and Applications, Volume 1, edited by Editor(s): Efstratios N. Pistikopoulos, Michael C. Georgiadis, Vivek Dua. There are a number of other books and articles.

$\endgroup$
1
$\begingroup$

This is sometimes called the "optimal value function". I remember that Rockafellar/Wets "Variational Analysis" treats this in some generality.

If you could evaluate the function without solving an optimization problem, you would essentially be solving linear programs with solving them, so no, this is not possible. However, there may be something you can do if you need to evaluate the function at many point. You may want to look at homotopy methods for linear programming (roughly speaking: the solution of the problem for some $t$ may give hints about the solution for another $t$...).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.