Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning a...
详细信息
Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning and robust optimization among others. In this paper, we first present a novel Constraint Extrapolation (ConEx) method for solving convex functional constrained problems, which utilizes linear approximations of the constraint functions to define the extrapolation (or acceleration) step. We show that this method is a unified algorithm that achieves the best-known rate of convergence for solving different functional constrained convex composite problems, including convex or strongly convex, and smooth or nonsmooth problems with stochastic objective and/or stochastic constraints. Many of these rates of convergence were in fact obtained for the first time in the literature. In addition, ConEx is a single-loop algorithm that does not involve any penalty subproblems. Contrary to existing primal-dual methods, it does not require the projection of Lagrangian multipliers into a (possibly unknown) bounded set. Second, for nonconvex functional constrained problems, we introduce a new proximal point method which transforms the initial nonconvex problem into a sequence of convex problems by adding quadratic terms to both the objective and constraints. Under certain MFCQ-type assumption, we establish the convergence and rate of convergence of this method to KKT points when the convex subproblems are solved exactly or inexactly. For large-scale and stochastic problems, we present a more practical proximal point method in which the approximate solutions of the subproblems are computed by the aforementioned ConEx method. Under a strong feasibility assumption, we establish the total iteration complexity of ConEx required by this inexact proximal point method for a variety of problem settings, including nonconvex smooth or nonsmooth problems with stochastic objective and/or
In this paper, we propose a cache-aided non-orthogonal multiple access (NOMA) scheme for spectrally efficient downlink transmission. The proposed scheme not only reaps the benefits associated with NOMA and caching, bu...
详细信息
In this paper, we propose a cache-aided non-orthogonal multiple access (NOMA) scheme for spectrally efficient downlink transmission. The proposed scheme not only reaps the benefits associated with NOMA and caching, but also exploits the data cached at the users for interference cancelation. As a consequence, caching can help to reduce the residual interference power, making multiple decoding orders at the users feasible. The resulting flexibility in decoding can be exploited for improved NOMA detection. We characterize the achievable rate region of cache-aided NOMA and derive the Pareto optimal rate tuples forming the boundary of the rate region. Moreover, we optimize cacheaided NOMA for minimization of the time required for completing file delivery. The optimal decoding order and the optimal transmit power and rate allocation are derived as functions of the cache status, the file sizes, and the channel conditions. Simulation results confirm that, compared to several baseline schemes, the proposed cache-aided NOMA scheme significantly expands the achievable rate region and increases the sum rate for downlink transmission, which translates into substantially reduced file delivery times.
We consider nonmonotone projected gradient methods based on non-Euclidean distances, which play the role of barrier for a given constraint set. Our basic scheme uses the resulting projection-like maps that produces in...
详细信息
We consider nonmonotone projected gradient methods based on non-Euclidean distances, which play the role of barrier for a given constraint set. Our basic scheme uses the resulting projection-like maps that produces interior trajectories, and combines it with the recent nonmonotone line search technique originally proposed for unconstrained problems by Zhang and Hager. The combination of these two ideas leads to produce a nonmonotone scheme for constrained nonconvex problems, which is proven to converge to a stationary point. Some variants of this algorithm that incorporate spectral steplength are also studied and compared with classical nonmonotone schemes based on the usual Euclidean projection. To validate our approach, we report on numerical results solving bound constrained problems from the CUTEr library collection.
The augmented Lagrangian method (ALM) is extended to a broader-than-ever setting of generalized nonlinear programming in convex and nonconvex optimization that is capable of handling many common manifestations of nons...
详细信息
The augmented Lagrangian method (ALM) is extended to a broader-than-ever setting of generalized nonlinear programming in convex and nonconvex optimization that is capable of handling many common manifestations of nonsmoothness. With the help of a recently developed sufficient condition for local optimality, it is shown to be derivable from the proximal point algorithm through a kind of local duality corresponding to an optimal solution and accompanying multiplier vector that furnish a local saddle point of the augmented Lagrangian. This approach leads to surprising insights into stepsize choices and new results on linear convergence that draw on recent advances in convergence properties of the proximal point algorithm. Local linear convergence is shown to be assured for a class of model functions that covers more territory than before.
An extension of the auxiliary problem principle to variational inequalities with non-symmetric multi-valued operators in Hilbert spaces is studied. This extension concerns the case that the operator is split into the ...
详细信息
An extension of the auxiliary problem principle to variational inequalities with non-symmetric multi-valued operators in Hilbert spaces is studied. This extension concerns the case that the operator is split into the sum of a single-valued operator F, possessing a kind of pseudo Dunn property, and a maximal monotone operator Q. The current auxiliary problem is constructed by fixing F at the previous iterate, whereas Q (or its single-valued approximation Q(k)) is considered at a variable point. Using auxiliary operators of the form L-k + chi (k)delh, with chi (k)> 0, the standard for the auxiliary problem principle assumption of the strong convexity of the function h can be weakened exploiting mutual properties of Q and h. Convergence of the general scheme is analyzed and some applications are sketched briefly.
We present a line search multigrid method for solving discretized versions of general unconstrained infinite-dimensional optimization problems. At each iteration on each level, the algorithm computes either a "di...
详细信息
We present a line search multigrid method for solving discretized versions of general unconstrained infinite-dimensional optimization problems. At each iteration on each level, the algorithm computes either a "direct search" direction on the current level or a "recursive search" direction from coarser level models. Introducing a new condition that must be satisfied by a backtracking line search procedure, the "recursive search" direction is guaranteed to be a descent direction. Global convergence is proved under fairly minimal requirements on the minimization method used at all grid levels. Using a limited memory BFGS quasi-Newton method to produce the "direct search" direction, preliminary numerical experiments show that our line search multigrid approach is promising.
We propose a new randomized Bregman (block) coordinate descent (RBCD) method for minimizing a composite problem, where the objective function could be either convex or nonconvex, and the smooth part are freed from the...
详细信息
ISBN:
(纸本)9781728176055
We propose a new randomized Bregman (block) coordinate descent (RBCD) method for minimizing a composite problem, where the objective function could be either convex or nonconvex, and the smooth part are freed from the global Lipschitz-continuous (partial) gradient assumption. Under the notion of relative smoothness based on the Bregman distance, we prove that every limit point of the generated sequence is a stationary point. Further, we show that the iteration complexity of the proposed method is O(n epsilon(-2)) to achieve epsilon-stationary point, where n is the number of blocks of coordinates. If the objective is assumed to be convex, the iteration complexity is improved to O(n epsilon(-1)). If, in addition, the objective is strongly convex (relative to the reference function), the global linear convergence rate is recovered. We also present the accelerated version of the RBCD method, which attains an O(n epsilon(-1/gamma)) iteration complexity for the convex case, where the scalar gamma is an element of [1, 2] is determined by the generalized translation variant of the Bregman distance. Convergence analysis without assuming the global Lipschitz-continuous (partial) gradient sets our results apart from the existing works in the composite problems.
暂无评论