Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProportional-Integral Projected Gradient Method for Conic Optimization
126
0
0.0
(
0
)
Added by
Yue Yu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Conic optimization is the minimization of a differentiable convex objective function subject to conic constraints. We propose a novel primal-dual first-order method for conic optimization, named proportional-integral projected gradient method (PIPG). PIPG ensures that both the primal-dual gap and the constraint violation converge to zero at the rate of (O(1/k)), where (k) is the number of iterations. If the objective function is strongly convex, PIPG improves the convergence rate of the primal-dual gap to (O(1/k^2)). Further, unlike any existing first-order methods, PIPG also improves the convergence rate of the constraint violation to (O(1/k^3)). We demonstrate the application of PIPG in constrained optimal control problems.
rate research
Read More
A constrained optimization problem is primal infeasible if its constraints cannot be satisfied, and dual infeasible if the constraints of its dual problem cannot be satisfied. We propose a novel iterative method, named proportional-integral projected gradient method (PIPG), for detecting primal and dual infeasiblity in convex optimization with quadratic objective function and conic constraints. The iterates of PIPG either asymptotically provide a proof of primal or dual infeasibility, or asymptotically satisfy a set of primal-dual optimality conditions. Unlike existing methods, PIPG does not compute matrix inverse, which makes it better suited for large-scale and real-time applications. We demonstrate the application of PIPG in quasiconvex and mixed-integer optimization using examples in constrained optimal control.
This paper studies the distributed optimization problem where the objective functions might be nondifferentiable and subject to heterogeneous set constraints. Unlike existing subgradient methods, we focus on the case when the exact subgradients of the local objective functions can not be accessed by the agents. To solve this problem, we propose a projected primal-dual dynamics using only the objective functions approximate subgradients. We first prove that the formulated optimization problem can only be solved with an approximate error depending upon the accuracy of the available subgradients. Then, we show the exact solvability of this optimization problem if the accumulated approximation error is not too large. After that, we also give a novel componentwise normalized variant to improve the transient behavior of the convergent sequence. The effectiveness of our algorithms is verified by a numerical example.
In this paper, we propose a relaxation to the stochastic ruler method originally described by Yan and Mukai in 1992 for asymptotically determining the global optima of discrete simulation optimization problems. We show that our proposed variant of the stochastic ruler method provides accelerated convergence to the optimal solution by providing computational results for two example problems, each of which support the better performance of the variant of the stochastic ruler over the original. We then provide the theoretical grounding for the asymptotic convergence in probability of the variant to the global optimal solution under the same set of assumptions as those underlying the original stochastic ruler method.
Distributed optimization is concerned with using local computation and communication to realize a global aim of optimizing the sum of local objective functions. It has gained wide attention for a variety of applications in networked systems. This paper addresses a class of constrained distributed nonconvex optimization problems involving univariate objective functions, aiming to achieve global optimization without requiring local evaluations of gradients at every iteration. We propose a novel algorithm named CPCA, exploiting the notion of combining Chebyshev polynomial approximation, average consensus and polynomial optimization. The proposed algorithm is i) able to obtain $epsilon$ globally optimal solutions for any arbitrarily small given accuracy $epsilon$, ii) efficient in terms of both zeroth-order queries (i.e., evaluations of function values) and inter-agent communication, and iii) distributed terminable when the specified precision requirement is met. The key insight is to use polynomial approximations to substitute for general objective functions, and turn to solve an easier approximate version of the original problem. Due to the nice analytic properties owned by polynomials, this approximation not only facilitates efficient global optimization, but also allows the design of gradient-free iterations to reduce cumulative costs of queries and achieve geometric convergence when nonconvex problems are solved. We provide comprehensive analysis of the accuracy and complexities of the proposed algorithm.
This paper considers the problem of designing accelerated gradient-based algorithms for optimization and saddle-point problems. The class of objective functions is defined by a generalized sector condition. This class of functions contains strongly convex functions with Lipschitz gradients but also non-convex functions, which allows not only to address optimization problems but also saddle-point problems. The proposed design procedure relies on a suitable class of Lyapunov functions and on convex semi-definite programming. The proposed synthesis allows the design of algorithms that reach the performance of state-of-the-art accelerated gradient methods and beyond.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
