Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Problems with edge case (Maros Meszaros) #74

Open
migarstka opened this issue Apr 24, 2019 · 0 comments
Open

Problems with edge case (Maros Meszaros) #74

migarstka opened this issue Apr 24, 2019 · 0 comments
Labels
bug Something isn't working help wanted Extra attention is needed

Comments

@migarstka
Copy link
Member

migarstka commented Apr 24, 2019

I came across the following problem when I tried to debug a Maros Meszaros benchmark. The following problem is HS51 from the problem set. It has the following form:

1/2 x' P x + q' x + r
s.t. l <= Ax <= u

We can solve the problem in COSMO with a Box-constraint:

using COSMO


P =[2.0 -2.0  0.0  0.0  0.0;
  -2.0   4.0  2.0  0.0  0.0;
   0.0   2.0  2.0  0.0  0.0;
   0.0   0.0  0.0  2.0  0.0;
   0.0   0.0  0.0  0.0  2.0]

q = [0.; -4; -4; -2; -2];

A = [ 1.0  3.0  0.0  0.0   0.0;
      0.0  0.0  1.0  1.0  -2.0;
      0.0  1.0  0.0  0.0  -1.0;
      1.0  0.0  0.0  0.0   0.0;
      0.0  1.0  0.0  0.0   0.0;
      0.0  0.0  1.0  0.0   0.0;
      0.0  0.0  0.0  1.0   0.0;
      0.0  0.0  0.0  0.0   1.0]

b = zeros(8)

l = [ 4.0;
  0.0;
  0.0;
 -1.0e20;
 -1.0e20;
 -1.0e20;
 -1.0e20;
 -1.0e20]

u = [4.0;
 0.0;
 0.0;
 1.0e20;
 1.0e20;
 1.0e20;
 1.0e20;
 1.0e20;]


 # solve with Box constraint l <= Ax <= u
model = COSMO.Model()
constraint = COSMO.Constraint(A, b, COSMO.Box(l, u))
assemble!(model, P, q, constraint)
result = COSMO.optimize!(model);

This yields the correct result obj_val = -6.0.

Now, lets assume we want to solve the same problem using one-sided constraints:
l <= Ax <= u <==> -Ax + u >= 0 and Ax - l >= 0


model = COSMO.Model()
constraint1 = COSMO.Constraint(-A, u, COSMO.Nonnegatives)
constraint2 = COSMO.Constraint(A, -l, COSMO.Nonnegatives)
assemble!(model, P, q, [constraint1, constraint2])
result = COSMO.optimize!(model);

The solver output:

------------------------------------------------------------------
             COSMO - A Quadratic Objective Conic Solver
                         Michael Garstka
                University of Oxford, 2017 - 2018
------------------------------------------------------------------

Problem:  x ∈ R^{5},
          constraints: A ∈ R^{16x5} (24 nnz), b ∈ R^{16},
          matrix size to factor: 21x21 (441 elem, 73 nnz)
Sets:     Nonnegatives{Float64} of dim: 16
Settings: ϵ_abs = 1.0e-04, ϵ_rel = 1.0e-04,
          ϵ_prim_inf = 1.0e-06, ϵ_dual_inf = 1.0e-04,
          ρ = 0.1, σ = 1.0e-6, α = 1.6,
          max_iter = 2500,
          scaling iter = 10 (on),
          check termination every 1 iter,
          check infeasibility every 40 iter
Setup Time: 0.46ms

