Optimization with a vector of penalty functions

I'd be very grateful for any pointers on how to solve my optimization problem.

I have 10 equality constraints to fulfill (bEq) 45 weights (x) I can adjust to fulfill these constraints (each of which affects 2 equality constraints)

I want to find the vector of weights (x) which minimises the summed penalty function subject to the boundary constraint that the minimum weight x(i) = 0 for all i.

If my problem has a vector of numeric penalties associated with each x(i) then it is a relatively easy linprog problem:

• min(f(x)) - where f is my costVectorS.T.
• AEq * x = bEq
• x(i) >= 0 (for all i)

so I would run

[weightsLP,fValLP,exitFlagLP] = ...
linprog(costVector,[],[],AEq,bEq,lowerBounds,[],[],options);

(where options sets my tolerences).

However, my true penalty is not a numeric vector but a vector of functions of x. Where my penalty function is quadratic it looks like:

global coeff mu;

coeffLocal = [coeff;coeff];
muLocal = [mu;mu];

N = size(coeffLocal,1);
y = zeros(N,1);
for i = 1:N
    if abs(x(i)) > 1e-6
        y(i) = coeffLocal(i,1) * ((abs(x(i))-muLocal(i,1))/muLocal(i,2))^2 + ...
            coeffLocal(i,2) * (abs(x(i))-muLocal(i,1))/muLocal(i,2) + ...
            coeffLocal(i,3);

      end
  end
  f = sum(y);

Where the final summation gives me the cost associated with the vector x, coeff is an Nx3 array of quadratic function parameters and mu an Nx2 array of rescaling parameters.

I have tried running fmincon to solve this problem using the results of the linprog step as initial starting point. No matter what I do to the function and step size tolerences I seem to get initial result back - stuck in a local minimum - which I can show is not the correct solution when I look at the quadratic penalty functions.

Am I missing something? Should I be running a different optimization function - ie not fmincon? I appreciate that this is a very general question but I cannot find anything obvious in the help pages which suggests I am going about this the wrong way.

Many thanks, Oliver

[Oliver]

I probably should have added that fgoalattain also gives me whatever initial x I give it

Answer 1

[Steve Grikschat]

Hi Oliver,

I think that fmincon is struggling with this for two reasons. fmincon is meant to work on smooth-continuous problems. You're function appears to be neither from what I can tell. Fmincon will struggle near the discontinuities/singularities.

Is the cutoff on the magnitude of x (1e-6) needed? Perhaps you can change your lower bounds from 0 to 1e-6? What about the abs() on the value of x?

If not, my advice would be to get this objective in a formulation for QUADPROG:

x'*H*x + f'*x

That will probably be much faster and smooth.

+Steve

[Oliver]

Steve,

Many thanks for your answer.

Good point on the cutoff, I should not have included

that in the objective function I posted - it is redundant

given I can adjust the x tolerence with optimset.

On the abs value of x being in there - yes I believe

that's necessary as with my current formulation of the

problem it allows me to specify that the penalty for using

+1 or -1 units of an individual element of x are the same.

Thanks again,

Oliver

Answer 2

[Oliver]

I do not believe the quadprog route will work.

The minimization I need to perform is over:

\sum_{i=1}^N (a_i x_i^2 + b_i x_i + c_i)

ST to the constraints mentioned in my earlier question

• x_i >= 0 for all i
• AEq x = bEq

Given I have constants in each quadratic and there are no cross terms I don't see a way to write this in the form:

x'Hx + fx

so I don't think quadprog will help. Any suggestions very gratefully received.

Many thanks, Oliver