Re: [ojAlgo-user] Probably User Error, but...
Mathematics, linear algebra and optimisation
Brought to you by:
apete
Menu
▾
▴
Re: [ojAlgo-user] Probably User Error, but...
|
From: Anders P. <an...@op...> - 2015-08-09 20:49:58
|
There was a bug that could give you a NullPointerException if you turned on debug logging and there were no equality constraints. That’s fixed.
Both cases where you had an identity Q-matrix works as expected (if you didn’t get that NullPointer).
The unconstrained case with a zero Q-matrix returns state INVALID rather than the perhaps more correct UNBOUNDED - is that a big problem for you?
The constrained zero Q-matrix case returned a strange solution and incorrectly reported it as OPTIMAL (The returned solution was feasible but not optimal.) I’ve modified the solver so that it returns the optimal solution (in your test case at least).
Generally you should not solve linear problems using the ConvexSolver!
/Anders
> On 9 aug 2015, at 11:34, Anders Peterson <an...@op...> wrote:
>
> The short answer and quick solution for you is to model your problems using ExpressionsBasedModel rather than using the ConvexSolver directly. It brings many advantages - among other things it would automagically switch to the LinearSolver for that one degenerate case.
>
>
> The ConvexSolver assumes there is a Q-matrix and that it is symmetric and (semi) positive definite. A Q-matrix with all zeros does theoretically meet those requirements, and It seems reasonable to assume that a convex solver can handle a linear problem. That said I’m not surprised it fails - it’s not designed to handle that case. I will, however, have a look your test code and investigate what (if anything) I can do handle the linear case.
>
>
> /Anders
>
>
>
>> On 9 aug 2015, at 02:40, Greg Sterijevski <gs...@ho...> wrote:
>>
>> Hi,
>>
>> I have a very simple quadratic programming problem. In one degenerate case, the Q matrix is composed of zeroes. In other words, the problem is a linear programming problem with Equality and Inequality constraints. It seems like ConvexSolver should be able to solve the problem but it fails in somewhat interesting ways. I am not sure what I am doing wrong.
>>
>> I am minimizing the expression
>>
>> x' Q x' - c' x
>>
>> where c = { 0.12, -0.05, 0.08, 0.07 }
>>
>> I would expect that without an constraints, the solver should fail as it attempts to take x[0],x[2],x[3] to +infinity and x[1] to -infinity. I next set liberal constraints of +/- 99999 for all the factors.. I would expect the solver to take the x vector to the bounds and terminate gracefully. In either case, the results are hard to understand.
>>
>> In the case where I use the zero matrix for Q, I get an infeasibility failure. Failure State = INVALID
>>
>>
>> In the case where I use an identity matrix (which is PSD and nice) , I get the result as:
>> x[0] = 0.12
>> x[1] = -0.05
>> x[2] = 0.08
>> x[3] = 0.07
>>
>> In the case of zero matrix and constraints I get:
>>
>> x[0] = 0.25
>> x[1] = 0.25
>> x[2] = 0.25
>> x[3] = 0.25
>>
>> The for the case of an identity matrix and constraints I get
>>
>> Identity Q matrix and constraints -------------------------!
>> Initial solution: [0.12, -0.05, 0.08, 0.07]
>> Initial I-included-slack: []
>> Initial I-excluded-slack: [99999.12, 99998.95, 99999.08, 99999.07, 99998.88, 99999.05, 99998.92, 99998.93]
>>
>> PerformIteration
>> Last Incl/Excl: -1/-1 => [] / [0, 1, 2, 3, 4, 5, 6, 7]
>> X/L: true X=[0.0, 0.0, 0..0, 0.0] L=[]
>> Current: [0.12, -0.05, 0.08, 0.07]
>> Step: [0.0, 0.0, 0.0, 0.0]
>> java.lang.NullPointerException
>>
>>
>> Any thoughts would be appreciated. Thank you to the creators of OjAlgo. It looks like a complete package!
>>
>>
>> -Greg
>>
>>
>> Test code below.
>>
>> public static void attempt5(boolean identity, boolean addDummyConstraints) {
>> if (!identity && !addDummyConstraints) {
>> System.out.println("Zero Q matrix and no constraints -------------------------!");
>> } else if (!identity) {
>> System.out.println("Zero Q matrix and constraints -------------------------!");
>> } else if (!addDummyConstraints) {
>> System.out.println("Identity Q matrix and no constraints -------------------------!");
>> } else {
>> System.out.println("Identity Q matrix and constraints -------------------------!");
>> }
>>
>> double[] C = new double[]{0.12, -0.05, 0.08, 0.07};
>> final RawStore cov = new RawStore(4, 4);
>> if (identity) {
>> for (int i = 0; i < 4; i++) {
>> cov.set(i, i, 1.0);
>> }
>> }
>> final RawStore linPart = new RawStore(C, 4);
>> ConvexSolver.Builder builder = ConvexSolver.getBuilder(
>> cov,
>> linPart);
>>
>> if (addDummyConstraints) {
>> RawStore ineq = RawStore.FACTORY.rows(
>> new double[][]{{-1.0, 0.0, 0.0, 0.0}, {0.0, -1.0, 0.0, 0.0}, {0.0, 0.0, -1.0, 0.0}, {0.0, 0.0, 0.0, -1.0},
>> {1.0, 0.0, 0.0, 0.0}, {0.0, 1.0, 0.0, 0.0}, {0.0, 0.0, 1.0, 0.0}, {0.0, 0.0, 0.0, 1.0}});
>>
>> RawStore coeff = RawStore.FACTORY.columns(new double[][]{{99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999}});
>>
>> builder = builder.inequalities(ineq, coeff);
>> }
>> final Optimisation.Options opts = new Optimisation.Options();
>> opts.iterations_abort = 10000;
>> opts.iterations_suffice = 100;
>> opts.debug(ConvexSolver.class);
>> final ConvexSolver cs = builder.build(opts);
>>
>> try {
>> final Optimisation.Result solution = cs.solve();
>> if (solution.getState() == Optimisation.State.DISTINCT
>> || solution.getState() == Optimisation.State.APPROXIMATE
>> || solution.getState() == Optimisation.State.OPTIMAL) {
>> double[] pt = new double[4];
>> for (int i = 0; i < pt.length; i++) {
>> pt[i] = solution.doubleValue(i);
>> }
>>
>> System.out.println("Objective " + solution.getValue());
>> for (int ii = 0; ii < 4; ii++) {
>> System.out.println("x[" + ii + "] = " + solution.doubleValue(ii));
>> }
>> } else {
>> System.out.println("Failure State = " + solution.getState().name());
>>
>> }
>>
>> } catch (Exception e) {
>> System..out.println(e);
>> }
>> }
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> ojAlgo-user mailing list
>> ojA...@li...
>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user
>
>
|
