Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10107-013-0644-1 | Mathematical Programming: Series A and B |
Keywords | Field | DocType |
90c27,90c46,90c35,critical cone,90c20,quadratic programming,optimality conditions,90c60,90c30,graph partitioning,vertex separator,edge-convexity | Discrete mathematics,Combinatorics,Mathematical optimization,Reduced cost,Vertex (geometry),Polyhedron,Vertex separator,Edge (geometry),Quadratic programming,Graph partition,Mathematics,Face (geometry) | Journal |
Volume | Issue | ISSN |
145 | 1-2 | 1436-4646 |
Citations | PageRank | References |
4 | 0.42 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| William W. Hager | 1 | 1603 | 214.67 |
| James T. Hungerford | 2 | 11 | 1.57 |