A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
An interior point method is developed for maximizing a concave quadratic function order convex quadratic constraints. The algorithm constructs a sequence of nested convex sets and finds their approximate centers using a partial Newton step. Given the first convex set and its approximate center, the...
| Main Authors: | , |
|---|---|
| Format: | Journal Article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
1991
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/91447 |
| _version_ | 1848765523145261056 |
|---|---|
| author | Mehrotra, S. Sun, Jie |
| author_facet | Mehrotra, S. Sun, Jie |
| author_sort | Mehrotra, S. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | An interior point method is developed for maximizing a concave quadratic function order convex quadratic constraints. The algorithm constructs a sequence of nested convex sets and finds their approximate centers using a partial Newton step. Given the first convex set and its approximate center, the total arithmetic operations required to converge to an approximate solution are of order O(√m(m + n)n2 ln ε), where m is the number of constraints, n is the number of variables, and ε is determined by the desired tolerance of the optimal value and the size of the first convex set. A method to initialize the algorithm is also proposed so that the algorithm can start from an arbitrary (perhaps infeasible) point. |
| first_indexed | 2025-11-14T11:36:36Z |
| format | Journal Article |
| id | curtin-20.500.11937-91447 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T11:36:36Z |
| publishDate | 1991 |
| publisher | Society for Industrial and Applied Mathematics |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-914472023-04-20T05:18:44Z A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs Mehrotra, S. Sun, Jie Science & Technology Physical Sciences Mathematics, Applied Mathematics ANALYTIC CENTER QUADRATIC PROGRAMMING INTERIOR POINT METHODS KARMARKAR ALGORITHM METHOD OF CENTERS POLYNOMIAL-TIME ALGORITHM PRIMAL-DUAL ALGORITHMS An interior point method is developed for maximizing a concave quadratic function order convex quadratic constraints. The algorithm constructs a sequence of nested convex sets and finds their approximate centers using a partial Newton step. Given the first convex set and its approximate center, the total arithmetic operations required to converge to an approximate solution are of order O(√m(m + n)n2 ln ε), where m is the number of constraints, n is the number of variables, and ε is determined by the desired tolerance of the optimal value and the size of the first convex set. A method to initialize the algorithm is also proposed so that the algorithm can start from an arbitrary (perhaps infeasible) point. 1991 Journal Article http://hdl.handle.net/20.500.11937/91447 10.1137/0728029 English Society for Industrial and Applied Mathematics restricted |
| spellingShingle | Science & Technology Physical Sciences Mathematics, Applied Mathematics ANALYTIC CENTER QUADRATIC PROGRAMMING INTERIOR POINT METHODS KARMARKAR ALGORITHM METHOD OF CENTERS POLYNOMIAL-TIME ALGORITHM PRIMAL-DUAL ALGORITHMS Mehrotra, S. Sun, Jie A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs |
| title | A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs |
| title_full | A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs |
| title_fullStr | A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs |
| title_full_unstemmed | A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs |
| title_short | A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs |
| title_sort | method of analytic centers for quadratically constrained convex quadratic programs |
| topic | Science & Technology Physical Sciences Mathematics, Applied Mathematics ANALYTIC CENTER QUADRATIC PROGRAMMING INTERIOR POINT METHODS KARMARKAR ALGORITHM METHOD OF CENTERS POLYNOMIAL-TIME ALGORITHM PRIMAL-DUAL ALGORITHMS |
| url | http://hdl.handle.net/20.500.11937/91447 |