Need a symbolic solution to least-squares optimization problem

Question

What's the symbolic solution to this problem?

Minimize $\left(x-x_T\right){}^2+\left(y-y_T\right){}^2+\left(z-z_T\right){}^2$

for variables $x,y$ and $z\in \mathbb{R}$, given parameters $x_T, y_T, z_T, x_L, y_L$ and $z_L \in \mathbb{R}$.

where $0\leq x\leq x_L, 0\leq y\leq y_L, 0\leq z\leq z_L$

and

$x+y+z=1$

You may also assume that

$0\leq x_T\leq 1, 0\leq y_T\leq 1, 0\leq z_T\leq 1$

if that helps.

Thanks.

Answer 1

This is a so called multi-parametric quadratic program. Theory tells us that the solution will be a piecewise affine function w.r.t the three parameters, with a polyhedral partition (i.e, the feasible set can be partitioned into a finite set of polyhedrons, and in each polyhedron, the optimal solution is affine.

There are tools to compute the solutions. In MATLAB, there is a toolbox called MPT (multiparametric toolbox). I use it below, interfaced via YALMIP (disclaimer: developed by me) to compute the solution to your particular problem (the solution is a partition with 16 regions, and I think if you look at the solution, it would be straightforward in hindsight to understand the possible optimal solutions)

sdpvar x y z
sdpvar xT yT zT xL yL zL

Model = [x + y + z == 1,0 <=[x y z] <= [xL yL zL],0 <=[xL yL zL xT yT zT] <= 1]
Objective = (x-xT)^2 + (y-yT)^2 + (z-zT)^2;

solution = solvemp(Model,Objective,[],[xT yT zT xL yL zL])