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$?

$\endgroup$
  • 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 '14 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 '14 at 12:05
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.$$

$\endgroup$
  • $\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 '14 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 '14 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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