Some NP-complete problems in quadratic and nonlinear programming
From MaRDI portal
Publication:3778558
DOI10.1007/BF02592948zbMath0637.90078WikidataQ60608950 ScholiaQ60608950MaRDI QIDQ3778558
Santosh N. Kabadi, Katta G. Murty
Publication date: 1987
Published in: Mathematical Programming (Search for Journal in Brave)
NP-completecopositiveindefinite quadratic programscontinuous variable, smooth, nonconvex nonlinear programminginteger square matrix
Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Quadratic programming (90C20)
Related Items
Learning Dynamical Systems with Side Information, The maximum feasible subset problem (maxFS) and applications, On the accuracy of uniform polyhedral approximations of the copositive cone, Algebraic Perspectives on Signomial Optimization, Tensors in computations, Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery, Lifting for Simplicity: Concise Descriptions of Convex Sets, Algorithms and Software for Convex Mixed Integer Nonlinear Programs, Matrix Relaxations in Combinatorial Optimization, Continuous quadratic programming formulations of optimization problems on graphs, Irreducible elements of the copositive cone, On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming, Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, Accelerated Methods for NonConvex Optimization, An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix, A Nonconvex Optimization Approach to IMRT Planning with Dose–Volume Constraints, Sufficient conditions for the synthesis ofH? fixed-order controllers, Unnamed Item, The problems of non-convex quadratic programming related to phased antenna arrays optimization, Lower bounds for non-convex stochastic optimization, Convex computation of maximal Lyapunov exponents, A practical approach to SOS relaxations for detecting quantum entanglement, Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems, Geometric control of hybrid systems, The boosted DC algorithm for linearly constrained DC programming, Black holes and the loss landscape in machine learning, Auxiliary functions as Koopman observables: data-driven analysis of dynamical systems via polynomial optimization, A Sum of Squares Characterization of Perfect Graphs, Uniform exponential stability criteria with verification for nonautonomous switched nonlinear systems with uncertainty, On the weak second-order optimality condition for nonlinear semidefinite and second-order cone programming, A geometric approach of gradient descent algorithms in linear neural networks, Multi-activity influence and intervention, A General Regularized Continuous Formulation for the Maximum Clique Problem, A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Performance comparison of two recently proposed copositivity tests, On the degree of varieties of sum of squares, Using Intersection of Unions to Minimize Multi-directional Linearization Error in Reachability Analysis, Unnamed Item, A convergence analysis of Nesterov's accelerated gradient method in training deep linear neural networks, Sampling rates for \(\ell^1\)-synthesis, Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions, Convex Relaxations of Integral Variational Problems: Pointwise Dual Relaxation and Sum-of-Squares Optimization, Sublinear circuits and the constrained signomial nonnegativity problem, An approximation algorithm for indefinite mixed integer quadratic programming, First-Order Methods for Nonconvex Quadratic Minimization, Sum-of-squares chordal decomposition of polynomial matrix inequalities, The cone of \(5 \times 5\) completely positive matrices, Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem, Finding positively invariant sets and proving exponential stability of limit cycles using sum-of-squares decompositions, Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points, A Trust Region Method for Finding Second-Order Stationarity in Linearly Constrained Nonconvex Optimization, A Lanczos Method for Large-Scale Extreme Lorentz Eigenvalue Problems, Unnamed Item, Relative Robust Portfolio Optimization with benchmark regret, Bounding extrema over global attractors using polynomial optimisation, DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization, Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming, A guide to conic optimisation and its applications, A sufficient conditions for global quadratic optimization, Machine Learning: Deepest Learning as Statistical Data Assimilation Problems, Unnamed Item, Canonical Duality Theory: Connections between Nonconvex Mechanics and Global Optimization, Minimum wave speeds in monostable reaction–diffusion equations: sharp bounds by polynomial optimization, Analytical expressions of copositivity for fourth-order symmetric tensors, Contribution of copositive formulations to the graph partitioning problem, Bitopological spaces, Copositive realxation for genera quadratic programming, Solving the canonical dual of box- and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm, A copositivity probe, The CP-Matrix Approximation Problem, Extremal copositive matrices with minimal zero supports of cardinality two, A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, Unnamed Item, A Robust Optimization Model for Managing Elective Admission in a Public Hospital, Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints, Best Nonnegative Rank-One Approximations of Tensors, Copositivity tests based on the linear complementarity problem, Scaling of symmetric matrices by positive diagonal congruence, Copositive Programming, Optimality conditions for linear copositive programming problems with isolated immobile indices, Finding Extremal Periodic Orbits with Polynomial Optimization, with Application to a Nine-Mode Model of Shear Flow, Effect of Depth and Width on Local Minima in Deep Learning, Machine Learning of Time Series Using Time-Delay Embedding and Precision Annealing, Every Local Minimum Value Is the Global Minimum Value of Induced Model in Nonconvex Machine Learning, GpoSolver: a Matlab/C++ toolbox for global polynomial optimization, Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls, Depth-first simplicial partition for copositivity detection, with an application to MaxClique, On linear conic relaxation of discrete quadratic programs, Bounding Extreme Events in Nonlinear Dynamics Using Convex Optimization, The Computational Complexity of Duality, Unnamed Item, Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems, On LP-based approximation for copositive formulation of stable set problem, Unnamed Item, On Degenerate Doubly Nonnegative Projection Problems, On matrix algebras associated to sum-of-squares semidefinite programs, Distributionally Robust Chance Constrained Geometric Optimization, Local saddle points for unconstrained polynomial optimization, Feature extraction algorithms for constrained global optimization. II: Batch process scheduling application, On standard quadratic programs with exact and inexact doubly nonnegative relaxations, An active-set algorithm for norm constrained quadratic problems, Inverse problems from biomedicine: inference of putative disease mechanisms and robust therapeutic strategies, Criteria for copositive matrices using simplices and barycentric coordinates, A game-theoretic analysis of deep neural networks, On monotonicity and search strategies in face-based copositivity detection algorithms, A branch-and-bound algorithm for bound constrained optimization problems without derivatives, Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives, Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs, On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices, Conic approximation to quadratic optimization with linear complementarity constraints, Embedded variable selection method using signomial classification, Immobile indices and CQ-free optimality criteria for linear copositive programming problems, A survey of hidden convex optimization, Scheduling for a processor sharing system with linear slowdown, A branch-and-reduce approach to global optimization, UTA-poly and UTA-splines: additive value functions with polynomial marginals, A fresh CP look at mixed-binary QPs: new formulations and relaxations, Improved approximation results on standard quartic polynomial optimization, Data science applications to string theory, A new certificate for copositivity, A new approximation hierarchy for polynomial conic optimization, Maximization of homogeneous polynomials over the simplex and the sphere: structure, stability, and generic behavior, On the complexity of detecting convexity over a box, Facets of a mixed-integer bilinear covering set with bounds on variables, A study of piecewise linear-quadratic programs, First-order methods almost always avoid strict saddle points, NP-hardness of deciding convexity of quartic polynomials and related problems, An exact algorithm for graph partitioning, Separation and relaxation for cones of quadratic forms, Hermitian completely positive matrices, Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision, Lower bounds for finding stationary points I, Factorization and cutting planes for completely positive matrices by copositive projection, Unbounded convex sets for non-convex mixed-integer quadratic programming, Open weak CAD and its applications, On the exhaustivity of simplicial partitioning, On the facet defining inequalities of the mixed-integer bilinear covering set, A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints, Testing copositivity via mixed-integer linear programming, Exploiting partial correlations in distributionally robust optimization, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, Globally solving extended trust region subproblems with two intersecting cuts, Two methods for the maximization of homogeneous polynomials over the simplex, Algebra -- 9. Translated from the Russian, A robust unscented transformation for uncertain moments, Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system, The bounds of feasible space on constrained nonconvex quadratic programming, Optimization over structured subsets of positive semidefinite matrices via column generation, Optimality conditions for maximizing a function over a polyhedron, Algorithmic copositivity detection by simplicial partition, Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems, On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems, Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches, A multiple penalty function method for solving max-bisection problems, A simplex algorithm for rational cp-factorization, The extreme rays of the \(6\times 6\) copositive cone, Nonconvex min-max fractional quadratic problems under quadratic constraints: copositive relaxations, On the solution of concave knapsack problems, Minimum concave-cost network flow problems: Applications, complexity, and algorithms, A proximal DC approach for quadratic assignment problem, Polyhedral approximations of the semidefinite cone and their application, Maximizing perturbation radii for robust convex quadratically constrained quadratic programs, Discriminant analysis of distributional data via fractional programming, On types of degenerate critical points of real polynomial functions, A new conic approach to semisupervised support vector machines, Alternative SDP and SOCP approximations for polynomial optimization, On approximation algorithms for concave mixed-integer quadratic programming, Note on combinatorial optimization with max-linear objective functions, The impact of accelerating tools on the interval subdivision algorithm for global optimization, Partially distributed outer approximation, Stability of the linear complementarity problem properties under interval uncertainty, A modified simplex partition algorithm to test copositivity, Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence, A semidefinite relaxation algorithm for checking completely positive separable matrices, Newton polytopes and relative entropy optimization, Quadratic-programming criteria for copositive matrices, A continuous approach to nonlinear integer programming, An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs, Complexity aspects of local minima and related notions, An adaptive high order method for finding third-order critical points of nonconvex optimization, \(Z\)-eigenvalues based structured tensors: \(\mathcal{M}_Z\)-tensors and strong \(\mathcal{M}_Z\)-tensors, Block pivoting and shortcut strategies for detecting copositivity, The copositive completion problem, Sufficient optimality criterion for linearly constrained, separable concave minimization problems, On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint, On the complexity of finding a local minimizer of a quadratic function over a polytope, A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems, Some aspects of studying an optimization or decision problem in different computational models, A new class of improved convex underestimators for twice continuously differentiable constrained NLPs, Feedback control design using sum of squares optimisation, Optimality and stability of symmetric evolutionary games with applications in genetic selection, A game-theoretic perspective of deep neural networks, An efficient PGM-based algorithm with backtracking strategy for solving quadratic optimization problems with spherical constraint, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Speeding up a memetic algorithm for the max-bisection problem, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, Methods for convex and general quadratic programming, Reexamining low rank matrix factorization for trace norm regularization, Optimization and analysis of three-part tariff pricing strategies, Recent Theoretical Advances in Non-Convex Optimization, Signomial and polynomial optimization via relative entropy and partial dualization, Some applications of polynomial optimization in operations research and real-time decision making, A deterministic annealing algorithm for approximating a solution of the min-bisection problem, Conic relaxations for semi-supervised support vector machines, Solution to nonconvex quadratic programming with both inequality and box constraints, Distributionally robust mixed integer linear programs: persistency models with applications, Computing the distance between the linear matrix pencil and the completely positive cone, A branch bound method for subset sum problem, SPN graphs: when copositive = SPN, Copositive programming motivated bounds on the stability and the chromatic numbers, Stochastic nonlinear resource allocation problem, Complexity issues in robust stability of linear delay-differential systems, Checking local optimality in constrained quadratic programming is NP- hard, Toward unified analysis and controller synthesis for a class of hybrid systems, Analytical solutions to general anti-plane shear problems in finite elasticity, Considering manufacturing cost and scheduling performance on a CNC turning machine, An effective iterated tabu search for the maximum bisection problem, On a quadratic programming problem involving distances in trees, Trading performance for stability in Markov decision processes, Constrained optimization with integer and continuous variables using inexact restoration and projected gradients, New reformulations of distributionally robust shortest path problem, LP-based tractable subcones of the semidefinite plus nonnegative cone, Semidefinite programming relaxations for graph coloring and maximal clique problems, Nested nonnegative cone analysis, Testing copositivity with the help of difference-of-convex optimization, Scheduling parallel CNC machines with time/cost trade-off considerations, Distributionally robust chance constrained problem under interval distribution information, Local optimization on graphs, Minimum distance to the complement of a convex set: Duality result, On the complexity of approximating a KKT point of quadratic programming, Copositivity detection of tensors: theory and algorithm, Sparse solutions to random standard quadratic optimization problems, Moment approximations for set-semidefinite polynomials, On computational complexity of invalidating structured uncertainty models, Scaling relationship between the copositive cone and Parrilo's first level approximation, Minimal zeros of copositive matrices, Copositivity and constrained fractional quadratic problems, Extensions of Gauss quadrature via linear programming, Deciding positivity of multisymmetric polynomials, Cardinality constrained portfolio selection problem: a completely positive programming approach, Copositive optimization -- recent developments and applications, A new bound-and-reduce approach of nonconvex quadratic programming problems, Formulas for calculating the extremum ranks and inertias of a four-term quadratic matrix-valued function and their applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, An improved algorithm to test copositivity, Obtaining certificates for complete synchronisation of coupled oscillators, An algorithm for determining copositive matrices, A hybrid branch-and-bound and evolutionary approach for allocating strings of applications to heterogeneous distributed computing systems, Stochastic robustness metric and its use for static resource allocations, Active constraints, indefinite quadratic test problems, and complexity, The extreme rays of the \(5 \times 5\) copositive cone, Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method, On the computational complexity of membership problems for the completely positive cone and its dual, The computational complexity of evolutionarily stable strategies, Quadratic programming with one negative eigenvalue is NP-hard, A FPTAS for computing a symmetric leontief competitive economy equilibrium, Extremal ranks of some nonlinear matrix expressions with applications, qpOASES: a parametric active-set algorithm for~quadratic programming, A unified dissipativity approach for stability analysis of piecewise smooth systems, An analytical approach to global optimization, Local minima for indefinite quadratic knapsack problems, Analysis of copositive optimization based linear programming bounds on standard quadratic optimization, An optimality criterion for global quadratic optimization, On reduced semidefinite programs for second order moment bounds with applications, Satisfactory fault tolerant control with soft-constraint for discrete time-varying systems: numerical recursive approach, Data-driven inverse optimization with imperfect information, Applications of completions of operator matrices to some properties of operator products on Hilbert spaces, On affine scaling algorithms for nonconvex quadratic programming, Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points, Copositive tensor detection and its applications in physics and hypergraphs, Mixed-integer quadratic programming is in NP, Deciding uniqueness in norm maximazation, Approximation algorithms for indefinite quadratic programming, Open questions in complexity theory for numerical optimization, A robust Lagrangian-DNN method for a class of quadratic optimization problems, Algorithms for determining the copositivity of a given symmetric matrix, A new Lagrangian net algorithm for solving max-bisection problems, Optimization and analysis of the profitability of tariff structures with two-part tariffs, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Canonical dual least square method for solving general nonlinear systems of quadratic equations, A convex polynomial that is not sos-convex, Solutions to quadratic minimization problems with box and integer constraints, A direct active set algorithm for large sparse quadratic programs with simple bounds, Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations, An objective general index for multivariate ordered data, Copositive Lyapunov functions for switched systems over cones, Approachability in repeated games: Computational aspects and a Stackelberg variant, Computational complexity of norm-maximization, Efficient heuristics for inventory placement in acyclic networks, On the computation of \(C^*\) certificates, Investigations in topology. 9. Work collection, Conditionally definite matrices, Bitopologies on products and ratios, Interior-point algorithms for global optimization, A new technique for generating quadratic programming test problems, A finite algorithm for solving general quadratic problems, Using copositivity for global optimality criteria in concave quadratic programming problems, Detecting all evolutionarily stable strategies, Role of copositivity in optimality criteria for nonconvex optimization problems, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
Cites Work
