Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Quadprog converges to suboptimal point?

Subject: Quadprog converges to suboptimal point?

From: sally

Date: 11 Jul, 2012 20:50:22

Message: 1 of 5

Hi,

I am comparing results from quadprog using the interior-point-convex algorithm to results from another optimizer.

Both solutions are feasible, but the quadprog solution's fval is suboptimal.

I am wondering if this is due to tolerance settings. I am currently just using the default quadprog options.

Output messages pasted below.
____________________________________________________________
The interior-point-convex algorithm does not accept an initial point.
Ignoring X0.
Solved 0 variables, 0 equality, and 121 inequality constraints during the presolve.
                                    First-order Total relative
 Iter f(x) Feasibility optimality error
    0 -2.752162e-003 1.058e+001 1.222e-001 3.234e+001
    1 -1.875931e-003 5.296e-014 2.378e-005 2.088e+001
    2 -2.066126e-003 1.443e-015 3.898e-007 3.354e-001
    3 -2.545616e-003 1.332e-015 3.695e-007 3.308e-001
    4 -7.100663e-003 5.551e-016 6.674e-008 8.913e-002
    5 -1.113042e-002 8.882e-016 8.139e-009 1.331e-002

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the default value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint tolerance.

Optimization completed: The relative dual feasibility, 1.734723e-017,
is less than options.TolFun = 1.000000e-008, the complementarity measure,
8.138838e-009, is less than options.TolFun, and the relative maximum constraint
violation, 8.881784e-016, is less than options.TolCon = 1.000000e-008.

Optimization Metric Options
relative dual feasibility = 1.73e-017 TolFun = 1e-008 (default)
complementarity measure = 8.14e-009 TolFun = 1e-008 (default)
relative max(constraint violation) = 8.88e-016 TolCon = 1e-008 (selected)

____________________________________________________________
Any insights or hints would be greatly appreciated.

Thanks,

Sally

Subject: Quadprog converges to suboptimal point?

From: Matt J

Date: 11 Jul, 2012 22:06:10

Message: 2 of 5

"sally" wrote in message <jtkoue$a9b$1@newscl01ah.mathworks.com>...
> Hi,
>
> I am comparing results from quadprog using the interior-point-convex algorithm to results from another optimizer.
>
> Both solutions are feasible, but the quadprog solution's fval is suboptimal.
>
> I am wondering if this is due to tolerance settings. I am currently just using the default quadprog options.
>
> Output messages pasted below.
> ____________________________________________________________
> The interior-point-convex algorithm does not accept an initial point.
> Ignoring X0.
> Solved 0 variables, 0 equality, and 121 inequality constraints during the presolve.
> First-order Total relative
> Iter f(x) Feasibility optimality error
> 0 -2.752162e-003 1.058e+001 1.222e-001 3.234e+001
> 1 -1.875931e-003 5.296e-014 2.378e-005 2.088e+001
> 2 -2.066126e-003 1.443e-015 3.898e-007 3.354e-001
> 3 -2.545616e-003 1.332e-015 3.695e-007 3.308e-001
> 4 -7.100663e-003 5.551e-016 6.674e-008 8.913e-002
> 5 -1.113042e-002 8.882e-016 8.139e-009 1.331e-002
>
> Minimum found that satisfies the constraints.
=============


What evidence are you showing us here that the optimization failed? Why shouldn't we believe the output message that you're getting?

Subject: Quadprog converges to suboptimal point?

From: sally

Date: 12 Jul, 2012 13:42:23

Message: 3 of 5

"Matt J" wrote in message <jtktci$qn5$1@newscl01ah.mathworks.com>...

> What evidence are you showing us here that the optimization failed? Why shouldn't we believe the output message that you're getting?

Hi Matt,

Here you go. x_star contains the solution from another optimizer which gives me a minimum of -.0143 which is less than x's -.0111. Both solutions do not violate any constraints.

