English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper, we consider an SDP relaxation of the quadratic knapsackproblem (QKP). After using the Burer-Monteiro factorization, we get anon-convex optimization problem, whose feasible region is an algebraic variety.Although there might be non-regular points on the algebraic variety, we provethat the algebraic variety is a smooth manifold except for a trivial point fora generic input data. We also analyze the local geometric properties ofnon-regular points on this algebraic variety. In order to maintain theequivalence between the SDP problem and its non-convex formulation, we derive anew rank condition under which these two problems are equivalent. This new rankcondition can be much weaker than the classical rank condition if thecoefficient matrix has certain special structures. We also prove that under anappropriate rank condition, any second order stationary point of the non-convexproblem is also a global optimal solution without any regularity assumption.This result is distinguished from previous results based on LICQ-likesmoothness assumption. With all these theoretical properties, we design analgorithm that equip a manifold optimization method with a strategy to escapefrom non-optimal non-regular points. Our algorithm can also be used as aheuristic for solving the quadratic knapsack problem. Numerical experiments areconducted to verify the high efficiency and robustness of our algorithm ascompared to other SDP solvers and a heuristic method based on dynamicprogramming. In particular, our algorithm is able to solve the SDP relaxationof a one-million dimensional QKP with a sparse cost matrix very accurately inabout 20 minutes on a modest desktop computer.

A feasible method for solving an SDP relaxation of the quadratic knapsack problem