Exploiting Known Structures to Approximate Normal Cones

• 成果类型: Article
• 署名作者: Davis, Chad; Hare, Warren
• 署名单位: University of British Columbia
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0590
• 发表日期: 2013
• 页码: 665-681
• 关键词: search methods; optimization; gradient; algorithm

摘要

The normal cone to a constraint set plays a key role in optimization theory, algorithms, and applications. We consider the question of how to approximate the normal cone to a set under the assumption that the set is provided through an oracle function or collection of oracle functions, but contains some exploitable structure. We provide a new simplex gradient-based approximation technique that works for sets defined through a finite number of oracle-based functions. We further present novel results showing that, under a non-degeneracy condition, approximating normal cones to intersections of sets is possible by taking sums of approximations. Finally, we provide numerical results that exemplify the accuracy of the simplex gradient approximation when it is applicable, and the failure of this technique when a linear independence constraint qualification is not met.