In this talk we will present penalty and barrier methods for solving convex second-order cone programming:
`\begin{array}{ccc}
\text{min} & f(x) \\
\text{s.t} & Ax - b \preceq_{\mathcal{K}^n} 0
\end{array}
where `A` is an `n\times m` matrix with `n\geq m`, `\text{rank }A=m`. `f:ℜ^m\to(-\infty,+\infty]` is a closed proper convex function. `\mathcal{K}^n` is a second-order cone (SOC for short) in `ℜ^n` given by
where `\|\cdot\|` denotes the Euclidean norm.
This class of methods is an extension of penalty and barrier methods for convex optimization which was presented by A. Auslender et al. in 1997. With this method, we provide under implementable stopping rule that the sequence generated by the proposed algorithm is bounded and that every accumulation point is a solution to the considered problem. Furthermore, we examine effectiveness of the algorithm by means of numerical experiments.
References
[1] A. Auslender, R. Cominetti and M. Haddou, Asymptotic analysis of penalty and barrier methods in convex and linear programming,
Mathematics of Operations Research, 22, pp. 43-62, 1997.
[2] A. Auslender, Penalty and barrier methods: A unified framework,
SIAM J. Optimization, 10, pp. 211-230, 1999.
[3] A. Auslender, Variational inequalities over the cone of semidefinite positive matrices and over the Lorentz cone,
Optimization methods and software, pp. 359-376, 2003.
[4] A. Auslender and M. Teboulle, Asymptotic cones and functions in optimization and variational inequalities,
Springer monographs in mathematics, Springer, Berlin Heidelberg New York, 2003.
[5] A. Auslender and H. Ramírez C, Penalty and barrier methods for convex semidefinite programming,
Mathematics of Operations Research, 63, pp.195-219, 2006.
[6] M. S. Bazaraa, H. D. Sherali and C. M. Shetty , Nonlinear Programming: Theory and Algorithms, 3rd Edition,
Wiley - Interscience, 2006.
[7] A. Ben-Tal and M. Teboulle, A smoothing technique for nondifferentiable optimization problems, in
Optimization, Fifth French German Conference, Lecture Notes in Math. 1405, Springer-Verlag, New York, pp. 1-11, 1989.
[8] A. Ben-Tal and M. Zibulevsky, Penalty-barrier multiplier methods for convex programming problems,
SIAM J. Optim. Vol 7, No. 2, pp. 347-366, 1997.
[9] J. S. Chen, T. K. Liao and S. Pan, Using Schur complement theorem to prove convexity of some soc-functions,
Journal of Nonlinear and Convex Analysis, Vol 13, No. 3, pp. 421-431, 2012.
[10] C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,
Comput. Optim. Appl, 5, pp. 97-138, 1996.
[11] U. Faraut and A. Koranyi, Anlysis on Symmetric Cones,
Oxford Mathematical Monographs, Oxford University Press, New York, 1994.
[12] E.D. Dolan and J.J. More, Benchmarking optimization software with performance profiles,
Mathematical Programming, vol. 91, pp. 201-213, 2002.
[13] M. Fukushima, Z.-Q. Luo, and P. Tseng, Smoothing functions for second- order-cone complimentarity problems,
SIAM Journal on Optimization, vol. 12, pp. 436-460, 2002.
[14] L. Mosheyev and M. Zibulevsky, Penalty-barrier multiplier algorithm for semidefinite programming,
Optimization Meth. Soft., Vol. 13, pp. 235-261, 2000.
[15] N. Parikh and S. Boyd, Proximal Algorithms,
Foundations and Trends in Optimization, Vol. 1, No. 3, pp. 123-231, 2013.
[16] S. H. Pan and J. S. Chen, A proximal-like algorithnm using quasi D-function for convex second-order cone programming,
J. Optim. Theory Appl., 138 , pp. 95-113, 2008.
[17] S. H Pan and J. S. Chen, A class of interior proximal-like algorithms for convex second-order cone programming,
SIAM J. Optim. Vol. 19, No. 2, pp. 883-910, 2008.
[18] R. T. Rockafellar, Convex Analysis,
Princeton University Press, Princeton, NJ, 1970.
[19] L. Zhang, J. Gu and X. Xiao, A class of nonlinear Lagrangians for nonconvex second order cone programming,
Computational Optimization and Applications. Vol. 49, pp. 61-99, 2011.