Optimization Online


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

Gabriel Haeser(ghaeser***at***ime.usp.br)
Hongcheng Liu(hql5143liu***at***gmail.com)
Yinyu Ye(yinyu-ye***at***stanford.edu)

Abstract: 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 reduces 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 trust-region point 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 the literature, our results also indicate that best known complexity bounds hold for a wider class of nonlinear programming problems.

Keywords: Constrained optimization, Nonconvex programming, Interior point method, First order algorithm, Nonsmooth problems

Category 1: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 02/14/2017
Entry Accepted: 02/14/2017
Entry Last Modified: 02/14/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society