Hiriart-Urruty gave formulas of the first-order and second-order ε-directional derivatives of a marginal function for a convex programming problem with linear equality constraints, that is, the image of a function un...
详细信息
Hiriart-Urruty gave formulas of the first-order and second-order ε-directional derivatives of a marginal function for a convex programming problem with linear equality constraints, that is, the image of a function under linear mapping (Ref. 1). In this paper, we extend his results to a problem with linear inequality constraints. The formula of the first-order derivative is given with the help of a duality theorem. A lower estimate for the second-order ε-directional derivative is given.
In this paper the relationships between various constraint qualifications for infinite-dimensional convex programs are investigated. Using Robinson’s refinement of the duality result of Rockafellar, it is demonstrate...
详细信息
In this paper the relationships between various constraint qualifications for infinite-dimensional convex programs are investigated. Using Robinson’s refinement of the duality result of Rockafellar, it is demonstrated that the constraint qualification proposed by Rockafellar provides a systematic mechanism for comparing many constraint qualifications as well as establishing new results in different topological environments.
This paper presents new versions of proximal bundle methods for solving convex constrained nondifferentiable minimization problems. The methods employ l1 or l infinity exact penalty functions with new penalty updates ...
详细信息
This paper presents new versions of proximal bundle methods for solving convex constrained nondifferentiable minimization problems. The methods employ l1 or l infinity exact penalty functions with new penalty updates that limit unnecessary penalty growth. In contrast to other methods, some of them are insensitive to problem function scaling. Global convergence of the methods is established, as well as finite termination for polyhedral problems. Some encouraging numerical experience is reported. The ideas presented may also be used in variable metric methods for smooth nonlinear programming.
作者：
TSENG, PMIT
CTR INTELLIGENT CONTROL SYSTCAMBRIDGEMA 02139 MIT
INFORMAT & DECIS SYST LABCAMBRIDGEMA 02139
In this paper, we propose a decomposition algorithm for convex differentiable minimization. This algorithm at each iteration solves a variational inequality problem obtained by adding to the gradient of the cost funct...
详细信息
In this paper, we propose a decomposition algorithm for convex differentiable minimization. This algorithm at each iteration solves a variational inequality problem obtained by adding to the gradient of the cost function a strongly proximal related function. A line search is then performed in the direction of the solution to this variational inequality (with respect to the original cost). If the constraint set is a Cartesian product of m sets, the variational inequality decomposes into m coupled variational inequalities, which can be solved in either a Jacobi manner or a Gauss-Seidel manner. This algorithm also applies to the minimization of a strongly convex (possibly nondifferentiable) cost subject to linear constraints. As special cases, we obtain the GP-SOR algorithm of Mangasarian and De Leone, a diagonalization algorithm of Feijoo and Meyer, the coordinate descent method, and the dual gradient method. This algorithm is also closely related to a splitting algorithm of Gabay and a gradient projection algorithm of Goldstein and of Levitin-Poljak, and has interesting applications to separable convex programming and to solving traffic assignment problems.
This paper considers the minimization of a convex integral functional over the positive cone of an L(p) space, subject to a finite number of linear equality constraints. Such problems arise in spectral estimation, whe...
详细信息
This paper considers the minimization of a convex integral functional over the positive cone of an L(p) space, subject to a finite number of linear equality constraints. Such problems arise in spectral estimation, where the objective function is often entropy-like, and in constrained approximation. The Lagrangian dual problem is finite-dimensional and unconstrained. Under a quasi-interior constraint qualification, the primal and dual values are equal, with dual attainment. Examples show the primal value may not be attained. Conditions are given that ensure that the primal optimal solution can be calculated directly from a dual optimum. These conditions are satisfied in many examples.
The proximal point algorithm (PPA) for the convex minimization problem min(x-epsilon-H)f(x), where f:H --> R union of {infinity} is a proper, lower semicontinuous (lsc) function in a Hilbert space H is considered. ...
详细信息
The proximal point algorithm (PPA) for the convex minimization problem min(x-epsilon-H)f(x), where f:H --> R union of {infinity} is a proper, lower semicontinuous (lsc) function in a Hilbert space H is considered. Under this minimal assumption on f, it is proved that the PPA, with positive parameters {lambda-k} k = 1, infinity converges in general if and only if sigma-n = SIGMA-k = 1n-lambda-k --> infinity. Global convergence rate estimates for the residual f(X)(n) - f(u), where x(n) is the nth iterate of the PPA and u-epsilon-H is arbitrary are given. An open question of Rockafellar is settled by giving an example of a PPA for which x(n) converges weakly but not strongly to a minimizer of f.
The problem of stabilizing linear systems subject to possibly fast time varying uncertainties is investigated. Necessary and sufficient conditions of quadratic stabilizability are discussed. The design process is form...
详细信息
The problem of stabilizing linear systems subject to possibly fast time varying uncertainties is investigated. Necessary and sufficient conditions of quadratic stabilizability are discussed. The design process is formulated as a two level optimization process, which can be simplified if the uncertainty is bounded by a hyperpolyhedron.
In this paper we present two new algorithms for maximizing a separable concave function on a polymatroid. Both algorithms apply to the discrete as well as the continuous version of the problem. The application of thes...
详细信息
In this paper we present two new algorithms for maximizing a separable concave function on a polymatroid. Both algorithms apply to the discrete as well as the continuous version of the problem. The application of these algorithms to several types of polymatroids is discussed, and we show that the Decomposition Algorithm runs in polynomial time (in the discrete version) for network and generalized symmetric polymatroids, and the Bottom Up Algorithm (in the discrete version) runs in polynomial time when the polymatroid is given as an explicit list of constraints.
A proximal bundle method is given for minimizing a convex function f. It accumulates so-called tilted cutting planes in polyhedral approximations to f that introduce some second-order information and interior point fe...
详细信息
A proximal bundle method is given for minimizing a convex function f. It accumulates so-called tilted cutting planes in polyhedral approximations to f that introduce some second-order information and interior point features absent in usual methods. Global convergence of the method is proved.
In their seminal papers Eremin [Soviet Mathematics Doklady, 8 1966), pp. 459-462] and Zangwill [Management Science, 13 (1967), pp. 344-358] introduce a notion of exact penalization for use in the development of algori...
详细信息
In their seminal papers Eremin [Soviet Mathematics Doklady, 8 1966), pp. 459-462] and Zangwill [Management Science, 13 (1967), pp. 344-358] introduce a notion of exact penalization for use in the development of algorithms for constrained optimization. Since that time, exact penalty functions have continued to play a key role in the theory of mathematical programming. In the present paper, this theory is unified by showing how the Eremin-Zangwill exact penalty functions can be used to develop the foundations of the theory of constrained optimization for finite dimensions in an elementary and straightforward way. Regularity conditions, multiplier rules, second-order optimality conditions, and convex programming are all given interpretations relative to the Eremin-Zangwill exact penalty functions. In conclusion, a historical review of those results associated with the existence of an exact penalty parameter is provided.
暂无评论