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.  
 A: 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.
A: 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.
