Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

2 Answers 2

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.

share|improve this answer
    
+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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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