共查询到20条相似文献,搜索用时 31 毫秒
1.
Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods 总被引:6,自引:0,他引:6
The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The
specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization
of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic
programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that
a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance.
Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000 相似文献
2.
A. Auslender 《Mathematical Programming》2000,88(1):45-59
In this paper we consider an ordinary convex program with no qualification conditions (such as Slater’s condition) and for
which the optimal set is neither required to be compact, nor to be equal to the sum of a compact set and a linear space. It
is supposed only that the infimum α is finite. A very wide class of convex functions is exhibited for which the optimum is
always attained and α is equal to the supremum of the ordinary dual program. Additional results concerning the existence of
optimal solutions in the non convex case are also given.
Received: February 1, 1999 / Accepted: December 15, 1999?Published online February 23, 2000 相似文献
3.
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 相似文献
4.
Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems 总被引:3,自引:0,他引:3
ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρf is a feasibility measure.
We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility
(primal or dual) can be detected in O(ln) iterations, where ρ· is a primal or dual infeasibility measure.
Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998 相似文献
5.
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 相似文献
6.
Lagrangean dualization and subgradient optimization techniques are frequently used within the field of computational optimization
for finding approximate solutions to large, structured optimization problems. The dual subgradient scheme does not automatically
produce primal feasible solutions; there is an abundance of techniques for computing such solutions (via penalty functions,
tangential approximation schemes, or the solution of auxiliary primal programs), all of which require a fair amount of computational
effort.
We consider a subgradient optimization scheme applied to a Lagrangean dual formulation of a convex program, and construct,
at minor cost, an ergodic sequence of subproblem solutions which converges to the primal solution set. Numerical experiments
performed on a traffic equilibrium assignment problem under road pricing show that the computation of the ergodic sequence
results in a considerable improvement in the quality of the primal solutions obtained, compared to those generated in the
basic subgradient scheme.
Received February 11, 1997 / Revised version received June 19, 1998?Published online June 28, 1999 相似文献
7.
In this paper, we analyse three interior point continuous trajectories for convex programming with general linear constraints. The three continuous trajectories are derived from the primal–dual path-following method, the primal–dual affine scaling method and the central path, respectively. Theoretical properties of the three interior point continuous trajectories are fully studied. The optimality and convergence of all three interior point continuous trajectories are obtained for any interior feasible point under some mild conditions. In particular, with proper choice of some parameters, the convergence for all three interior point continuous trajectories does not require the strict complementarity or the analyticity of the objective function. These results are new in the literature. 相似文献
8.
Smooth methods of multipliers for complementarity problems 总被引:2,自引:0,他引:2
This paper describes several methods for solving nonlinear complementarity problems. A general duality framework for pairs
of monotone operators is developed and then applied to the monotone complementarity problem, obtaining primal, dual, and primal-dual
formulations. We derive Bregman-function-based generalized proximal algorithms for each of these formulations, generating
three classes of complementarity algorithms. The primal class is well-known. The dual class is new and constitutes a general
collection of methods of multipliers, or augmented Lagrangian methods, for complementarity problems. In a special case, it
corresponds to a class of variational inequality algorithms proposed by Gabay. By appropriate choice of Bregman function,
the augmented Lagrangian subproblem in these methods can be made continuously differentiable. The primal-dual class of methods
is entirely new and combines the best theoretical features of the primal and dual methods. Some preliminary computation shows
that this class of algorithms is effective at solving many of the standard complementarity test problems.
Received February 21, 1997 / Revised version received December 11, 1998? Published online May 12, 1999 相似文献
9.
Chek Beng Chua 《Mathematical Programming》2008,115(2):239-271
The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming
is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central
paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary
solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central
path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the
additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual
solutions to converge linearly with their duality gaps.
This research was supported by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from
NSERC. 相似文献
10.
On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating 总被引:2,自引:0,他引:2
In previous work, the authors provided a foundation for the theory of variable metric proximal point algorithms in Hilbert
space. In that work conditions are developed for global, linear, and super–linear convergence. This paper focuses attention
on two matrix secant updating strategies for the finite dimensional case. These are the Broyden and BFGS updates. The BFGS
update is considered for application in the symmetric case, e.g., convex programming applications, while the Broyden update
can be applied to general monotone operators. Subject to the linear convergence of the iterates and a quadratic growth condition
on the inverse of the operator at the solution, super–linear convergence of the iterates is established for both updates.
These results are applied to show that the Chen–Fukushima variable metric proximal point algorithm is super–linearly convergent
when implemented with the BFGS update.
Received: September 12, 1996 / Accepted: January 7, 2000?Published online March 15, 2000 相似文献
11.
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 相似文献
12.
In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP)
problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints
by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems
includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important
SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem
and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of
the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale
SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method
designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the
transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global
convergence of the algorithm is established under mild and reasonable assumptions.
Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002 相似文献
13.
Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality.
However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent
spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite
programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that
it can handle inequality constraints without seriously increasing computation time. In addition, we introduce inexact null
steps. This abolishes the need of computing exact eigenvectors for subgradients, which brings along significant advantages
in theory and in practice. Encouraging preliminary computational results are reported.
Received: February 1, 2000 / Accepted: September 26, 2001?Published online August 27, 2002
RID="*"
ID="*"A preliminary version of this paper appeared in the proceedings of IPCO ’98 [12]. 相似文献
14.
Basis- and partition identification for quadratic programming and linear complementarity problems 总被引:1,自引:0,他引:1
Arjan B. Berkelaar Benjamin Jansen Kees Roos Tamás Terlaky 《Mathematical Programming》1999,86(2):261-282
Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide
maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other
hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification
algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification
algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from
any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski
and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity
problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality
property of basis tableaus.
Received April 9, 1996 / Revised version received April 27, 1998?
Published online May 12, 1999 相似文献
15.
This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality
constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods
for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the
iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal
set is ensured when the barrier parameter tends to zero, provided strict complementarity holds.
Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 相似文献
16.
This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill
and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n
4
m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that
an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem
with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems
with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms. 相似文献
17.
By means of a conjugation scheme based on generalized convex conjugation theory instead of Fenchel conjugation, we build an alternative dual problem, using the perturbational approach, for a general optimization one defined on a separated locally convex topological space. Conditions guaranteeing strong duality for primal problems which are perturbed by continuous linear functionals and their respective dual problems, which is named stable strong duality, are established. In these conditions, the fact that the perturbation function is evenly convex will play a fundamental role. Stable strong duality will also be studied in particular for Fenchel and Lagrange primal–dual problems, obtaining a characterization for Fenchel case. 相似文献
18.
Satoru Fujishige 《Mathematical Programming》2000,88(1):217-220
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella
and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in
terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional
condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class
of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily
be solved by their greedy algorithm.
Received: February 1999 / Accepted: December 1999?Published online February 23, 2000 相似文献
19.
In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard. 相似文献
20.
Felipe Alvarez Miguel Carrasco Thierry Champion 《Journal of Optimization Theory and Applications》2012,153(2):388-407
Algorithms for convex programming, based on penalty methods, can be designed to have good primal convergence properties even
without uniqueness of optimal solutions. Taking primal convergence for granted, in this paper we investigate the asymptotic
behavior of an appropriate dual sequence obtained directly from primal iterates. First, under mild hypotheses, which include
the standard Slater condition but neither strict complementarity nor second-order conditions, we show that this dual sequence
is bounded and also, each cluster point belongs to the set of Karush–Kuhn–Tucker multipliers. Then we identify a general condition
on the behavior of the generated primal objective values that ensures the full convergence of the dual sequence to a specific
multiplier. This dual limit depends only on the particular penalty scheme used by the algorithm. Finally, we apply this approach
to prove the first general dual convergence result of this kind for penalty-proximal algorithms in a nonlinear setting. 相似文献