Optimality conditions for maximizing a function over a polyhedron
成果类型：
Article
署名作者：
Hager, William W.; Hungerford, James T.
署名单位：
State University System of Florida; University of Florida
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-013-0644-1
发表日期：
2014
页码：
179-198
关键词：
摘要：
We present new first and second-order optimality conditions for maximizing a function over a polyhedron. These conditions are expressed in terms of the first and second-order directional derivatives along the edges of the polyhedron, and an edge description of the polyhedron. If the objective function is quadratic and edge-convex, and the constraint polyhedron includes a box constraint, then local optimality can be checked in polynomial time. The theory is applied to continuous formulations of the vertex and edge separator problems. It is seen that the necessary and sufficient optimality conditions for these problems are related to the existence of edges at specific locations in the graph.