共查询到20条相似文献,搜索用时 0 毫秒
1.
Piecewise affine functions arise from Lagrangian duals of integer programming problems, and optimizing them provides good
bounds for use in a branch and bound method. Methods such as the subgradient method and bundle methods assume only one subgradient
is available at each point, but in many situations there is more information available. We present a new method for optimizing
such functions, which is related to steepest descent, but uses an outer approximation to the subdifferential to avoid some
of the numerical problems with the steepest descent approach. We provide convergence results for a class of outer approximations,
and then develop a practical algorithm using such an approximation for the compact dual to the linear programming relaxation
of the uncapacitated facility location problem. We make a numerical comparison of our outer approximation method with the
projection method of Conn and Cornuéjols, and the bundle method of Schramm and Zowe.
Received September 10, 1998 / Revised version received August 1999?Published online December 15, 1999 相似文献
2.
We show that a locally Lipschitz homeomorphism function is semismooth at a given point if and only if its inverse function
is semismooth at its image point. We present a sufficient condition for the semismoothness of solutions to generalized equations
over cone reducible (nonpolyhedral) convex sets. We prove that the semismoothness of solutions to the Moreau-Yosida regularization
of a lower semicontinuous proper convex function is implied by the semismoothness of the metric projector over the epigraph
of the convex function.
This paper is dedicated to Terry Rockafellar on the occasion of his seventieth birthday 相似文献
3.
对分片 C2凸函数的 Moreau-Yosida逼近研究了它的梯度性质,引进了序列常秩约束条件,在此条件下证明了梯度函数具有分片光滑性质. 相似文献
4.
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints 总被引:12,自引:0,他引:12
Le Thi Hoai An 《Mathematical Programming》2000,87(3):401-426
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids.
The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the
proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound
scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham
Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting
point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order
to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the
ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can
be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting
procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems.
Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA
and the combined DCA-branch-and-bound algorithm.
Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000 相似文献
5.
J. Sun 《Journal of Optimization Theory and Applications》1992,72(3):499-510
Convex piecewise quadratic functions (CPQF) play an important role in mathematical programming, and yet their structure has not been fully studied. In this paper, these functions are categorized into difference-definite and difference-indefinite types. We show that, for either type, the expressions of a CPQF on neighboring polyhedra in its domain can differ only by a quadratic function related to the common boundary of the polyhedra. Specifically, we prove that the monitoring function in extended linear-quadratic programming is difference-definite. We then study the case where the domain of the difference-definite CPQF is a union of boxes, which arises in many applications. We prove that any such function must be a sum of a convex quadratic function and a separable CPQF. Hence, their minimization problems can be reformulated as monotropic piecewise quadratic programs.This research was supported by Grant DDM-87-21709 of the National Science Foundation. 相似文献
6.
Krzysztof C. Kiwiel 《Mathematical Programming》1999,85(2):241-258
k } by taking xk to be an approximate minimizer of , where is a piecewise linear model of f constructed from accumulated subgradient linearizations of f, Dh is the D-function of a generalized Bregman function h and tk>0. Convergence under implementable criteria is established by extending our recent framework of Bregman proximal minimization, which is of independent interest, e.g., for nonquadratic multiplier methods for constrained minimization. In particular, we provide new insights into the convergence properties of bundle methods based on h=?|·|2. Received September 18, 1997 / Revised version received June 30, 1998 Published online November 24, 1998 相似文献
7.
Logarithmic SUMT limits in convex programming 总被引:1,自引:1,他引:0
The limits of a class of primal and dual solution trajectories associated with the Sequential Unconstrained Minimization Technique
(SUMT) are investigated for convex programming problems with non-unique optima. Logarithmic barrier terms are assumed. For
linear programming problems, such limits – of both primal and dual trajectories – are strongly optimal, strictly complementary,
and can be characterized as analytic centers of, loosely speaking, optimality regions. Examples are given, which show that
those results do not hold in general for convex programming problems. If the latter are weakly analytic (Bank et al. [3]),
primal trajectory limits can be characterized in analogy to the linear programming case and without assuming differentiability.
That class of programming problems contains faithfully convex, linear, and convex quadratic programming problems as strict
subsets. In the differential case, dual trajectory limits can be characterized similarly, albeit under different conditions,
one of which suffices for strict complementarity.
Received: November 13, 1997 / Accepted: February 17, 1999?Published online February 22, 2001 相似文献
8.
We prove that strict complementarity, primal and dual nondegeneracy of optimal solutions of convex optimization problems in
conic form are generic properties. In this paper, we say generic to mean that the set of data possessing the desired property
(or properties) has strictly larger Hausdorff dimension than the set of data that does not. Our proof is elementary and it
employs an important result due to Larman [7] on the boundary structure of convex bodies.
Received: September 1997 / Accepted: May 2000?Published online November 17, 2000 相似文献
9.
The local quadratic convergence of the Gauss-Newton method for convex composite optimization f=h∘F is established for any convex function h with the minima set C, extending Burke and Ferris’ results in the case when C is a set of weak sharp minima for h.
Received: July 24, 1998 / Accepted: November 29, 2000?Published online September 3, 2001 相似文献
10.
1 , the smallest eigenvalue of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The
paper describes the algorithm and its implementation including estimation of λ1, how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive
testing and comparison with other methods for constrained QP are given.
Received May 1, 1997 / Revised version received March 17, 1998 Published online November 24, 1998 相似文献
11.
Nonlinear programming without a penalty function 总被引:57,自引:0,他引:57
In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm
is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead,
a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or
the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm
compares favourably with LANCELOT and an implementation of Sl1QP.
Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001 相似文献
12.
Roman A. Polyak 《Mathematical Programming》2002,92(2):197-235
We introduce an alternative to the smoothing technique approach for constrained optimization. As it turns out for any given
smoothing function there exists a modification with particular properties. We use the modification for Nonlinear Rescaling
(NR) the constraints of a given constrained optimization problem into an equivalent set of constraints.?The constraints transformation
is scaled by a vector of positive parameters. The Lagrangian for the equivalent problems is to the correspondent Smoothing
Penalty functions as Augmented Lagrangian to the Classical Penalty function or MBFs to the Barrier Functions. Moreover the
Lagrangians for the equivalent problems combine the best properties of Quadratic and Nonquadratic Augmented Lagrangians and
at the same time are free from their main drawbacks.?Sequential unconstrained minimization of the Lagrangian for the equivalent
problem in primal space followed by both Lagrange multipliers and scaling parameters update leads to a new class of NR multipliers
methods, which are equivalent to the Interior Quadratic Prox methods for the dual problem.?We proved convergence and estimate
the rate of convergence of the NR multipliers method under very mild assumptions on the input data. We also estimate the rate
of convergence under various assumptions on the input data.?In particular, under the standard second order optimality conditions
the NR method converges with Q-linear rate without unbounded increase of the scaling parameters, which correspond to the active
constraints.?We also established global quadratic convergence of the NR methods for Linear Programming with unique dual solution.?We
provide numerical results, which strongly support the theory.
Received: September 2000 / Accepted: October 2001?Published online April 12, 2002 相似文献
13.
Stephen M. Robinson 《Mathematical Programming》1999,86(1):41-50
This paper establishes a linear convergence rate for a class of epsilon-subgradient descent methods for minimizing certain
convex functions on ℝ
n
. Currently prominent methods belonging to this class include the resolvent (proximal point) method and the bundle method
in proximal form (considered as a sequence of serious steps). Other methods, such as a variant of the proximal point method
given by Correa and Lemaréchal, can also fit within this framework, depending on how they are implemented. The convex functions
covered by the analysis are those whose conjugates have subdifferentials that are locally upper Lipschitzian at the origin,
a property generalizing classical regularity conditions.
Received March 29, 1996 / Revised version received March 5, 1999? Published online June 11, 1999 相似文献
14.
Manuel A. Nunez 《Mathematical Programming》2002,91(2):375-390
Given a data instance of a convex program, we provide a collection of conic linear systems such that the data instance is
ill-posed if and only if at least one of those systems is satisfied. This collection of conic linear systems is derived from
a characterization of the boundary of the set of primal and dual feasible data instances associated with the given convex
program.
Received: September 1998 / Accepted: August 2000?Published online October 26, 2001 相似文献
15.
The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular
function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions
and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set
functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions
and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems
that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis.
Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000 相似文献
16.
We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound
uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known
projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and
computational effort.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 相似文献
17.
Stephen J. Wright 《Mathematical Programming》2001,90(3):459-473
Techniques for transforming convex quadratic programs (QPs) into monotone linear complementarity problems (LCPs) and vice
versa are well known. We describe a class of LCPs for which a reduced QP formulation – one that has fewer constraints than
the “standard” QP formulation – is available. We mention several instances of this class, including the known case in which
the coefficient matrix in the LCP is symmetric.
Received: May 2000 / Accepted: February 22, 2001?Published online April 12, 2001 相似文献
18.
R. S. Yulmukhametov 《Mathematical Notes》1997,62(2):260-267
We consider the problem of approximating a given plurisubharmonic function by smooth plurisubharmonic functions. We propose
a new constructive approximation method that permits one to obtain more detailed information about the approximating functions.
Thus a functionu ∈ PSH(ℂ
n
) having finite growth order can be approximated by smooth functionsv ∈ PSH(ℂ
n
) so that the difference |v−u| has almost logarithmic growth (Theorem 2). It can also be approximated so that the difference |v−u| has a power-law growth; in this case, however, power-law estimates on |gradv| appear (Theorem 3).
Translated fromMatematicheskie Zametki, Vol. 62, No. 2, pp. 312–320, August, 1997.
Translated by I. P. Zvyagin 相似文献
19.
Entropic proximal decomposition methods for convex programs and variational inequalities 总被引:2,自引:0,他引:2
We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition
method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a
decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to
produce for the first time provably convergent decomposition schemes based on C
∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty
solution sets, global convergence of the primal-dual sequences produced by the algorithm is established.
Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001 相似文献
20.
Andrzej Cegielski 《Mathematical Programming》1999,85(3):469-490
Received November 11, 1995 / Revised version received June 2, 1998 Published online March 16, 1999 相似文献