Linear Programming with Constraints of lower bound and upper bound

1

Hi,

I’m working on a project related to radiotherapy treatment planning.
The mathematical expression is as following
d=Ax
Where
d is an m\times1 dose distribution vector of each voxel,
x is the n\times1\ fluence weighting vector on each radiation beamlet,
A is the precalculated m\times n dose-fluence deposition matrix

The objective can be any function of x. In our case, the objective function is to minimize the norm to the target dose
\mathrm{argmin\ }\left|\left|Ax-d_p\right|\right|
Where d_p is the prescribe dose
Subject to the following constraints:
LBdose \le Ax \le UBdose
LBdose,UBdose,d,\ x \geq0
Where LBdose and UBdose are the lower bound and upper bound of the dose d

I tried to script it in CVX, but the model will say that it is not feasible.
for example:
n=number of beammlets;
Dp=60;
LBdose=59;
UBdose=66;
cvx_begin
variable x(n);
minimize( norm(Ax-Dp) );
subject to
LBdose <= Ax <= UBdose;
x>=0;
cvx_end

the message showed on MATLAB:

Barrier solved model in 0 iterations and 161.13 seconds
Model is infeasible

Status: Infeasible
Optimal value (cvx_optval): +Inf

Thank you.

JackieC

2

Infeasible means there is no solution (value of x) which simultaneously satisfies all the constraints.

Everything in https://yalmip.github.io/debugginginfeasible except section 1 also applies to diagnosing infeasibility in CVX.

Given the input data you show, your program (problem) could be feasible or infeasible, depending on A, which you haven’t shown.

3

Thank you so much!

A is a sparse matrix with all elements are nonnegative.

I’ve tried to import the zeros vector as the LBdose, and that will work. However, as long as I import the vector contains positive integers, it will tell me infeasible, which is confusing to me.

4

For illustration, let’s say m = 2, n = 1, and A is the 2 by 1 matrix [1;2]. There is no x >= 0 for which 59 <= x <= 66 and 59 <= 2*x <= 66; Hence this simple model, for which all elements of A are nonnegative, is infeasible. So certainly a more complicated model having all elements of A nonnegative, could be infeasible, even though the “reason(s)” for the infeasibility might be more subtle than in my simple example.

I suggest you follow the advice in the link.