On the complexity of approximating a KKT point of quadratic programming
From MaRDI portal
Publication:1380927
DOI10.1007/BF01581726zbMath0894.90117OpenAlexW2063676335MaRDI QIDQ1380927
Publication date: 7 September 1998
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01581726
quadratic programminglocal minimizerfully polynomial-time approximation schemeKKT pointpotential reduction algorithm
Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20)
Related Items
A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms, High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks, Accelerated Methods for NonConvex Optimization, A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity, An L p Norm Relaxation Approach to Positive Influence Maximization in Social Network under the Deterministic Linear Threshold Model, Newton-KKT interior-point methods for indefinite quadratic programming, An improved algorithm for the \(L_2-L_p\) minimization problem, Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions, Some theoretical limitations of second-order algorithms for smooth constrained optimization, A new global algorithm for factor-risk-constrained mean-variance portfolio selection, Effective algorithms for optimal portfolio deleveraging problem with cross impact, Linear-step solvability of some folded concave and singly-parametric sparse optimization problems, A note on the complexity of \(L _{p }\) minimization, A FPTAS for computing a symmetric leontief competitive economy equilibrium, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems, Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming, Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
Cites Work
- A continuous approach to inductive inference
- A new polynomial-time algorithm for linear programming
- Constrained global optimization: algorithms and applications
- Checking local optimality in constrained quadratic programming is NP- hard
- How easy is local search?
- On affine scaling algorithms for nonconvex quadratic programming
- Complexity of uniqueness and local search in quadratic 0-1 programming
- Combining binary search and Newton's method to compute real roots for a class of real functions
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Introduction to global optimization
- The complexity of approximating a nonlinear program
- Complementary pivot theory of mathematical programming
- Some NP-complete problems in quadratic and nonlinear programming
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- Computing Optimal Locally Constrained Steps
- Newton’s Method with a Model Trust Region Modification
- A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem
- A method for the solution of certain non-linear problems in least squares
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
