Ускоренные безградиентные методы оптимизации с неевклидовым проксимальным оператором
This paper proposes an approach to obtaining of the set of admissible values of the optimization variables (design space) in the form of extreme ellipsoids describing a given set of points and inscribed in a given set of linear constraints. Considered ellipsoids include Principal Component’s ellipsoid, minimal volume ellipsoid and ellipsoid with minimal trace of its matrix containing given points. We have developed the procedures which change ellipsoid built based on points set exclusively in order to inscribe it into polyhedron. Ellipsoids are constructed by solving corresponding optimization problems which are formulated as convex programming problems using linear matrix inequalities.
The mixed-norm cost functions arise in many applied optimization problems. As an important example, we consider the state estimation problem for a linear dynamic system under a nonclassical assumption that some entries of state vector admit jumps in their trajectories. The estimation problem is solved by means of mixed l1/l2-norm approximation. This approach combines the advantages of the well-known quadratic smoothing and the robustness of the least absolute deviations method. For the implementation of the mixed-norm approximation, a dynamic iterative estimation algorithm is proposed. This algorithm is based on weight and time recursions and demonstrates the high efficiency. It well identifies the rare jumps in the state vector and has some advantages over more customary methods in case of a large amount of measurements that are typical for applied problems. Nonoptimality levels for current iterations of the algorithm are constructed. The computation of these levels allows to check the accuracy of iterations.
In this paper, we consider a large class of hierarchical congestion population games. One can show that the equilibrium in a game of such type can be described as a minimum point in a properly constructed multi-level convex optimization problem. We propose a fast primal-dual composite gradient method and apply it to the problem, which is dual to the problem describing the equilibrium in the considered class of games. We prove that this method allows to find an approximate solution of the initial problem without increasing the complexity.