The interior-point-convex method does not take an x0, but the trust-region-reflective with starting point x0 = x_star does converge to x_star. So I don't think I formulated the constraints wrong.

I am not saying the optimization "failed", just hoping someone can point me in the right direction to help figure out what is going on.

Thanks,

Sally

>> fval

fval =

   -0.0111

>> 0.5*x_star'*H*x_star + f'*x_star

ans =

   -0.0143

>> [sum(x>ub & x<lb) sum(A*x>b) abs(Aeq*x-beq)>options.TolCon]

ans =

     0 0 0

>> [sum(x_star>ub & x_star<lb) sum(A*x_star>b) abs(Aeq*x_star-beq)>options.TolCon]

ans =

     0 0 0

Subject: Quadprog converges to suboptimal point?

From: Matt J

Date: 12 Jul, 2012 13:59:12

Message: 4 of 5

"sally" wrote in message <jtmk7v$6t2$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <jtktci$qn5$1@newscl01ah.mathworks.com>...
>
> > What evidence are you showing us here that the optimization failed? Why shouldn't we believe the output message that you're getting?
>
> Hi Matt,
>
> Here you go. x_star contains the solution from another optimizer which gives me a minimum of -.0143 which is less than x's -.0111. Both solutions do not violate any constraints.
>
> The interior-point-convex method does not take an x0, but the trust-region-reflective with starting point x0 = x_star does converge to x_star. So I don't think I formulated the constraints wrong.
>
> I am not saying the optimization "failed", just hoping someone can point me in the right direction to help figure out what is going on.
=============

We might have to see your code. Off the top of my head, the only thing I can think of is that xstar is the true optimum, but x (the output of the interior point method) might be a saddle point that you're getting stuck at. You haven't said that the quadratic you're minimizing is convex.

You could analyze the situation by plotting the objective function along the line between x and xstar. That would let you see if there's some sort of inflection shelf separating them.

Subject: Quadprog converges to suboptimal point?

From: Steve Grikschat

Date: 12 Jul, 2012 14:26:13

Message: 5 of 5

"Matt J" wrote in message <jtml7g$bcg$1@newscl01ah.mathworks.com>...
> "sally" wrote in message <jtmk7v$6t2$1@newscl01ah.mathworks.com>...
> > "Matt J" wrote in message <jtktci$qn5$1@newscl01ah.mathworks.com>...
> >
> > > What evidence are you showing us here that the optimization failed? Why shouldn't we believe the output message that you're getting?
> >
> > Hi Matt,
> >
> > Here you go. x_star contains the solution from another optimizer which gives me a minimum of -.0143 which is less than x's -.0111. Both solutions do not violate any constraints.
> >
> > The interior-point-convex method does not take an x0, but the trust-region-reflective with starting point x0 = x_star does converge to x_star. So I don't think I formulated the constraints wrong.
> >
> > I am not saying the optimization "failed", just hoping someone can point me in the right direction to help figure out what is going on.
> =============
>
> We might have to see your code. Off the top of my head, the only thing I can think of is that xstar is the true optimum, but x (the output of the interior point method) might be a saddle point that you're getting stuck at. You haven't said that the quadratic you're minimizing is convex.
>
> You could analyze the situation by plotting the objective function along the line between x and xstar. That would let you see if there's some sort of inflection shelf separating them.

Additional ideas on what could be happening...

Is xstar located near the bounds in some or all directions? Interior-point algorithms have difficulties approaching constraint boundaries. Perhaps the other solver was not interior-point?

How about the sensitivity of the objective? How close are x and xstar in relative terms? For some problems, small changes in x may yield more significant changes in the function values. This can be related to scaling as well.

Have you tried starting the trust-region algorithm from the x returned by the interior point algorithm? This could also help resolve the saddle point discussion.

Finally, you might try tightening the tolerances to make quadprog move closer to the solution. Try reducing TolFun to see if you can drive that complementarity measure lower.

+Steve

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us