Cones and interior-point algorithms for structured convex optimization involving powers andexponentials
(2009)
Files
thesis.pdf
Open Access - Adobe PDF
- 2.29 MB
Details
- Authors
- Supervisors
- Glineur, François
- Abstract
- (en) Optimization is an important field of applied mathematics with many applications in various domains, ranging from mechanical and electrical engineering to finance and operations research. In particular, convex optimization is very popular because of the availability of highly efficient methods supported by strong theoretical results. In this thesis, we study interior-point methods whose computing time is guaranteed to grow polynomially with the problem dimension. These methods can be applied to any convex problem provided a special function known as a self-concordant barrier is available for the given formulation. We demonstrate in this work that a large class of convex optimization problems are representable in a convex conic form based on the so-called power cone. This very general formulation unifies well-known problem classes such as linear and convex quadratic optimization, but also problem classes such as geometric programming or p-norm location problems. Moreover, we show that the power cone admits a self-concordant barrier with a low parameter, which implies that all problems belonging to the aforementioned class are solvable in polynomial time. Furthermore, recent nonsymmetric primal-dual interior-point methods can be used with that conic formulation. However, in order to formulate a given convex problem in a conic form with power cones, it is often necessary to add auxiliary variables, which increase computing time. In this work, we tackle this drawback with a new framework based on approximate partial minimization. Partial minimization removes the artificially introduced auxiliary variables in order to restore the efficiency of the algorithms. We show that polynomial complexity of standard interior-point methods can be preserved in this framework and demonstrate how it can be applied to concrete problem classes, along with numerical tests that display notable improvements both in terms of the computing time and of the number of iterations.
- Affiliations
Citations
Chares, R. (2009). Cones and interior-point algorithms for structured convex optimization involving powers andexponentials. https://hdl.handle.net/2078.5/128520