Description

 

Convex Optimization

 

Ref.	Exercises
[1]	3.32, 3.33, 4.11, 4.17, 4.23, 4.26(a), 4.30

Matlab Assignment

Problem 1. Consider the problem of traveling from the point (x₀,y₀) = (0,4) to the point (x₆,y₆) = (24,4) by going through 5 parallel gates located at fixed positions (x_i,y_i) with width c_i reported in the following Table.

• Use optimization modeling to find the path which minimizes the total length of the path.
• Use the function “quadprog” in Matlab to solve the problem with the data provided in the following Table.

Problem 2. (Extra point) In radiation treatment, radiation is delivered to a patient, with the goal of killing or damaging the cells in a tumor, while carrying out minimal damage to other tissue. The radiation is delivered in beams, each of which has a known pattern; the level of each beam can be adjusted. (In most cases multiple beams are delivered at the same time, in one shot, with the treatment organized as a sequence of shots.) We let b_j denote the level of beam j, for j = 1,…,n. These must satisfy 0 ≤ b_j ≤ B^max,

where B_max is the maximum possible beam level. The exposure area is divided into m voxels, labeled i = 1,…,m. The dose d_i delivered to voxel i is linear in the beam levels, i.e.,  where

(known) matrix that characterizes the beam patterns. We now describe a simple radiation

treatment planning problem.

A (known) subset of the voxels, τ ⊂{1,…,m}, corresponds to the tumor or target region. We require that a minimum radiation dose D^target be administered to each tumor voxel, i.e., d_i ≥ D^target for i ∈ τ . For all other voxels, we would like to have d_i ≤ D^other, where D^other is a desired maximum dose for non-target voxels. This is generally not feasible, so instead we settle for minimizing the penalty,

 .

where ()₊ denotes the nonnegative part of its argument (i.e., (z)₊ = max{0,z}). We can interpret E as the total nontarget excess dose.

• Show that the treatment planning problem is a linear program. The optimization variable is b ∈Rⁿ ; the problem data are B^max,A,T,D^target, and D^other
• Solve the problem instance with data generated by the file treatment-planning-data.m using the matlab function “linprog”. Here we have split the matrix A into Atarget, which contains the rows corresponding to the target voxels, and Aother, which contains the rows corresponding to other voxels. Plot the dose histogram for the target voxels, and also for the other voxels in Matlab (You can use the Matlab function “hist” to plot histograms.) Make a brief comment on what you see. Remark: The beam pattern matrix in this problem instance is randomly generated, but similar results would be obtained with realistic data.