Can someone please help me with my QP problem?


(Myo Min Htwe) #1

myproblem1

eta = [0.03; 0.03; 0.03; 0.03; 0.03; 0.03; 0.03; 0.03; 0.03; 0.03; ...
            0.03; 0.03; 0.03; 0.03; 0.06; 0.06; 0.06; 0.06; 0.06; 0.06; ...
            0.06; 0.06; 0.06; 0.06; 0.06; 0.06; 0.06; 0.06; 0.3; 0.3; 0.3; ...
            0.3; 0.3; 0.3; 0.3; 0.3; 0.3; 0.3; 0.3; 0.3; 0.06; 0.06; 0.06; ...
            0.06; 0.03; 0.03; 0.03; 0.03]; 
I = eye(48);v1 = ones(48,1);v0 = zeros(48,1);m0 = zeros(48,48);delta = 0.5;
t = ones(48);
w = 1; T = delta*tril(t);
Dbar = [0.6257; 0.3301; 0.5974; 0.5713; 0.3849; 0.3559; 0.5175; 0.4597; ...
          0.5437; 0.3759; 0.7033; 0.622; 0.3774; 0.5164; 0.314852; 0.878052; ...
          0.263379; -0.082852; -0.200377; -0.421854; -0.594954; -0.571881; ...
          -0.663856; -0.769529; -0.744304; -0.668006; -0.694656; -0.539479; ...
          -0.215531; 0.025592; 0.267942; 0.092242; 0.169571; 0.207742; ...
          0.330148; 0.233; 0.473529; 1.065802; 0.9228; 1.0381; 1.0339; ...
          0.8007; 0.6873; 0.7936; 1.0575; 0.5244; 0.7084; 0.5883];
