Minimize distance of LP solution to a given vector

Question

I am solving for a regular LP problem

$max$ $c^T.v_1$

$s.t.$

$A.v_1=b$

$lb<v_1<ub$

let $v_2$ a given known vector of the same size than $v_1$.

I would like to obtain the $v_1$ solution vector such that the distance to $v_2$ is minimal i.e. $|v_1-v_2|$ is minimal.

I am wondering how can I formulate the problem and implement it in Matlab.

Thanks a lot for the help.

Answer 1

This algorithm should do what you want.

Step 1

Solve $$\begin{align} \min \> & z_1 = \sum_i (d_i^+ + d_i^-)\\ &d^+ - d^- = v_1 - v_2\\ &Av_1=b\\ &\ell \le v_1 \le u\\ &d^+, d^- \ge 0 \end{align}$$ and record the optimal objective value $z^*_1$.

Step 2

Solve

$$\begin{align} \max\> & z_2 = c^Tv_1 \\ & z^*_1 = \sum_i (d_i^+ + d_i^-)\\ &d^+ - d^- = v_1 - v_2\\ &Av_1=b\\ &\ell \le v_1 \le u\\ &d^+, d^- \ge 0 \end{align}$$

Notes:

• $d^+,d^-$ are vectors of non-negative variables (same size as $v_1,v_2$).
• LPs cannot handle $<$, $>$ inequalities. They have to be $\le$,$\ge$.