2
$\begingroup$

I am trying to solve a non-convex optimization problem with the help of sequential quadratic programming.

enter image description here

I need to develop an algorithm inside SQP to solve this subproblem. What potential methods (conjugate gradient, etc) can be used to solve this, keeping in mind the Hessian $H$ is not positive semidefinite?

$\endgroup$

2 Answers 2

1
$\begingroup$

Use an off-the-shelf non-convex QP solver. There is a choice of solving to local optimality or to global optimality. Solving to local optimality is generally much faster, and may (but not necessarily) provide better overall algorithm progress (with starting point for the QP solve being the current iterate (incumbent)). That is because a local minimum is more likely to be close to the starting point, and therefore be in a region where the QP objective function is likely to be a better model of the objective of the original problem. If the QP solves for the step to the new iterate (which your formulation apparently does based on $\Delta x$ ), then a starting point of the vector of zeros can be used for the QP solve.

Or use a damped BFGS update for the Hessian (which maintains positive semidefiniteness), combined with a convex QP solver.

$\endgroup$
4
  • $\begingroup$ I need to implement some algorithms; I don't want to use some solvers. I have read about the conjugate gradient method in theory, which can be used for the above problem. I want to know if there are some others which I should explore, and the BFGS method for Hessian approximation is also in my mind. $\endgroup$
    – Muhammad
    Apr 19, 2023 at 8:53
  • 1
    $\begingroup$ For an SQP method, you have choice of 1) how the Hessian is calculated or approximated, for example BFGS (convex QP subproblem) or SR1 (non-convex QP subproblem) 2) trust region or line search 3) choice of merit function or use filter 4) choice of algorithm (which is affected by whether QP subproblems are convex or not) to solve QP subproblem. These can be combined in essentially any combination. $\endgroup$ Apr 19, 2023 at 12:17
  • $\begingroup$ I appreciate your help. My hessian is not positive semi-definite, so the above problem is non-convex. H = bfgs(method). And now, moving to the 4rth point in your answer, "the choice of an algorithm that can be used to solve the above minimization problem. i need help finding methods for solving this problem. $\endgroup$
    – Muhammad
    Apr 19, 2023 at 13:20
  • 1
    $\begingroup$ If you are using BFGS, why isn't the Hessian positive semidefinite (unless you are not using damped BFGS and the problem is constrained or gradients have (stochastic) errors,)? Nocedal and Wright "Numerical Optimization" link.springer.com/book/10.1007/978-0-387-40065-5 is a good book to read if you want to try to implement your own SQP solver, or to modify an existing solver. But what you are asking for,, teams of experts may spend several to tens or hundreds or person years to develop, so more than can be covered on this forum. $\endgroup$ Apr 19, 2023 at 20:31
0
$\begingroup$

Why not try out an existing SQP method that solves indefinite QPs, such as filterSQP? It is extremely robust and efficient. As globalization strategies, it uses a filter strategy to accept/reject iterates and a trust region to restrict the length of the step. It can even be tested online: https://neos-server.org/neos/solvers/nco:filter/AMPL.html

$\endgroup$

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.