On the complexity of approximating a KKT point of quadratic programming
From MaRDI portal
Publication:1380927
DOI10.1007/BF01581726zbMATH Open0894.90117OpenAlexW2063676335MaRDI QIDQ1380927FDOQ1380927
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
Quadratic programming (90C20) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- An Algorithm for Least-Squares Estimation of Nonlinear Parameters
- A method for the solution of certain non-linear problems in least squares
- Some NP-complete problems in quadratic and nonlinear programming
- Constrained global optimization: algorithms and applications
- Complementary pivot theory of mathematical programming
- How easy is local search?
- Introduction to global optimization
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Computing Optimal Locally Constrained Steps
- Newton’s Method with a Model Trust Region Modification
- Complexity of uniqueness and local search in quadratic 0-1 programming
- The complexity of approximating a nonlinear program
- On affine scaling algorithms for nonconvex quadratic programming
- Checking local optimality in constrained quadratic programming is NP- hard
- A continuous approach to inductive inference
- Combining binary search and Newton's method to compute real roots for a class of real functions
- A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem
Cited In (22)
- A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity
- A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation
- Quasi-orthogonalization for alternating non-negative tensor factorization
- A note on the complexity of \(L _{p }\) minimization
- Some theoretical limitations of second-order algorithms for smooth constrained optimization
- Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
- A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms
- Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions
- A generalization of the Karush-Kuhn-Tucker theorem for approximate solutions of mathematical programming problems based on quadratic approximation
- Newton-KKT interior-point methods for indefinite quadratic programming
- Effective algorithms for optimal portfolio deleveraging problem with cross impact
- Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
- A new global algorithm for factor-risk-constrained mean-variance portfolio selection
- Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems
- An L p Norm Relaxation Approach to Positive Influence Maximization in Social Network under the Deterministic Linear Threshold Model
- An improved algorithm for the \(L_2-L_p\) minimization problem
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Accelerated Methods for NonConvex Optimization
- Linear-step solvability of some folded concave and singly-parametric sparse optimization problems
- New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
- High-Dimensional Learning Under Approximate Sparsity with Applications to Nonsmooth Estimation and Regularized Neural Networks
- A FPTAS for computing a symmetric leontief competitive economy equilibrium
This page was built for publication: On the complexity of approximating a KKT point of quadratic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380927)
