Nonconvex minimization of a quadratic function over a sphere
Tóm tắt
The problem of minimizing a nonconvex function over a sphere is reduced to a sequence of problems of minimizing its convex majorants over the sphere. To construct the majorants, the objective function is represented as the difference of convex quadratic functions, and the problem is solved at the previous step. The objective function representation is based on a modified procedure of the Cholesky decomposition of symmetric indefinite matrices.
Tài liệu tham khảo
Dennis, J. and Schnabel, R., Chislennye metody bezuslovnoi optimizatsii i resheniya nelineinykh uravnenii (Numerical Methods of Unconstrained Optimization and Nonlinear Equations), Moscow: Mir, 1988.
Nechaeva, M.S. and Khamisov, O.V., A Branch-and-Bound Method for the Problem of Minimizing a Quadratic Function under Convex Quadratic Constraints, Diskr. An. Iss. Oper., ser. 2, 2000, Vol. 7, No. 2, pp. 74–88.
Gay, D.M., Computing Optimal Locally Constrained Steps, SIAM J. Sci. Comput., 1981, Vol. 2, No. 2, pp. 186–197.
Ye, Y., On Affine Scaling Algorithms for Nonconvex Quadratic Programming, Math. Programming, 1992, Vol. 56, No. 3, pp. 285–300.
Hager, W.W., Minimizing a Quadratic over a Sphere, SIAM J. Optim., 2001, Vol. 12, No. 1, pp. 188–208.
Polyak, B.T., Vvedenie v optimizatsiyu (Introduction to Optimization), Moscow: Nauka, 1983.
Kotel’nikov, E.A., A Method of Exhaustion for Symmetric Matrices, Preprint of Computer Center, Siberian Branch, Russ. Acad. Sci., Novosibirsk, 1997, no. 1083.
Gill, P.E., Murray, W., and Wright, M., Prakticheskaya optimizatsiya (Practical Optimization), Moscow: Mir, 1985.
Kotel’nikov, E.A., Minimization of a Quadratic Function over a Sphere, Sib. Zh. Vych. Mat., 2014, Vol. 17, No. 4, pp. 329–338.