Specify initial condition for linprog?

Hello there,

I am using `linprog` to solve a linear program. The solution to the program are mostly zeros. Also, I have a version of the problem with zero cost, i.e., constraint satisfaction problem, again, with mostly zeros solution. It takes 7 and 16 seconds, respectively, to solve those two problems. I figured I would set the initial condition for `linprog` to zeros as it may speed up convergence. However, it appears that for new versions of MATLAB, `linprog` stopped supporting the initial condition argument. When I pass an initial condition argument following this old api, I get the following warning:

The dual-simplex algorithm uses a built-in starting point; ignoring supplied X0.

Is there a way to set the initial condition for the `linprog` solver in another way?

Kind regards, and I look forward to hearing from you soon.

Answer 1

[Walter Roberson]

https://www.mathworks.com/help/optim/ug/linprog.html#buusznx-options

Use the options to set the Algorithm to interior-point

[Ahmad Abuaish]

Thanks for the prompt response. I tried all three solver options listed below, yet I get the same warning message; "The <solver-name> algorithm uses a built-in starting point; ignoring supplied X0."

• 'dual-simplex'
• 'interior-point-legacy'
• 'interior-point'

Please let me know if there is a workaround to set the initial value for linprog.

Kind regards,

[Walter Roberson]

I just checked the code, and there is no work-around (sort of editing the code.)

[Ahmad Abuaish]

I see. Thanks for the prompt responses.

Answer 2

[Matt J]

You can try adding the inequality constraint f.'*x<=f.'*x0.

[Ahmad Abuaish]

I do not think is going to work becuase I want to start with x0=zeros(n,1), as I expect the majority of solution to be zeros. I think the defualt behavour of linprog is start from ones(n,1).

Walter has a short comment in the parentheses about changing the code. In the linprog code, x0 is omitted but I added it the the problem strcut, as shown below. It does not seem to change the behavour of the solver. I will resort to c++ for now, as I think that my LP should run faster.

Best,

problem.f = f;
problem.Aineq = A;
problem.bineq = B;
problem.Aeq = Aeq;
problem.beq = Beq;
problem.lb = lb;
problem.ub = ub;
problem.options = algoptions;
problem.solver = 'linprog';
problem.x0 = x0; % added at line 352

[Matt J]

I do not think is going to work becuase I want to start with x0=zeros(n,1)

The only reason it wouldn't work is if x0 is infeasible with respect to the other constraints.