How do I solve a linear optimization problem with a constrained output?

0

I am trying to solve the following optimization problem in Matlab: MPC problem

k is the time with N being the amount of timesteps.

linprog(c_k,F_uk,f_k) solves elements 7.1a and 7.1e of the above problem description. However, the output of the model/problem, x, needs to be constrained within bounds. In the image, x is first converted to y and then y is constrained, but directly constraining x would also work.

For context, u is the (decision variable) input to various radiators in a building and x the resulting temperatures of rooms and wall, which need to be constrained between eg 20 and 25 degrees. v are external factors such as outside temperature.

Is there a way to incorporate the constraint on x in the linprog function? Or should I use another optimization method altogether?

What I tried: what linprog solves

I've thought a lot about how to rewrite x/u and/or how to use one of the three constraint methods as seen in the image to constrain x. Note that vector u in my problem description is the x to be solved in matlab, while x in my problem is a different variable.

I've thought about adding the states x to the decision variable u, but the problem is also that x depends on x in the previous timestep. u is currently a long vector with input variables for each timestep.

Perhaps I should use a heuristic algorithm, but a low computation time is important for my research.

Answer 1

[Torsten]

Define the X to be solved for as X = (u,x).Then you can constrain x according to your needs and continue using "linprog".

Answer 2

[John D'Errico]

Seems easy enough. For example, suppose you have a linear programming problem where you solve it to minimize over x.

But you also have some other constraint that applies to the result x.

Just add it to the original problem. Solve the expanded problem, where you now have one more constraint.

For example, here is a simple problem.

Maximize x1 + x2

x1 >= 0, x2 >= 0

x1 + x2 <= 3

2*x1 + x2 <= 5

x1 + 3*x2 <= 6

I'll set up the solution using an optimproblem. It make things easy to read.

prob = optimproblem('Description','Unbounded 2-d example');
x = optimvar('x',[1,2],'lower',0);
prob.ObjectiveSense = 'maximize';
prob.Objective = x(1) + x(2);
prob.Constraints.Con1 = x(1) + x(2) <= 3;
prob.Constraints.Con2 = 2*x(1) + x(2) <= 5;
prob.Constraints.Con3 = x(1) + 3*x(2) <= 6;
xsol = solve(prob)

Solving problem using linprog.

Optimal solution found.

xsol = struct with fields:
    x: [2 1.0000]

Now I'll plot the constraints, as well as the solution.

plot2dHalfPlane([-1 -1],-3,[0,6],[0,6])
plot2dHalfPlane([-2 -1],-5,[],[],gcf)
plot2dHalfPlane([-1 -3],-6,[],[],gcf)
hold on
plot(xsol.x(1),xsol.x(2),'rx')

As expected, the solution lies at a vertex of the polytope defined by the constraints.

But now you tell us there is an additional constraint on the solution? This is not a problem, as long as that additional constraint can be formulated in a linear way. If it cannot, then you cannot solve the problem using a basic linear programming tool. You may need to use other tools like FMINCON, INTLINPROG, or even GA.

So suppose now you tell me the solution has yet another constraint on the result? Just add it to the proiginal problem formulation.

prob.Constraints.Con4 = 2*x(1) + 7*x(2) <= 8;
xsol = solve(prob)

Solving problem using linprog.

Optimal solution found.

xsol = struct with fields:
    x: [2.2500 0.5000]

The new solution is now inside the first convex polytope, again as expected.

[Anne Aarts]

Thanks for the help! I've added x as an optimization variable now.