4

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?

Aron Ahmadia
  • 6,951
  • 4
  • 34
  • 54
maomoa
  • 41
  • 1
  • What do you mean by "the solution of LP is positive"? Do you mean that all variables $y$ are positive? – Aron Ahmadia Aug 03 '12 at 16:39
  • 1
    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. – David Ketcheson Aug 07 '12 at 08:17

1 Answers1

5

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).

Johan Löfberg
  • 1,848
  • 10
  • 6
  • 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. – Aron Ahmadia Aug 04 '12 at 09:39
  • $\lambda$ is a KKT multiplier in the optimality conditions (necessary under constraint qualification, sufficient under convexity). – Geoff Oxberry Aug 04 '12 at 21:28
  • 1
    @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. – Johan Löfberg Aug 06 '12 at 19:21
  • 1
    @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.) – Johan Löfberg Aug 06 '12 at 19:53
  • @David. I think my note should describe it, but I'll descibe it in slightly different words in order to clearly separate the variables – Johan Löfberg Aug 07 '12 at 08:30
  • @David. timed-out...Can you give me a constant $k$ such that the solution $x$ to the optimization problem minimize $x$ subject to $x\geq k$ will yield a solution $x$ which is non-negative. Clearly, if you pick the constant $k$ non-negative, you will achieve this. Minimize $x$ subject to $x\geq 4$ will return a non-negative optimal solution, while minimize $x$ subject to $x\geq -7$ would yield a negative solution. Here we figured out a suitable value of $k$ by logic, but generally one would do it by bilevel programming. In the original question, $y$ plays a similar role as $k$. – Johan Löfberg Aug 07 '12 at 08:39
  • @David Your solution would correspond to solving an LP in the variables $x$ and $k$, minimize $x$ subject to $x\geq k, x\geq 0$. This would lead to the solution $x=0$ and $k$ any non-positive number. Clearly, that solution $k$ would not necessarily be an answer to the original question, "Can you give me a constant $k$ such that the solution $x$ to the optimization problem minimize $x$ subject to $x\geq k$ will yield a solution $x$ which is non-negative" – Johan Löfberg Aug 07 '12 at 08:43
  • @David You are absolutely correct that the original post really isn't about parametric programming. Bilevel programs, which I consider this to be, can be solved using parametric programming and there are many connections, hence the original posters confusion. I don't seem to be able to comment on the original post, so I post here. I'm new here... – Johan Löfberg Aug 07 '12 at 08:50
  • Well, the poster is initially probably not really interested in the value of $x$. He (or she) wants to select a parameter $y$ which specifies a linear program, such that the solution is guaranteed to be non-negative. Think of $y$ as the strategy in a game, and $x$ the result from using this strategy. He wants to find a strategy, such that when he plays the game (solves LP) the result is positive. Of course, here, if solving for $y$, we typically compute an $x$ too. A more interesting case would be to find the set of $y$ which guarantees a property of the LP. – Johan Löfberg Aug 07 '12 at 09:06
  • A simple counter-example to your direct bilinear (QCQP) approach: Let $b=(1,1)$ and $c=(1,1)$. Appending the bilinear constraints with positivity on $x$ leads to the solution $x=0$ and, e.g., $y_1 = y_2 = 1$. However, solving the LP with $y$ fixed to these values, will not lead to a positive solution $x$ (the problem is unbounded below). For this particular instance, I don't think there exist any solution due to the geometry induced by $A$.

    I hope I am not breaking any etiquette by down-voting your answer, since it really doesn't answer the question but is a discussion about nonconvex QCQPs.

     – Johan Löfberg Aug 07 '12 at 10:24
  • Haha, didn't have the reputation enough to downvote. – Johan Löfberg Aug 07 '12 at 10:25
  • @JohanLöfberg - Your contribution are really welcome here, you'll surely have the reputation for all of the extra features in no time :) – Aron Ahmadia Aug 07 '12 at 17:10
  • Many thanks for your patience, Johan. I understand now. I've deleted my answer. – David Ketcheson Aug 07 '12 at 19:47
  • @JohanLöfberg - One final request, can you come up with a better title for this question? Also, let me know if you have any tags to suggest. I added bilinear-programming, but I can add/create more if you think they'd be a better fit. – Aron Ahmadia Aug 07 '12 at 20:18