Inexact variable metric method for convex-constrained optimization problems

Abstract

This paper is concerned with the inexact variable metric method for solving convex-constrained optimization problems. At each iteration of this method, the search direction is obtained by inexactly minimizing a strictly convex quadratic function over the closed convex feasible set. Here, we propose a new inexactness criterion for the search direction subproblems. Under mild assumptions, we prove that any accumulation point of the sequence generated by the new method is a stationary point of the problem under consideration. In order to illustrate the practical advantages of the new approach, we report some numerical experiments. In particular, we present an application where our concept of the inexact solutions is quite appealing.

Keywords:

• Convex-constrained optimization problem
• approximate solution
• projected gradient method
• spectral gradient method
• inexact variable metric method

2010 Mathematics Subject Classifications:

• 90Cxx
• 90C30
• 65Kxx

Acknowledgements

We are indebted to two anonymous reviewers whose comments helped to improve this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 For MINQ8 solver, it seems that the main cost per iteration is $O\left(|I{|}^3\right)$ for solving a linear system of size $|I|\le m$, where I is the set of inactive constraints. On the other hand, each iteration of the revised simplex costs $O\left(m^2\right)$. If the revised simplex takes q iterations, then $O\left(q{m}^2\right)$ is the cost for the inner iteration of Algorithm 1, which is comparable with the cost of a MINQ8 iteration when q and $|I|$ are close to m.

2 with respect to the Frobenius norm

3 Assuming that the convex function q is α-strongly convex and L-smooth, the corresponding condition number is given by $\kappa =L/\alpha$. See [33] for details.

4 the reduction in the objective should be at least one percent of its value in the previous iterate.

Additional information

Funding

The work of this author was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Grant Number 421386/2016-9. The work of these authors was supported in part by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES), 88881.310538/2018-01, FAPEG/PRONEM-201710267000532 and Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Grant Numbers 302666/2017-6, 408123/2018-4.