Originally posted by: Riana

Dear All,

My optimizing problem is (in Matlab format):

minimize y

y = norm(Ax-b,Inf)+w*mean(abs(x-k))

where:
y is a value
A is a known matrix with size m*n
x is an unknown vector with size n*1
b is a known vector with size m*1
w is a variable weight coefficient
k is a known vector with size n*1

This optimization question plans to minimize the norm(Ax-b, Inf),while at the same time hoping to make the elements of x as close to the preset k as possible.

I would love to ask for some advices on how to model this whole problem into a LP.

Most appreciation.
Riana
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hints:

(1) Minimizing u + v often can be accomplished by minimizing something no smaller than u plus something no smaller than v.
(2) If x_i - k_i <= q_i AND k_i - x_i <= q_i, then |x_i - k_i| <= q_i.
(3) If z_i - b_i <= u for all i AND b_i - z_i <= u for all i, then the sup-norm of z - b is <= u.

Also note that if, in your notation, x and w are both variable, then your objective function cannot be linearized; it will at best be quadratic (if you make appropriate use of the hints above). So you may get a QP, but not an LP.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If you use MATLAB+CPLEX, you might be interested to now that the modelling language YALMIP (interfacing, e.g., CPLEX in MATLAB) takes care of this problem immediately for you (i.e., models the norm and abs operators)

x = sdpvar(n,1);
y = norm(Ax-b,Inf)+w*mean(abs(x-k))
solvesdp([],y)

(As Paul said, assuming w constant, the LP model YALMIP derives for you is something like
u = sdpvar(1)
v = sdpvar(n,1)
y = u+w*sum(v)
constraints = -u <= A*x-b<= u, -v <= x-k <= v
#CPLEXOptimizers
#DecisionOptimization