×

zbMATH — the first resource for mathematics

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
Software:
QDES; SDPpack; SOCP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, I.; Alizadeh, F., Primal-dual interior point algorithms for convex quadratically constrained and semidefinite optimization problems, ()
[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, () · 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, () · Zbl 1073.90572
[8] Boyd, S.; Barratt, C., Linear controller design: limits of performance, (1991), 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, ()
[11] Buss, M.; Faybusovich, L.; Moore, J.B., Recursive algorithms for real-time grasping force optimization, ()
[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, () · 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, () · 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, () · 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, () · Zbl 0852.68114
[21] Cheney, E.W., Introduction to approximation theory, (1982), 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 Dordrecht · Zbl 0808.90107
[25] Dreyer, D.R.; Overton, M.L., Two heuristics for the Steiner tree problem, () · 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, ()
[30] Lebret, H., Antenna pattern synthesis through convex optimization, (), 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, () · 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. · Zbl 0960.93007
[36] Oppenheim, A.V.; Schafer, R.W., Digital signal processing, (1970), 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, ()
[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, ()
[42] Vanderbei, R.J., Linear programming: foundations and extensions, (1997), 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. · Zbl 0959.90039
[45] Wu, S.-P.; Boyd, S.; Vandenberghe, L., FIR filter design via semidefinite programming and spectral factorization, (), 271-276
[46] Wu, S.-P.; Boyd, S.; Vandenberghe, L., Magnitude filter design via spectral factorization and convex optimization, (), 51-81, Birkhäuser, Basel, 1997
[47] Whittle, P., Optimization under constraints, theory and applications of nonlinear programming, (1971), Wiley/Interscience New York · Zbl 0218.90041
[48] Wright, S.J., Primal-dual interior-point methods, (1997), 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. · Zbl 0885.68074
[50] Ye, Y., An O(n^3L) 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.