0
$\begingroup$

I have to solve the problem

$$\min_x 1^Tx+\frac{\lambda}{2}\|\Omega\mu-x\|_2^2+\frac{\beta}{2}\|x-\bar{\gamma}\|_2^2\quad\text{w.r.t.}\quad Px-c=0,\ \ x\geq0$$

and in order to do that with Matlab I am currently using fmincon like that:

FMinValue = @(x) sum(x)            + lambda * sum((Omega*mu - x).^2) / 2 + beta * sum((x - gamma_bar).^2) / 2;
GradFMin  = @(x) ones(length(x),1) + lambda * (Omega*mu - x)             + beta * (x - gamma_bar);
Fmin = @(x) FMin(x, FMinValue, GradFMin); % merges FMinValue and GradFMin so that fmincon can handle it
HessianFPlusLagrangianPart = @(x, lagrange_multiplier) spdiags((beta-lambda)*ones(length(x),1),0,length(x),length(x));

options = optimoptions('fmincon', 'Algorithm', 'interior-point' , 'GradObj', 'on', 'Hessian', 'user-supplied', 'HessFcn', HessianFPlusLagrangianPart);
x = fmincon(Fmin, ones(length(gamma_bar), 1), [], [], P_bar, c_bar, zeros(length(gamma_bar), 1), [], [], options);

Here $\lambda$ and $\beta$ are fixed parameters which could be equal. If that is the case then $\lambda-\beta=0$ which means my hessian matrix is zero as well. Of course I get the Matlab warning Warning: Matrix is close to singular or badly scaled, but a zero hessian is correct in this case.

Any suggestions what to do in this situation? Unfortunately I cannot change to lsqnonlin because I have got the linear term sum(x) in my objectiv function. And I cannot use another algorithm instead of interior-point either, since I have bound and linear constraints at the same time.

How to overcome this problem and make it work for all choices of $\lambda$ and $\beta$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ At first, I wonder why you want to use the general nonlinear solver to solve a simple convex quadratic problem (for which there are loads of efficient solvers for MATLAB)? Second, the linear term is no problem, $x+(x-\gamma)^2 = (x-(\gamma-1/2))^2-1/4+\gamma$. Generalize and you'll see lsqnonlin is applicable. $\endgroup$
    – Johan Löfberg
    May 27, 2014 at 10:50
  • $\begingroup$ Wow, thanks for that very useful comment! With that reformulation I can even use lsqlin. This should actually be the right answer. Regarding your first question: I just wanted to use fmincon, because I thought there is no applicable, more specific solver. Of course I wasn't happy with it at all. Thanks again! $\endgroup$
    – Rob
    Jun 2, 2014 at 12:05

2 Answers 2

Reset to default
1
$\begingroup$

The problem is (likely) that your gradient and Hessian are incorrect: $$\nabla \left(\frac\lambda 2 \|\Omega\mu-x\|_2^2 \right)= \lambda(\Omega\mu-x)(-1) = \lambda(x-\Omega\mu)$$ and hence the corresponding part of the Hessian is $$\nabla^2 \left(\frac\lambda 2 \|\Omega\mu-x\|_2^2 \right) = \lambda I.$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, yes, you are totally right. I forgot the $-1$ from the inner derivative which would yield $\lambda+\beta$ in the hessian. Still the little problem remains, what to do if $\lambda=-\beta$, but I don't even know if I need this case. I guess not... Thanks again! Thinking to delete the question... $\endgroup$
    – Rob
    May 26, 2014 at 14:54
  • 1
    $\begingroup$ Penalty parameters should always be nonnegative, so I would be surprised if this case came up in practice. $\endgroup$
    – Christian Clason
    May 26, 2014 at 14:55
2
$\begingroup$

One way you could overcome this situation is to correct the Hessian of your objective function, which should be $(\lambda + \beta)I$, and then see if you still have scaling issues.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.