MATLAB: Optimization with a vector of penalty functions

optimizationOptimization Toolbox

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

Best Answer

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
Related Question