Baha Alzalg · 2024
In second-order cone programming (SOCP) problems, we optimize a linear objective function over the intersection of an affine set and the product of second-order cones. Within this chapter, we explore the SOCP problems and their associated interior-point methods, providing a comprehensive understanding of this important class of optimization problems. After studying the algebraic structure of the second-order cone, we delve into the theory and applications of SOCP. Additionally, we shed light on the interior-point methods developed for solving SOCP problems efficiently. The chapter concludes with a set of exercises to encourage readers to apply their knowledge and enrich their understanding.
Cited by 10
Baha Alzalg · Zenodo (CERN European Organization for Nuclear Research) · 2022
In modern convex optimization, the class of optimization that is an immediate enlargement of linear programming is not quadratic programming, but rather the so-called second-order cone programming. Second-order cone programming (SOCP for short) problems, which include linear programming problems and quadratic programming problems as special cases, are a class of convex optimization problems in which the variable is not a vector whose each of its components is required to be nonnegative, but rather a block vector whose each of its subvectors is required to reside in a second-order cone. So in an SOCP problem, we optimize a linear function over the intersection of an affine linear manifold with the Cartesian product of second-order cones. This chapter is devoted to studying SOCP problems.
Cited by 0Open access
Farid Alizadeh, Donald Goldfarb · Mathematical Programming · 2003
Cited by 1,504
Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd et al. · Linear Algebra and its Applications · 1998
Cited by 2,402
Sarah Drewes, Stefan Ulbrich · 2009
This paper deals with solving strategies for mixed integer second order cone problems. We present different lift-and-project based linear and convex quadratic cut generation techniques for mixed 0-1 second-order cone problems and present a new convergent outer approximation based approach to solve mixed integer SOCPs. The latter is an extension of outer approximation based approaches for continuously differ-entiable problems to subdifferentiable second order cone constraint functions. We give numerical results for some application problems, where the cuts are applied in the context of a nonlinear branch-and-cut method and the branch-and-bound based outer approximation algorithm. The different approaches are compared to each other.
Cited by 0
Magnus Åkerblad · 2004
Cited by 0
Yu Xia · International Journal of Operational Research · 2009
We show that the primal and dual 2-dimensional second-order cone programs in standard form are equivalent to the standard-form primal and dual linear programs via a linear transformation. We show how variables in the Second-Order Cone (SOC) programs and the linear programs are related by the transformation. Based on the transformation, we interpret the simplex method for two-dimensional Second-Order Cone Programming (SOCP). We show how pivot steps change the states of variables among interior, boundary, and zero. Finally, we give some applications of two-dimensional SOCP.
Cited by 1
Lieven Vandenberghe, Stephen Boyd · 1997
granted, provided that this entire notice is included in all copies of any software which is or includes a copy or modi cation of this software and in all copies of the supporting documentation for such software. This software is being provided \\as is", without any express or implied warranty. In particular, the authors do not make any representation or warranty of any kind concerning the merchantability of this software or its tness for any particular purpose. 1 1
Cited by 0
A. Antoniou, Wu-Sheng Lu · Texts in computer science · 2021
Cited by 1
Yu Xia, Farid Alizadeh · Computers & Operations Research · 2006
Cited by 8
Baha Alzalg · Applied Mathematical Modelling · 2011
Cited by 23
R. Debnath, H. Takahashi · The 2006 IEEE International Joint Conference on Neural Network Proceedings · 2006
The support vector machine (SVM) problem is a convex quadratic programming problem which scales with the training data size. If the training size is large, the problem cannot be solved by straighforward methods. The large-scale SVM problems are tackled by applying chunking (decomposition) technique. The quadratic programming problem involves a square matrix which is called kernel matrix is positive semi-definite. That is, the rank of the kernel matrix is less than or equal to its size. In this paper we discuss a method that can exploit the low-rank of the kernel matrix, and an interior-point method (IPM) is efficiently applied to the global (large-sized) problem. The method is based on the technique of second-order cone programming (SOCP). This method reformulates the SVM's quadratic programming problem into the second-order cone programming problem. The SOCP method is much faster than efficient softwares SVM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">light</sup> and SVMTorch if the rank of the kernel matrix is small enough compared to the training set size or if the kernel matrix can be approximated by a low-rank positive semidefinite matrix.
Cited by 6
Rameswar Debnath, Haruhisa Takahashi · The 2006 IEEE International Joint Conference on Neural Network Proceedings · 2006
The support vector machine (SVM) problem is a convex quadratic programming problem which scales with the training data size. If the training size is large, the problem cannot be solved by straighforward methods. The large-scale SVM problems are tackled by applying chunking (decomposition) technique. The quadratic programming problem involves a square matrix which is called kernel matrix is positive semi-definite. That is, the rank of the kernel matrix is less than or equal to its size. In this paper we discuss a method that can exploit the low-rank of the kernel matrix, and an interior-point method (IPM) is efficiently applied to the global (large-sized) problem. The method is based on the technique of second-order cone programming (SOCP). This method reformulates the SVM's quadratic programming problem into the second-order cone programming problem. The SOCP method is much faster than efficient softwares SVM <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">light</sup> and SVMTorch if the rank of the kernel matrix is small enough compared to the training set size or if the kernel matrix can be approximated by a low-rank positive semidefinite matrix.
Cited by 11
Roberto Andreani, Ellen H. Fukuda, Gabriel Haeser et al. · Journal of Optimization Theory and Applications · 2023
Cited by 9
Dessy Paramita, Dedi Rosadi · 2013
Optimisasi portofolio merupakan salah satu metode seleksi portofolio yang terkenal dan paling banyak digunakan. Teknik optimisasi portofolio pertama kali dikembangkan oleh Markowitz (1952), yaitu model mean-variance. Walaupun model ini didukung oleh teori yang kuat dan memiliki kemudahan dalam komputasi, mean-variance menunjukkan beberapa kelemahan, salah satunya sangat sensitif terhadap perubahan parameter input. Untuk mengurangi sensitivitas model ini, dikenalkan teknik optimisasi portofolio robust. Dalam optimisasi portofolio robust, parameter inputnya dianggap tidak pasti, dalam hal ini terletak dalam sebuah interval konfidensi yang selanjutnya disebut himpunan ketidakpastian (uncertainty set). Hal ini disebabkan karena pada realita mengestimasi nilai kedua parameter ini tidak mudah, selain itu nilainya selalu berubah setiap saat. Setelah menentukan himpunan ketidakpastian, masalah optimisasi akan diselesaikan untuk kasus terburuk yakni kondisi dengan nilai pengembalian (expected return) portofolio minimum dan risiko portofolio maksimum. Masalah optimisasi dalam analisis portofolio robust ini akan dibawa ke dalam bentuk second-order cone programming (SOCP) yang dapat diselesaikan dengan metode titik interior primal-dual. Studi kasus dilakukan dengan membentuk portofolio yang terdiri dari saham-saham yang terdaftar di Bursa Efek Indonesia, yaitu AALI, ADRO, ASRI, BBRI, CPIN, TLKM dan UNVR, menggunakan teknik SOCP dan mean-variance. Kedua metode ini dibandingkan dengan mengamati kinerja portofolio yang diukur dari tingkat pengembalian (rate of return) portofolio dan nilai indeks Sharpe. Hasilnya, portofolio robust SOCP menunjukkan kinerja yang lebih baik daripada portofolio mean-variance.
Cited by 0
Caturiyati, -, Ch. Rini, Indrati, Lina, Aryati · ePrints - UNY (Yogyakarta State University) · 2012
Pada makalah ini dikembangkan pengertian Second Order Cone (SOC) dan sifat-sifat kendala Second Order Cone Programming dengan Norma 1. \n \nKata kunci: Second Order Cone (SOC), Second Order Cone Programming.
Cited by 0Open access
Jianchao Yao · 2002
The visual motion, induced by ego-motion of the camera, can be estimated through resection, intersection and transfer processes. Under the assumption of affine camera, the intersection/transfer process can be formulated as a system of 5 linear equations, so that any correspondence of an image point and its affine coordinates can be obtained by solving the equations using least squares (LS) techniques. However it produces sometimes a poor estimation result, due to the singularity of the coefficient matrix. In order to solve the problem, instead of trying to find an exact solution of the equations, we tried to obtain a robust least squares (RLS) solution via a second order cone programming technique. The superiority of RLS over LS is demonstrated by the experimental results.
Cited by 2
Ivor W. Tsang, James T. Kwok · IEEE Transactions on Neural Networks · 2006
The kernel function plays a central role in kernel methods. Most existing methods can only adapt the kernel parameters or the kernel matrix based on empirical data. Recently, Ong et al. introduced the method of hyperkernels which can be used to learn the kernel function directly in an inductive setting. However, the associated optimization problem is a semidefinite program (SDP), which is very computationally expensive, even with the recent advances in interior point methods. In this paper, we show that this learning problem can be equivalently reformulated as a second-order cone program (SOCP), which can then be solved more efficiently than SDPs. Comparison is also made with the kernel matrix learning method proposed by Lanckriet et aL Experimental results on both classification and regression problems, with toy and real-world data sets, show that our proposed SOCP formulation has significant speedup over the original SDP formulation. Moreover, it yields better generalization than Lanckriet et al.'s method, with a speed that is comparable, or sometimes even faster, than their quadratically constrained quadratic program (QCQP) formulation.
Cited by 58
Farid Alizadeh, Yu Xia · 2004
Based on the Q method for SDP, we develop the Q method for SOCP. A modified Q method is also introduced. Properties of the algorithms are discussed. Convergence proofs are given. Finally, we present numerical results.
Cited by 0
Raithatha, A, Duncan, SR, Jackson, KP et al. · Cambridge University Engineering Department Publications Database · 2007
Cited by 0