4
$\begingroup$

I have a linear programming problem

min $c^T x$

$Ax\leq b$

However, in my problem, $A$ contains also some variables $y$, e.g.

$$A = \begin{pmatrix} y_1 & 4 \\ 3 & y_2 \end{pmatrix}$$

I want to find a value of $y$ such that the solution $x$ of the LP, for that fixed choice of $y$, is positive.

This question is different than normal formulation of parametric LP which typically only involves parameters in the cost vector or right-hand side of the constraints, and I do not want to simply use nonlinear programing. Any good solution?

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "the solution of LP is positive"? Do you mean that all variables $y$ are positive? $\endgroup$
    – Aron Ahmadia
    Commented Aug 3, 2012 at 16:39
  • 1
    $\begingroup$ In the literature, parametric linear programming refers to something different -- the situation in which a solution must be found for all $y$ values in some interval. $\endgroup$
    – David Ketcheson
    Commented Aug 7, 2012 at 8:17

1 Answer 1

Reset to default
5
$\begingroup$

As (almost) always in parametric programming, you have to encode optimality of $x$, for a given $y$, using optimality conditions.

$c + A(y)^T\lambda=0$ (stationarity)

$\lambda^T(b-A(y)x)=0$ (complementarity)

$\lambda\geq 0,b-A(y)x\geq 0$ (dual and primal feasibility)

To solve your problem, you solve a feasibility problem with the KKT conditions above, and the additional constraint $x\geq 0$. In other words, effectively solving a bilevel program, where the outer program has no objective and a simple bound constraint.

Parametric/bilevel programming is hard, and as you probably realized, with parametric $A$ is even harder as it doesn't retain the polytopic properties of parametric linear programming. I don't think there is any straightforward way to solve the problem beyond simply attacking the problem just posed using global nonlinear programming.

EDIT By using the stationarity constraint in the complementarity constraint, bilinear constraints arise (still nonconvex of-course)

$c + A(y)^T\lambda=0$ (stationarity)

$\lambda^Tb + c^Tx=0$ (rewritten complementarity)

$\lambda\geq 0,b-A(y)x\geq 0$ (dual and primal feasibility)

Note, in case someone is missing the point with optimality conditions, we are not looking for a solution in $(x,y)$ to the problem minimize $c^Tx$ subject to $A(y)x\leq b, x\geq 0$. As an example (using parametric $b$ instead of $A$ for simplicity), let us find a fixed value $y$ such that the optimal solution $x$ to minimize $x$ subject to $x\geq y$ is non-negative. The solution to this problem is any $y\geq 0$ (since with these fixed values of $y$ the LP will return the non-negative solution $x=y\geq 0$). However, if we simply merge the constraints and minimize $x$ subject $x\geq y, x\geq 0$, over $x$ and $y$, the optimal solution is $x=0$ and $y$ any non-positive number. A completely wrong solution, since using this non-positive number (-2 for example) in the LP will lead to an infeasible $x$ (-2).

Improve this answer
$\endgroup$
14
  • $\begingroup$ Do you mind specifically addressing what's wrong with David Ketcheson's answer either as a comment to his answer or in greater detail in your post? I'm going to admit that I don't follow your argument. $\endgroup$
    – Aron Ahmadia
    Commented Aug 4, 2012 at 9:39
  • $\begingroup$ $\lambda$ is a KKT multiplier in the optimality conditions (necessary under constraint qualification, sufficient under convexity). $\endgroup$
    – Geoff Oxberry
    Commented Aug 4, 2012 at 21:28
  • 1
    $\begingroup$ @aron Well, the mistake in David's answer is that he is looking at the problem as a standard optimization problem in the variables $x$ and $y$. However, that is not what the question is about, as it is a parametric program. It asks for a value of y, such that the optimal solution $x$ to the LP, for fixed $y$, is positive. This is called a bilevel program, and can be seen as a parametric program. I think my note illustrates the crucial importance of incorporating the notion of optimality of $x$ as a function of $y$, in contrast to jointly optimizing over them. I'll see if I can do some edit. $\endgroup$
    – Johan Löfberg
    Commented Aug 6, 2012 at 19:21
  • 1
    $\begingroup$ @David Yes, the trilinearity is a consequence of the introduction of the KKT conditions. Bad news indeed, but required in order to formulate the problem correctly as we are not talking about standard optimization but parametric/bilevel optimization where $y$ and $x$ are decided in a hierarchical order. If it was possible to do this without introducing the KKT conditions, it would mean that it would be possible to get linear constraints in the case when only $b$ or $c$ is influenced by the parameter $y$, which isn't the case (NP-hard problem already then.) $\endgroup$
    – Johan Löfberg
    Commented Aug 6, 2012 at 19:53
  • $\begingroup$ @David. I think my note should describe it, but I'll descibe it in slightly different words in order to clearly separate the variables $\endgroup$
    – Johan Löfberg
    Commented Aug 7, 2012 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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