Path Following in the Exact Penalty Method of Convex Programming

Details Path Following in the Exact Penalty Method of Convex Programming Path Following in the Exact Penalty Method of Convex Programming

2012-01-17

arxiv.org/abs/1201.3593v1

Mathematics

Numerical Analysis

Scientific paper

Classical penalty methods solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to $\infty$, one recovers the constrained solution. In the exact penalty method, squared penalties are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. In practice, the kinks in the penalty and the unknown magnitude of the penalty constant prevent wide application of the exact penalty method in nonlinear programming. In this article, we examine a strategy of path following consistent with the exact penalty method. Instead of performing optimization at a single penalty constant, we trace the solution as a continuous function of the penalty constant. Thus, path following starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. For quadratic programming, the solution path is piecewise linear and takes large jumps from constraint to constraint. For a general convex program, the solution path is piecewise smooth, and path following operates by numerically solving an ordinary differential equation segment by segment. Our diverse applications to a) projection onto a convex set, b) nonnegative least squares, c) quadratically constrained quadratic programming, d) geometric programming, and e) semidefinite programming illustrate the mechanics and potential of path following. The final detour to image denoising demonstrates the relevance of path following to regularized estimation in inverse problems. In regularized estimation, one follows the solution path as the penalty constant decreases from a large value.

Affiliated with

Also associated with

No associations

Rating

Path Following in the Exact Penalty Method of Convex Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Path Following in the Exact Penalty Method of Convex Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path Following in the Exact Penalty Method of Convex Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-98099