LP/QP with not-so-constant linear constaints

Question

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.

Answer 1

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.

Answer 2

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.