Iter:	Objective:	Primal Res:	Dual Res:	Rho:
1	-8.9378e-01	1.1155e+20	4.3746e+00	1.0000e-01
2	-3.6748e-01	6.6932e+19	5.1392e+00	1.0000e-01
3	-1.5205e+00	4.0159e+19	5.0813e+00	1.0000e-01
4	-1.1850e+00	2.4095e+19	5.1194e+00	1.0000e-01
5	-1.8224e+00	1.4457e+19	5.0379e+00	1.0000e-01
6	-1.7447e+00	8.6743e+18	5.0732e+00	1.0000e-01
7	-2.1014e+00	5.2046e+18	5.0594e+00	1.0000e-01
8	-2.1504e+00	3.1228e+18	5.0766e+00	1.0000e-01
9	-2.3635e+00	1.8737e+18	5.0702e+00	1.0000e-01
10	-2.4491e+00	1.1242e+18	5.0760e+00	1.0000e-01
11	-2.5902e+00	6.7452e+17	5.0741e+00	1.0000e-01
12	-2.6777e+00	4.0471e+17	5.0770e+00	1.0000e-01
13	-2.7802e+00	2.4283e+17	5.0769e+00	1.0000e-01
14	-2.8583e+00	1.4570e+17	5.0785e+00	1.0000e-01
15	8.7145e-01	8.7417e+16	4.3610e+00	1.0000e-01
16	-3.3878e-01	5.2450e+16	8.3304e+00	1.0000e-01
17	-5.2683e+00	3.1470e+16	3.6624e+00	1.0000e-01
18	-5.0070e+00	1.8882e+16	1.6080e+00	1.0000e-01
19	-5.4227e+00	1.1329e+16	3.2440e+00	1.0000e-01
20	-5.7013e+00	6.7976e+15	1.3145e+00	1.0000e-01
21	-5.5454e+00	4.0785e+15	1.6094e+00	1.0000e-01
22	-5.7007e+00	2.4471e+15	1.4807e+00	1.0000e-01
23	-5.5601e+00	1.4683e+15	1.7154e+00	1.0000e-01
24	-5.6145e+00	8.8097e+14	1.5812e+00	1.0000e-01
25	-5.5645e+00	5.2858e+14	1.6702e+00	1.0000e-01
26	-5.5581e+00	3.1715e+14	1.5066e+00	1.0000e-01
27	-5.5191e+00	1.9029e+14	1.5663e+00	1.0000e-01
28	-5.5048e+00	1.1417e+14	1.5274e+00	1.0000e-01
29	-5.4773e+00	6.8504e+13	1.5490e+00	1.0000e-01
30	-5.4648e+00	4.1102e+13	1.5495e+00	1.0000e-01
31	-5.4466e+00	2.4661e+13	1.5535e+00	1.0000e-01
32	-5.4342e+00	1.4797e+13	1.5506e+00	1.0000e-01
33	-5.4222e+00	8.8781e+12	1.5484e+00	1.0000e-01
34	-5.4121e+00	5.3269e+12	1.5501e+00	1.0000e-01
35	-5.4033e+00	3.1961e+12	1.5493e+00	1.0000e-01
36	-5.3957e+00	1.9177e+12	1.5496e+00	1.0000e-01
37	-5.3890e+00	1.1506e+12	1.5492e+00	1.0000e-01
38	-5.3834e+00	6.9036e+11	1.5490e+00	1.0000e-01
39	-5.3783e+00	4.1422e+11	1.5489e+00	1.0000e-01
40	-5.3741e+00	2.4853e+11	1.5489e+00	1.0000e-01
41	-5.7532e+00	1.4912e+11	6.4953e-01	7.3505e-06
42	-5.8355e+00	8.9471e+10	3.8156e-01	7.3505e-06
43	-5.9076e+00	5.3683e+10	2.2797e-01	7.3505e-06
44	-5.9087e+00	3.2210e+10	1.3640e-01	7.3505e-06
45	-5.9238e+00	1.9326e+10	8.1474e-02	7.3505e-06
46	-5.9205e+00	1.1595e+10	4.8892e-02	7.3505e-06
47	-5.9246e+00	6.9573e+09	2.9152e-02	7.3505e-06
48	-5.9229e+00	4.1744e+09	1.7588e-02	7.3505e-06
49	-5.9242e+00	2.5046e+09	1.0414e-02	7.3505e-06
50	-5.9236e+00	1.5027e+09	6.3671e-03	7.3505e-06
51	-5.9240e+00	9.0164e+08	3.6916e-03	7.3505e-06
52	-5.9238e+00	5.4101e+08	2.3388e-03	7.3505e-06
53	-5.9240e+00	3.2458e+08	1.2771e-03	7.3505e-06
54	-5.9239e+00	1.9475e+08	8.9129e-04	7.3505e-06
55	-5.9240e+00	1.1685e+08	4.0917e-04	7.3505e-06

------------------------------------------------------------------
>>> Results
Status: Solved
Iterations: 55
Optimal objective: -5.924
Runtime: 0.026s (26.27ms)

which yields the wrong result. It seems like the large values in l and u which internally get set as b mess up (or at least dilute) the residual computations.
We can solve the same problem by removing the unnecessary constraint rows 4-8:


l_short = [ 4.0; 0.0; 0.0]

u_short = [4.0; 0.0; 0.0]

A_short = A[1:3, :]

model = COSMO.Model()
constraint1 = COSMO.Constraint(-A_short, u_short, COSMO.Nonnegatives)
constraint2 = COSMO.Constraint(A_short, -l_short, COSMO.Nonnegatives)
assemble!(model, P, q, [constraint1, constraint2], settings = COSMO.Settings(verbose = true, check_termination = 1))
result = COSMO.optimize!(model);

unsurprisingly, this again yields the correct result of obj_val = -6.0

@migarstka migarstka added bug Something isn't working help wanted Extra attention is needed labels Apr 24, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

1 participant