C= 10; chi = 6;               
Cmax = (chi/delta)*v1;
Cmin = (1/delta)*(C-chi)*v1;
Bmax = 0.6*C; Bmin = -0.6*C;
%% For H matrix
h = diag(eta');
H = [m0 m0;m0 -h];
%% For c matrix
c = w*delta*[eta; v0];
%% Lower Bounds
lb = -10*ones(96,1);
lb (1:48) = Bmin;
%% Upper Bounds
ub = 10*ones(96,1);
ub (1:48) = Bmax;
%% Linear Inequalities
A1 = [I m0;-I m0;T m0;-T m0];
b1 = [Bmax*v1' Bmin*v1' Cmin' Cmax']';
%% Linear Equalities
A2 = [v1' v0';I I];
b2 = [0; Dbar];
%% The objective function
cvx_begin
cvx_precision high
variable x(96,1);
dual variables y z
maximize(quad_form(x,H)+c'*x);
subject to
y: A1*x <=b1;
z: A2*x ==b2;
cvx_end

Calling SDPT3 4.0: 291 variables, 49 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 49
dim. of socp var = 98, num. of socp blk = 1
dim. of linear var = 192
dim. of free var = 1
96 linear variables from unrestricted variable.
*** convert ublk to lblk


SDPT3: Infeasible path-following algorithms


version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|6.1e+00|9.3e+00|2.5e+06| 1.619537e+04 0.000000e+00| 0:0:00| chol 1 1
1|0.998|0.927|1.3e-02|6.8e-01|1.3e+05| 7.423176e+03 -1.848562e+01| 0:0:00| chol 1 1
2|0.430|0.172|7.6e-03|5.7e-01|1.2e+05|-1.266757e+05 -4.529696e+01| 0:0:00| chol 1 1
3|0.520|0.067|3.7e-03|5.3e-01|7.3e+05|-6.651689e+06 -6.240615e+01| 0:0:00| chol 1 1
4|0.182|0.077|3.1e-03|4.9e-01|1.0e+07|-1.656263e+08 -1.886036e+02| 0:0:00| chol 1 1
5|0.041|0.052|3.0e-03|4.6e-01|1.2e+08|-2.188198e+09 -1.450873e+03| 0:0:00| chol 1 2
6|0.043|0.048|2.9e-03|4.4e-01|2.0e+09|-3.575164e+10 -1.316936e+04| 0:0:00| chol 1 2
7|0.018|0.047|2.8e-03|4.2e-01|1.5e+10|-2.672094e+11 -2.178849e+05| 0:0:00| chol 1 2
8|0.073|0.047|2.7e-03|4.0e-01|4.1e+11|-7.322074e+12 -1.542518e+06| 0:0:00| chol 2 2
9|0.008|0.047|2.7e-03|3.8e-01|1.6e+12|-2.816550e+13 -4.967044e+07| 0:0:00| chol 2 2
10|0.354|0.047|8.6e-03|3.7e-01|2.0e+14|-3.648722e+15 -1.785701e+08| 0:0:00| chol 2 2
11|0.002|0.047|2.2e-02|3.5e-01|3.1e+14|-5.667451e+15 -4.022820e+10| 0:0:00| chol 2 2
stop: primal infeas has deteriorated too much, 3.2e+00
12|1.000|0.047|2.2e-02|3.5e-01|3.1e+14|-5.667451e+15 -4.022820e+10| 0:0:00|
prim_inf,dual_inf,relgap = 2.17e-02, 3.49e-01, 5.54e-02
sqlp stop: dual problem is suspected of being infeasible

number of iterations = 12
residual of dual infeasibility
certificate X = 1.00e-16
reldist to infeas. <= 1.47e-16
Total CPU time (secs) = 0.20
CPU time per iteration = 0.02
termination code = 2
DIMACS: 2.8e-02 0.0e+00 1.1e+00 0.0e+00 -1.0e+00 5.5e-02


Status: Infeasible
Optimal value (cvx_optval): -Inf

echo off


How to add a slack variable in a optimal problem?
(Mark L. Stone) #2

As the message says, the problem is infeasible.

If only A1*x <=b1 is removed, the problem is feasible. If only A2*x ==b2 is removed, the problem is infeasible.

To further diagnose, you can introduce and minimize a slack variable vector slack.

cvx_begin
variable x(96,1);
variable slack(192,1) nonnegative
minimize(norm(slack))
A1*x -slack <=b1
A2*x ==b2
cvx_end

which produces optimal objective (measure of infeasibility) of +41.5692
>> disp(slack’)
Columns 1 through 18

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 19 through 36

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 37 through 54

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000

  Columns 55 through 72

    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000

  Columns 73 through 90

    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000

  Columns 91 through 108

    6.0000    6.0000    6.0000    6.0000    6.0000    6.0000    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 109 through 126

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 127 through 144

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 145 through 162

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 163 through 180

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

  Columns 181 through 192

    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002    0.0002

Id the equality constraint is removed,
i.e.,

    cvx_begin
    variable x(96,1);
    variable slack(192,1) nonnegative
    minimize(norm(slack))
    A1*x -slack <=b1
    cvx_end

the optimal objective value (measure of infeasibility) is +38.5499

>> disp(slack')
  Columns 1 through 18

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 19 through 36

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 37 through 54

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150

  Columns 55 through 72

    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150

  Columns 73 through 90

    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150    5.6150

  Columns 91 through 108

    5.5720    5.4220    5.1275    4.6148    3.7559    2.3360    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 109 through 126

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 127 through 144

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0860    0.3000    0.5890    1.0253    1.7179    2.8399    4.6719

  Columns 145 through 162

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 163 through 180

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

  Columns 181 through 192

    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003    0.0003

(Myo Min Htwe) #3

Thank you so much for your kind support. I am trying to flatten the ‘Dbar’ which will result as x (49:96) . Is there a way to get expected answer if we can modify H matrix?


(Mark L. Stone) #4

There is no change to Dbar which will make the problem feasible, because it is only used in b2, whose only appearance in the optimization problem is in the constraint A2*x ==b2 . As I wrote in my previous answer, even if that constraint were removed, the problem would still be infeasible.

Unless you change or remove the constraint A1*x <= b1, the problem will be infeasible.


(Myo Min Htwe) #5

My target of solving QP problem is to get resultant answer ‘x’. More specifically, in the resultant answer ‘x’ what I’m expecting to get is flattened ‘Dbar’ which will get as x(49:96).

For my problem, ‘H’ matrix is also adjustable. Do you think adjusting ‘H’ matrix can help me getting feasible answer?

According to your explanation, I can get feasible solution if I adjust inequalities constraint. How can I use ‘slack minimization’ to find ‘inequalities constraint’ which can be feasible for my problem?


(Mark L. Stone) #6

In my first post of the thread, I showed you how to use slacks to find a feasible solution wither with or without the A2*x ==b2 constraint.

if you want to, you can keep your original objective and the slack, place an upper bound on the slack (you will know how tight the bound can be and still preserve feasibility based on first solving the version in which some metric (such two-norm, or a different norm) is minimized).