The Cutting-Plane Method for Solving Convex Programs

By J. E. Kelley. 1960

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning Optimized Risk Scores (2016, methodology): “ of ^lk() + C0 kk 0, it follows that k+ C0kkk0 = ^lk k + C0kkk0 ^lk() + C0 kk 0 V() Algorithm 1 converges to "-optimal solution of RiskSlimMINLP in a xed number of iterations (see Kelley, 1960, for a proof). To see this, note that the cutting plane approximation of a convex loss function impr”
On the Behrens–Fisher problem: A globally convergent algorithm and a finite-sample study of the Wald, LR and LM tests (2008, background): “1Such approximation for convex sets can be traced back to the Cutting Planes Algorithm in the Optimization literature [3, 13, 14].”
$\propto$SVM for learning with label proportions (2013, methodology): “This form enables us to apply the cutting plane method (Kelley Jr, 1960) to incrementally include the most violated y into Yactive, and then solve the MKL problem, (14) with Y replaced as Yactive.”
Chance-Constrained Optimal Power Flow: Risk-Aware Network Control under Uncertainty (2012, unknown): “For a classical reference, see [36].”
Analysis of stochastic dual dynamic programming method (2011, methodology): “It also could be noted that the above ‘‘backward step” procedure is the standard cutting plane algorithm (Kelley’s cutting plane algorithm [6]) applied to the SAA problem (2.”
Variable Neighborhood Search (2018, methodology): “[95] J.E. Kelley (1960) The cutting-plane method for solving convex programs.”
Bundle Methods for Regularized Risk Minimization (2010, methodology): “Similar to the CPM the proximal bundle method also builds a piecewise linear lower boundJCPt (see (4)).”
A Primer on Monotone Operator Methods (2015, background): “By judiciously choosing points to evaluate and accumulating the cutting planes, one can localize a small set in which x⋆ must lie in [29,65,68,73,78,91,92,95,107,108].”
Monte Carlo sampling-based methods for stochastic optimization (2014, methodology): “L-shaped method in stochastic programming is commonly known as Benders’ decomposition (Benders [22]) in mixed-integer programming and Kelley’s cutting plane algorithm in convex programming (Kelley [127], HiriartUrruty and Lemaréchal [106]).”
A new MILP based approach for unit commitment in power production planning (2013, methodology): “The algorithm is an application of Kelley’s theorem on the cutting plane method for convex programs (see [25]), which states the conditions and method of obtaining a sequence of points that converge to the minimum of a convex function in a compact, convex set, using successive linear approximations.”
Maximum Margin Multiple Instance Clustering With Applications to Image and Text Clustering (2011, methodology): “In this way, the successive strengthening approximation series of the problem (12) is constructed by the expanding number of cutting planes that cut off the current optimal solution from the feasible set [14].”
Recent Advances of Large-Scale Linear Classification (2012, methodology): “[112], [118]) use a cutting plane method [119] to solve (45).”
Uncertain convex programs: randomized solutions and confidence levels (2005, methodology): “The dual analog of these methods can indeed be viewed as a constraint reduction technique, and it is related to Kelley’s cutting plane methods for convex programming, [20].”