Applications of second-order cone programming. (English) Zbl 0946.90050
Summary: In a Second-Order Cone Program (SOCP) a linear function is minimized over the intersection of an affine set and the product of second-order (quadratic) cones. SOCPs are nonlinear convex problems that include linear and (convex) quadratic programs as special cases, but are less general than SemiDefinite Programs (SDPs). Several efficient primal-dual interior-point methods for SOCP have been developed in the last few years. After reviewing the basic theory of SOCPs, we describe general families of problems that can be recast as SOCPs. These include robust linear programming and robust least-squares problems, problems involving sums or maxima of norms, or with convex hyperbolic constraints. We discuss a variety of engineering applications, such as filter design, antenna array weight design, truss design, and grasping force optimization in robotics. We describe an efficient primal-dual interior-point method for solving SOCPs, which shares many of the features of primal-dual interior-point methods for Linear Programming (LP): Worst-case theoretical analysis shows that the number of iterations required to solve a problem grows at most as the square root of the problem size, while numerical experiments indicate that the typical number of iterations ranges between 5 and 50, almost independent of the problem size.
MSC:
| 90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |
| 90C20 | Quadratic programming |
| 90C90 | Applications of mathematical programming |
| 93B40 | Computational methods in systems theory (MSC2010) |
| 90C51 | Interior-point methods |
Keywords:
convex optimization; quadratic programming; semidefinite programming; interior-point methodsReferences:
| [1] | Adler, I.; Alizadeh, F., Primal-dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems, (Technical Report RRR 46-95, RUT-COR (1995), Rutgers University) |
| [2] | Andersen, E.; Andersen, K., APOS User’s Manual for QCOPT ver 1.00 Beta, EKA consulting (1997) |
| [3] | Achtziger, W.; Bendsoe, M.; Ben-Tal, A.; Zowe, J., Equivalent displacement based formulations for maximum strength truss topology design, Impact of Computing in Science and Engineering, 4, 4, 315-345 (1992) · Zbl 0769.73054 |
| [4] | Andersen, K.; Christiansen, E.; Overton, M., Computing limits loads by minimizing a sum of norms, (Technical Report 30 (1994), Institut for Matematik og Datalogi, Odense Universitet) · Zbl 0924.73074 |
| [5] | Alizadeh, F.; Haeberly, J. P.; Nayakkankuppam, M. V.; Overton, M. L., SDPPACK User’s Guide, version 0.8 Beta (1997), NYU |
| [6] | Andersen, K., An efficient Newton barrier method for minimizing a sum of Euclidean norms, SIAM Journal on Optimization, 6, 1, 74-95 (1996) · Zbl 0842.90105 |
| [7] | Alizadeh, F.; Schmieta, S. H., Optimization with semidefinite, quadratic and linear constraints, (Technical Report (1997), RUTCOR, Rutgers University) · Zbl 1073.90572 |
| [8] | Boyd, S.; Barratt, C., Linear Controller Design: Limits of Performance (1991), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0748.93003 |
| [9] | Bendsoe, M.; Ben-Tal, A.; Zowe, J., Optimization methods for truss geometry and topology design, Structural Optimization, 7, 141-159 (1994) |
| [10] | Boyd, S.; Crusius, C.; Hansson, A., Control applications of nonlinear convex programming, Process Control, 1997, (Special issue for papers presented at the 1997 IFAC Conference on Advanced Process Control. Special issue for papers presented at the 1997 IFAC Conference on Advanced Process Control, Banff (1997)) |
| [11] | Buss, M.; Faybusovich, L.; Moore, J. B., Recursive algorithms for real-time grasping force optimization, (Proceedings of International Conference on Robotics and Automation. Proceedings of International Conference on Robotics and Automation, Albuquerque, NM, USA (1997)) |
| [12] | Buss, M.; Hashimoto, H.; Moore, J. B., Dextrous hand grasping force optimization, IEEE Transactions on Robotics and Automation, 12, 3, 406-418 (1996) |
| [13] | Ben-Tal, A.; Bendsøe, M. P., A new method for optimal truss topology design, SIAM Journal on Optimization, 3, 322-358 (1993) · Zbl 0780.90076 |
| [14] | Ben-Tal, A.; Nemirovskii, A., Interior point polynomial-time method for truss topology design, (Technical Report (1992), Faculty of Industrial Engineering and Management, Technion Institute of Technology: Faculty of Industrial Engineering and Management, Technion Institute of Technology Haifa, Israel) · Zbl 0821.90137 |
| [15] | Ben-Tal, A.; Nemirovski, A., Optimal design of engineering structures, Optima, 4-9 (1995) |
| [16] | Ben-Tal, A.; Nemirovski, A., Robust convex optimization, (Technical Report (1996), Faculty of Industrial Engineering and Management, Technion) · Zbl 0977.90052 |
| [17] | Boyd, S.; Vandenberghe, L., Introduction to convex optimization with engineering applications, Course Notes (1997) |
| [18] | Chandrasekaran, S.; Golub, G. H.; Gu, M.; Sayed, A. H., Efficient algorithms for least square type problems with bounded uncertainties, (Technical Report, SCCM-96-16 (1996), Stanford University) · Zbl 0957.65070 |
| [19] | Chandrasekaran, S.; Golub, G. H.; Gu, M.; Sayed, A. H., Parameter estimation in the presence of bounded data uncertainties, SIAM Journal on Matrix Analysis and Applications, 19, 1, 235-252 (1998) · Zbl 0914.65147 |
| [20] | Chan, T. F.; Golub, G. H.; Mulet, P., A nonlinear primal-dual method for total variation-based image restoration, (Technical Report, SCCM-95-10 (1995), Stanford University, Computer Science Department) · Zbl 0852.68114 |
| [21] | Cheney, E. W., Introduction to Approximation Theory (1982), Chelsea: Chelsea New York · Zbl 0535.41001 |
| [22] | Cheng, F.-T.; Orin, D. E., Efficient algorithm for optimal force distribution - the compact-dual LP method, IEEE Transactions on Robotics and Automation, 6, 2, 178-187 (1990) |
| [23] | Conn, A. R.; Overton, M. L., Primal-dual interior-point method for minimizing a sum of Euclidean distances (1994), Draft |
| [24] | den Hertog, D., Interior Point Approach to Linear, Quadratic and Convex Programming (1993), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0808.90107 |
| [25] | Dreyer, D. R.; Overton, M. L., Two heuristics for the Steiner tree problem, (Technical Report, 724 (1996), New York University Computer Science Department) · Zbl 0909.90199 |
| [26] | El Ghaoui, L.; Lebret, H., Robust solutions to least-squares problems with uncertain data, SIAM Journal on Matrix Analysis and Applications, 18, 4, 1035-1064 (1997) · Zbl 0891.65039 |
| [27] | Goldfarb, D.; Liu, S.; Wang, S., A logarithmic barrier function algorithm for convex quadratically constrained quadratic programming, SIAM Journal on Optimization, 1, 252-267 (1991) · Zbl 0754.90044 |
| [28] | Lebret, H.; Boyd, S., Antenna array pattern synthesis via convex optimization, IEEE Transactions on Signal Processing, 45, 3, 526-532 (1997) |
| [29] | Lebret, H., Synthèse de diagrammes de réseaux d’antennes par optimisation convexe, (Ph.D. Thesis (1994), Université de Rennes I) |
| [30] | Lebret, H., Antenna pattern synthesis through convex optimization, (Luk, Franklin T., Proceedings of the SPIE Advanced Signal Processing Algorithms (1995)), 182-192 |
| [31] | Lobo, M. S.; Vandenberghe, L.; Boyd, S., SOCP: Software for second-order cone programming (1997), Information Systems Laboratory, Stanford University |
| [32] | Nesterov, Yu.; Nemirovsky, A., Interior-point polynomial methods in convex programming, (Studies in Applied Mathematics, vol. 13 (1994), SIAM: SIAM Philadelphia) · Zbl 0754.90042 |
| [33] | Nemirovskii, A.; Scheinberg, K., Extension of Karmarkar’s algorithm onto convex quadratically constrained quadratic problems, Mathematical Programming, 72, 3, 273-289 (1996), (Ser. A) · Zbl 0853.90092 |
| [34] | Nesterov, Yu. E.; Todd, M. J., Self-scaled cones and interior-point methods for convex programming, Mathematics of Operations Research, 22, 1-42 (1997) · Zbl 0871.90064 |
| [35] | F. Oustry, L. El Ghaoui, H. Lebret, Robust solutions to uncertain semidefinite programs, SIAM Journal on Optimization, to appear.; F. Oustry, L. El Ghaoui, H. Lebret, Robust solutions to uncertain semidefinite programs, SIAM Journal on Optimization, to appear. · Zbl 0960.93007 |
| [36] | Oppenheim, A. V.; Schafer, R. W., Digital Signal Processing (1970), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [37] | Patel, M. H., Spherical minimax location problem using the Euclidean norm: formulation and optimization, Computational Optimization and Applications, 4, 79-90 (1995) · Zbl 0820.90063 |
| [38] | Potchinkov, A. W.; Reemtsen, R. M., The design of FIR filters in the complex plane by convex optimization, Signal Processing, 46, 2, 127-146 (1995) · Zbl 0875.93531 |
| [39] | Sayed, A. H.; Garulli, A.; Nascimento, V. H.; Chandrasekaran, S., Exponentially-weighted iterative solutions for worst-case parameter estimation, (Proceedings of the Fifth IEEE Med. Conference on Control and Systems. Proceedings of the Fifth IEEE Med. Conference on Control and Systems, Cyprus (1997)) |
| [40] | Southall, H.; Simmers, J.; O’Donnell, T., Direction finding in phased arrays with a neural network beamformer, IEEE Transactions on Antennas and Propagation, 43, 12, 1369-1374 (1995) |
| [41] | Tsuchiya, T., A polynomial primal-dual path-following algorithm for second-order cone programming, (Technical Report (1997), The Institute of Statistical Mathematics: The Institute of Statistical Mathematics Tokyo, Japan) |
| [42] | Vanderbei, R. J., Linear Programming: Foundations and Extensions (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht |
| [43] | Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Review, 38, 1, 49-95 (1996) · Zbl 0845.65023 |
| [44] | L. Vandenberghe, S. Boyd, S.-P. Wu, Determinant maximization with linear matrix inequality constraints, SIAM Journal on Matrix Analysis and Applications, to appear.; L. Vandenberghe, S. Boyd, S.-P. Wu, Determinant maximization with linear matrix inequality constraints, SIAM Journal on Matrix Analysis and Applications, to appear. · Zbl 0959.90039 |
| [45] | Wu, S.-P.; Boyd, S.; Vandenberghe, L., FIR filter design via semidefinite programming and spectral factorization, (Proceedings IEEE Conferance on Decision and Control (1996)), 271-276 |
| [46] | Wu, S.-P.; Boyd, S.; Vandenberghe, L., Magnitude filter design via spectral factorization and convex optimization, (Datta, B., Applied and Computational Control, Signals and Circuits (1997)), 51-81, Birkhäuser, Basel, 1997 |
| [47] | Whittle, P., Optimization under Constraints, Theory and Applications of Nonlinear Programming (1971), Wiley/Interscience: Wiley/Interscience New York · Zbl 0218.90041 |
| [48] | Wright, S. J., Primal-Dual Interior-Point Methods (1997), SIAM: SIAM Philadelphia · Zbl 0863.65031 |
| [49] | G. Xue, Y. Ye, An efficient algorithm for minimizing a sum of Euclidean norms with applications, SIAM Journal on Optimization, to appear.; G. Xue, Y. Ye, An efficient algorithm for minimizing a sum of Euclidean norms with applications, SIAM Journal on Optimization, to appear. · Zbl 0885.68074 |
| [50] | Ye, Y., An \(O(n^3\) L) potential reduction algorithm for linear programming, Mathematical Programming, 50, 239-258 (1991) · Zbl 0734.90057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
