Solve variation with tomlab LCP

[jlperla]

Once #5, #6, and #7 are complete, we can swap out the LCP function used in the baseline example for a high-performance commerical version. This is unlikely to help with this exact scenario since it is too simple, but may be necessary for larger problems with many more dimensions.

With tomab, see https://tomopt.com/docs/quickguide/quickguide027.php as a starting point. Knitro is likely to be the best solution. It is essential that you verify it is setup (and solving) as a sparse problem. May require flipping through documents to look for possible settings that ensure sparseness, and setting sparseness patterns directly (or indirectly)?

Worst case, any quadratic solver with linear constraints can do LCP, since there is a mapping of the LCP to the KKT conditions of a quadratic problem. See https://en.wikipedia.org/wiki/Linear_complementarity_problem#Convex_quadratic-minimization:_Minimum_conditions for an example of the mapping.

[jlperla]

The simple_optimal_stopping_diffusion.m file now has a placeholder for a knitro method. This is where the code should go. Once the code is complete for that method, the test suite of #14 should be repeated, but just changing the knitro setting. The previously saved files should be directly comparable within some precision.

For implementing knitro, see the https://tomopt.com/docs/TOMLAB_QUICKGUIDE.pdf LCP section.

[stevenzhangdx]

I read through the notes about solving LCP and QCP by using tomlab. It seems that our example cannot be directly solved as a LCP , because it requires a known c for questions in the form of $min_{x}$ $c^{T}x$ (c in our case is $Bz + q$, which is a variable). Then I tried it by using QCP method, but one test passed and the two encountered errors. I think the reason is that QCP problem requires a symmetric B. However, B is not symmetric when $ mu$ is non-zero. Please take a look at simple_optimal_stopping_diffusion.m and I am not sure if I am using the correct solving method. If you want we can discuss about it. I will be available today after 2PM.

[jlperla]

If this helps, for the objective function you can just set $c^T$ to be 0 (or leave it out entirely) and I think it just looks for feasible solutions rather than trying to minimize anything.

The QCP is a bigger issue, and I now think think it will work in this setup.

[jlperla]

I think you need to throw out the QP formulation, since you are right it will only work if $\mu = 0$. I am investigating if there are other approaches using QP, but I don't think they are appropriate. For the linear complementarity problem, take a look at: https://tomopt.com/docs/quickguide/quickguide027.php

I think to solve the LCP in tomlab, we need the following:

• Try to set c=[] to see if it ignores the objective, or c=0 otherwise.
• Based on what I can tell, you will need to introduce slack variables to the problem, maybe let $m \equiv Bz+q$. Slack variables are created with equality constraints, from what I understand, but you can verify.
• Then I think you need to pass in complementarity conditions as $m_i \perp z_i$ for all $i$... or something like that So, in tomlab notation, I think it is all about finding the A, b_L, and b_H to enforce the slack variables, and then the mpec to enforce the complementarity between the slack variables and the main variables.

That may be it? If so, then it is all about setting up the correct constraint matrices, etc. After you figure out if this is the right general approach, why don't you specify the algebra in optimal_stopping.tex so we can verify it?

[stevenzhangdx]

I just finished the tomlab version LCP solver and all tests pass. Since c has to be given, it works after setting c = zeros(I, 1).

[jlperla]

Great,. But I don't see the test of the knitro. Did you forget to commit code that checks if it works? If so, please add whatever you need to the test script, and verify that it gives the same solution as yuval in a couple of the simple cases. Also, if you look at #14 you will see that there are a couple more test cases that we should add in at the bottom.

[stevenzhangdx]

The test of Knitro in LCP_methods_test has been added. I notice that you made a few changes to the suite test. One big change is there is no default setting of solver. Without default setting, it will be solved by Yuval or none of them.

[jlperla]

Great. Are you sure you have it pushed to the server? I only see the lemke and yuval tests right now. Is there a chance you had a conflict you need to manually merge, for example?

Right now, the solution defaults to yuval if the methods hasn't been set on the settings.

[stevenzhangdx]

I uploaded the test case again. Now it is supposed to appear.

Also, I tried a couple of simple cases (u_x_is_negative_for_small_x_test and negative_S_x_test). Solutions do not exactly match. I manually saved values solved by knitro method and matched with ones from yuval method. Actually, they are very close. Please take a look at it.

[jlperla]

It looks great. I played around with it and reorganized the code a bit. This task is completely done, so move onto the #14 when you have time to work next, and then we will discuss the next steps.

[stevenzhangdx]

Sure, I will complete #14 as soon as I can.