# LP/QP with not-so-constant linear constaints

I have an otherwise standard LP or PSD QP problem as below:

$\min\limits_x {c}' x$ subject to $Ax\leq b$ or $\min\limits_x \frac{1}{2}{x}' Qx + {c}' x$ subject to $Ax\leq b$

the only exception is that the coefficients, $[a_{i,j}]$, in $A$ are not so constant – they can be changed slightly via other less convenient means (not through x).

My questions: (1) How to effectively find out which $[a_{i,j}]$’s are more impactive for further reducing the objective function? (There will be some cost to investigate if any specific $a_{i,j}$ can be modified.)

(2) Once I know which $a_{i,j}$'s are easily changeable and by how much, how to append some selected $a_{i,j}$'s into the decision variables without having to deal with the quadratic (possibly non-convex) constraints (Online solution time is important to me). Is there any iterative LP/QP scheme that can solve the new optimization problem? Sub-optimal solution (wrt $a_{i,j}$) is acceptable.

-
I cannot parse this. What do you mean that the coefficients are changeable? What do you mean by "not through $\mathbf{x}?$ –  Igor Rivin Aug 3 '12 at 3:34
I think what you want to look at is sensitivity analysis with respect to changes in the $A$ matrix. –  Robert Israel Aug 3 '12 at 8:34
Igor: The coefficients in A represent the underlying physical equipment/processes, some of which can be set up and/or operated differently (e.g., operating them in different modes) – not always easy to change but changeable nonetheless. I need to find out which part of A is worthwhile to change. –  JJL Aug 3 '12 at 13:23
Robert: Yes, my first question is about sensitivity analysis with respect to changes in A matrix. Is there any standard method for an LP or a QP problem? –  JJL Aug 3 '12 at 13:30

You may want to consult the oevre of Spielman and Teng (I think all their papers are on ArXiv). They study this sort of question in great depth.

-
+1 for using Old French :) –  quid Aug 3 '12 at 17:32
I am new to ArXiv, and I did not find a good reference there by them. Can you/anyone please provide a pointer (such as keywords in the title)? –  JJL Aug 3 '12 at 23:06

Consider a problem $\min_x f(x)$ subject to $A x \le b$, for which you have an optimal solution $x^\star$ with Lagrange multipliers $\lambda^\star$ satisfying the Karush-Kuhn-Tucker conditions \eqalign{\nabla f(x^\star) &+ \lambda^\star A = 0\cr \lambda_i^* (A x^\star - b)_i &= 0 \ \text{for each}\ i \cr \lambda^\star \ge 0\cr A x^\star \le b\cr}

I'll suppose this is a non-degenerate case where for each $i$, only one of $\lambda_i^\star$ and $(A x^\star - b)_i$ is $0$, and the submatrix $A_B$ of $A$ consisting of those rows for which $\lambda^\star_i \ne 0$ is invertible, so that the nonzero elements of $\lambda^\star$ are given by $\lambda_B^\star = - (\nabla f(x^\star)) A_B^{-1}$, while $x^\star$ is determined by $x^\star = A_B^{-1} b_B$.

Consider changing one entry $a_{rs}$ of $A$ by a very small amount.
If $(A x^\star - b)_r \ne 0$, i.e. the change is in a constraint that has some slack, so $\lambda^\star_r = 0$, then as long as $(A x^\star - b)_r$ stays nonnegative neither $x^\star$ nor $\lambda^\star$ will change.

On the other hand, suppose $(A x^\star - b)_r = 0$. Then both $\lambda_B^\star$ and $x^\star$ will change in general. Note that $$\frac{\partial}{\partial a_{rs}} A_B^{-1} = - A_B^{-1} E_{rs} A_B^{-1}$$ where $E_{rs}$ is the matrix with entry $1$ in the $(r,s)$ position and $0$ elsewhere. So $\dfrac{\partial}{\partial a_{rs}} x^\star = - A_B^{-1} E_{rs} A_B^{-1} b_B = - A_B^{-1} E_{rs} x^*$, i.e. $\dfrac{\partial}{\partial a_{rs}} x^\star_i = (A_B^{-1})_{ir} x_s^\star$. Similarly you can calculate the rate of change of $\lambda^\star$. This will remain valid as long as $A x^\star \le b$ and $\lambda^\star \ge 0$ and $A_B$ is invertible.

-
Thanks Robert for your answer. I found a paper by Robert Freund, which works for equality constraints but has a similar idea. [See dspace.mit.edu/bitstream/handle/1721.1/2072/… I have a question: for QP (and degenerate LP), $A_B$ can be nonsquare thus $A_B^{-1}$ may not exist. How do we handle that? –  JJL Aug 3 '12 at 23:29