1
$\begingroup$

I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the the Hessian semi-definite.

I solve material placement optimisation problem. Each variable $w_i$ corresponds to material amount in the i-th node, so each variable is between [0,1] or [0.1, 1] and sum of material is constant, that is $\sum_i w_i = const$.

The current idea is to use convex solvers for convex part, with randomised or brute-force approach for the rest of variables. I also thought about convexifiying the given function, and then tracking backwards from this "fully convex" solution. How those kind of problems is treated in practice? What is state of the art?

$\endgroup$
12
  • $\begingroup$ Are those your only constraints? Can you show us what the objective function looks like? Did you compute the "exact" Hessian of the objective function? Can you compute the exact gradient of the objective function? What is the dimension (number of optimization variables) of the problem? Do you have a good initial guess as to the optimum? $\endgroup$ Aug 7, 2016 at 12:16
  • $\begingroup$ @MarkL.Stone yes, those are my only constraints. Objective function is a function of solution of elasticity PDE, and it is too cumbersome, to type, here. The Hessian took me several A3 lists to derive, and yes, I can have exact Hessian and gradient, although they are incredibly cumbersome. The dimensions are like 128^2/128^3 and 256^2/256^3. I'd like some pointers and references to get me back on track, and if this won't work out I will ask for more help, but I thought those kinds of problem ought to be very well researched so I have only to apply known methods. $\endgroup$
    – Moonwalker
    Aug 7, 2016 at 19:32
  • $\begingroup$ @MarkL.Stone and honestly, I've got stuck, yes, but I still want to figure it out mostly myself. Truth be there is an element of pride, foolish as it is. $\endgroup$
    – Moonwalker
    Aug 7, 2016 at 19:40
  • 1
    $\begingroup$ How long does it take for each objective function evaluation, each gradient evaluation, each Hessian evaluation? Do you get time savings by computing one or more of them at the same time at a given argument value? $\endgroup$ Aug 7, 2016 at 23:20
  • 1
    $\begingroup$ Is this just a one-time problem and you really just want to get the answer, and not worry about the speed? If so, consider using a linearly constrained Newton trust region method, if Hessian evaluation is not too slow. You can try using the suboptimal point you're stuck on as a starting point. If Hessian takes too long to evaluate, then consider linearly constrained Quasi-Newton method, using trust region or line search if usng BFGS or L-BFGS, or using trust region if using SR1. Choice of BFGS vs. SR1 may come down to amount and extent of non-convexity in objective function on solution path. $\endgroup$ Aug 8, 2016 at 0:23

0

Your Answer

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

Browse other questions tagged or ask your own question.