 # Linear Programming with Constraints of lower bound and upper bound

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 <= A
x <= 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

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.

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.

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.