Busca avançada
Ano de início
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary

Texto completo
Haeser, Gabriel [1] ; Liu, Hongcheng [2] ; Ye, Yinyu [3]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Math & Stat, Dept Appl Math, Sao Paulo, SP - Brazil
[2] Stanford Univ, Dept Radiat Oncol, Stanford, CA 94305 - USA
[3] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 - USA
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: MATHEMATICAL PROGRAMMING; v. 178, n. 1-2, p. 263-299, NOV 2019.
Citações Web of Science: 1

In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is available. For this type of problems, existing necessary conditions often rely on the notion of subdifferential or become non-trivially weaker than the KKT condition in the (twice-)differentiable counterpart problems. In contrast, this paper presents a new set of first- and second-order necessary conditions that are derived without the use of subdifferential and reduce to exactly the KKT condition when (twice-)differentiability holds. As a result, these conditions are stronger than some existing ones considered for the discussed minimization problem when only non-negativity constraints are present. To solve for these optimality conditions in the special but important case of linearly constrained problems, we present two novel interior point trust-region algorithms and show that their worst-case computational efficiency in achieving the potentially stronger optimality conditions match the best known complexity bounds. Since this work considers a more general problem than those in the literature, our results also indicate that best known existing complexity bounds are actually held for a wider class of nonlinear programming problems. This new development is significant since optimality conditions play a fundamental role in computational optimization and more and more nonlinear and nonconvex problems need to be solved in practice. (AU)

Processo FAPESP: 13/05475-7 - Métodos computacionais de otimização
Beneficiário:Sandra Augusta Santos
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 16/02092-8 - Informação de segunda-ordem em otimização não linear
Beneficiário:Gabriel Haeser
Linha de fomento: Bolsas no Exterior - Pesquisa