fminunc: Interior Point Algorithm

Hey guys,

I was recently trying to give initial values for the dual-variables (Lagrange-Multipliers and Slack-Variables) in fmincon. You can see the old question here .

As I had to find out, that this is not possible, I am trying to implement an algorithm for the non-linear constrained optimization on my own, trying to do this as time efficient as possible.

So my idea was to just include the constraints with Lagrange-Multipliers, Penalty-Functions and Slack-Variables on my own.

I was reading literature and included the constraints as follows:

    %%Lagrangian
    L=cost(u)+y'*equality(u)'+z'*(inequality(u)'+s)-bar*(ones(1,e)*log(s));

Where "equality" is a function containing all the equality constraints, and respectively inequality is a function containing all the inequality constraints.

"y" is a vector with the Langrange-Multipliers for the equality-constraints, "z" are the Langrange-Multipliers for the inequlity-constraints and "s" are the slack-variables for the inequality-constraints. The last term is a barrier-function for the slack-varibales.

So what I am trying to do right now, is to minimze over this new objective function with the 'quasi-newton'-method in fminunc.

But... it doesn't yet work properly and the constraints get violated.

So as I'm not too familiar with optimization, my question is:

Is my approach correct or am I missing something? Is it sufficient to just include the constraints as described above, and apply the Newton-Method on this new objective function?

Hope someone can help me with this one.

Thanks!

Answer 1

[Matt J]

No, it won't work that way. Replacing the constrained problem with an unconstrained minimization of the Lagrangian works only if you already know the optimal values of the dual variables. Even then, I believe it only works for convex problems.

[Jakob]

So what do I have to do then? Let's assume the problem is convex.

First optimize (minimize) over the primal varibales with fixed values for the dual-variables.

And in a second step, optimize (maximize) over the dual-variables with fixed values for the primal ones?

[Matt J]

I don't know if there's a perfect solution beyond re-implementing the whole interior-point method.

However, an idea that I had involves you going back to fmincon and explicitly enforcing the constraints. After the first call fmincon, you obtain the Lagrange multipliers, lambda0, from the outputs

[x,fval,exitflag,output,lambda0] = fmincon(f,...)

Then, when you make the next call fmincon, instead of feeding it the original objective function f(x), you instead feed the Lagrangian

L(x)=f(x)+lambda0*constraints(x)

Now, this will not prevent fmincon from initiating a new set of Lagrange multipliers lambda1. However, effectively it will be building a new Lagrangian internally of the form

   L(x)=f(x) + lambda0*constraints(x) + lambda1*constraints(x) 

       =f(x) + (lambda0+lambda1)*constraints(x)

       =f(x) + Lambda*constraints(x)

I believe this is almost the same thing as initializing the 2nd optimization with lambda0 itself, because lambda1 will need to be only a small(er) increment of lambda0 for a solution to be reached. In fact, it should be exactly the same if the default initialization of the Lagrange multipliers is lambda1=0, although I don't think we know if that's how fmincon works.

In the 3rd call to fmincon, you would of course modify the objective again,

L(x)=f(x) + (lambda0+lambda1)*constraints(x)

and so forth.

[Jakob]

But I have to admit, that i dont get the point. The lambdas are always initial values of the minimization. So you would just sum up over all the initial values, instead of properly update them.

[Matt J]

No, you would sum the final values of the lambdas.

Again, supposing that fmincon chooses lambda=0 in any given run as the starting point for the dual variables, the scheme should be equivalent to resuming from the previous lambda.

Either way, you are feeding forward information on the Lagrangian in each pass through fmincon, so it has to be beneficial somehow.

[Matt J]

Jakob commented:

Okay, now I got it.

Will give it a try and give report.

Answer 2

[Matt J]

Another thing you could try is to apply FMINUNC with unknowns (u,y,z,s) to the function

F(u,y,z,s)= norm( [LagrangianGradient(u,y,z.^2) ; equality(u); 
                   (inequality(u)+s.^2); inequality(u).*z.^2] )^2

This is similar to what you attempted in your posted question, but here F=0 does correspond to an optimal point and the positivity of slack and Lagrange multipliers is enforced inherently by the squaring s.^2 and z.^2.