共查询到20条相似文献,搜索用时 31 毫秒
1.
R. Goldbach 《Applied Mathematics and Optimization》1999,39(1):121-142
We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems,
which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation
and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic
constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present.
We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical
results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered
in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since
many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular,
we do not assume boundedness of the feasible set as required in related methods.
Accepted 7 May 1997 相似文献
2.
A differential inclusion is designed for solving cone-constrained convex programs. The method is of subgradient-projection type. It involves projection, penalties and Lagrangian relaxation. Nonsmooth data can be accommodated. A novelty is that multipliers converge monotonically upwards to equilibrium levels. An application to stochastic programming is considered.Corresponding author. 相似文献
3.
Given a finite number of closed convex sets whose algebraic representation is known, we study the problem of finding the minimum
of a convex function on the closure of the convex hull of the union of those sets. We derive an algebraic characterization
of the feasible region in a higher-dimensional space and propose a solution procedure akin to the interior-point approach
for convex programming.
Received November 27, 1996 / Revised version received June 11, 1999?Published online November 9, 1999 相似文献
4.
Hiroshi Yabe Hideho Ogasawara Masayuki Yoshino 《Journal of Computational and Applied Mathematics》2007
For solving unconstrained minimization problems, quasi-Newton methods are popular iterative methods. The secant condition which employs only the gradient information is imposed on these methods. Several researchers paid attention to other secant conditions to get a better approximation of the Hessian matrix of the objective function. Recently, Zhang et al. [New quasi-Newton equation and related methods for unconstrained optimization, J. Optim. Theory Appl. 102 (1999) 147–167] and Zhang and Xu [Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, J. Comput. Appl. Math. 137 (2001) 269–278] proposed the modified secant condition which uses both gradient and function value information in order to get a higher order accuracy in approximating the second curvature of the objective function. They showed the local and q-superlinear convergence property of the BFGS-like and DFP-like updates based on their proposed secant condition. In this paper, we incorporate one parameter into this secant condition to smoothly switch the standard secant condition and the secant condition of Zhang et al. We consider a modified Broyden family which includes the BFGS-like and the DFP-like updates proposed by Zhang et al. We prove the local and q-superlinear convergence of our method. 相似文献
5.
Summary In this paper we describe how to use Gram-Schmidt factorizations of Daniel et al. [1] to realize the method of [8] for solving linearly constrained linear least squares problems. The main advantage of using these factorizations is that it is relatively easy to take data changes into account, if necessary.The algorithm is compared numerically with two other codes, one of them published by Lawson and Hanson [3]. Further computational tests show the efficiency of the proposed methods, if a few data of the original problem are changed subsequently.This paper was sponsored by Deutsche Forschungsgemeinschaft, Bonn-Bad Godesberg 相似文献
6.
Hideaki Iiduka 《Journal of Computational and Applied Mathematics》2012,236(7):1733-1742
A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness. 相似文献
7.
Levent Tunçel 《Foundations of Computational Mathematics》2001,1(3):229-254
We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems
in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov
and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we
allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd
algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual
interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual
algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication
increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better
theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric
primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated
framework.
August 25, 1999. Final version received: March 7, 2001. 相似文献
8.
Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested. 相似文献
9.
This paper concerns with convergence properties of the classical proximal point algorithm for finding zeroes of maximal monotone
operators in an infinite-dimensional Hilbert space. It is well known that the proximal point algorithm converges weakly to
a solution under very mild assumptions. However, it was shown by Güler [11] that the iterates may fail to converge strongly
in the infinite-dimensional case. We propose a new proximal-type algorithm which does converge strongly, provided the problem
has a solution. Moreover, our algorithm solves proximal point subproblems inexactly, with a constructive stopping criterion
introduced in [31]. Strong convergence is forced by combining proximal point iterations with simple projection steps onto
intersection of two halfspaces containing the solution set. Additional cost of this extra projection step is essentially negligible
since it amounts, at most, to solving a linear system of two equations in two unknowns.
Received January 6, 1998 / Revised version received August 9, 1999?Published online November 30, 1999 相似文献
10.
《Optimization》2012,61(4):503-508
The convex circumpolygon with maximal area to a given convex polygon can be determined by means of dynamic programming. The effort of this method increases cubically with respect to the number of sides. It is further shown that the optimal circum-polygon can be constructed with ruler and circle. The applied version of dynamic programming can be also used for solving Steiner's problem of the inpoiygon with minimal circumference but it demands a higher effort than Phú's method. 相似文献
11.
R. Pytlak 《Numerische Mathematik》2002,91(2):319-321
Summary. We show that the example given in [Dai, Y., Yuan, Y. (1999): Global convergence of the method of shortest residuals, Numerische
Mathematik 83, 581–598] does not contradict the results of [Pytlak, R. (1994): On the convergence of conjugate gradient algorithms,
IMA J. Numerical Analysis 14, 443–460].
Received September 9, 2000 / Revised version received November 28, 2000 / Published online July 25, 2001 相似文献
12.
Solving a class of linear projection equations 总被引:7,自引:0,他引:7
Binsheng He 《Numerische Mathematik》1994,68(1):71-80
Summary. Many interesting and important constrained
optimization problems in mathematical programming can be translated into an
equivalent linear projection equation
Here,
is the orthogonal projection on some convex set
(e.g. )
and is a positive semidefinite
matrix.
This paper presents some new methods for solving a class of linear projection
equations. The search directions of these methods are straighforward
extensions of
the directions in traditional methods for unconstrained optimization.
Based on the idea of a projection and contraction method [7] we get a
simple step length rule and are able to obtain global linear
convergence.
Received April 19, 1993 / Revised version received February 9,
1994 相似文献
13.
A proximal-based decomposition method for convex minimization problems 总被引:10,自引:0,他引:10
This paper presents a decomposition method for solving convex minimization problems. At each iteration, the algorithm computes two proximal steps in the dual variables and one proximal step in the primal variables. We derive this algorithm from Rockafellar's proximal method of multipliers, which involves an augmented Lagrangian with an additional quadratic proximal term. The algorithm preserves the good features of the proximal method of multipliers, with the additional advantage that it leads to a decoupling of the constraints, and is thus suitable for parallel implementation. We allow for computing approximately the proximal minimization steps and we prove that under mild assumptions on the problem's data, the method is globally convergent and at a linear rate. The method is compared with alternating direction type methods and applied to the particular case of minimizing a convex function over a finite intersection of closed convex sets.Corresponding author. Partially supported by Air Force Office of Scientific Research Grant 91-0008 and National Science Foundation Grant DMS-9201297. 相似文献
14.
Tamás Fleiner 《Combinatorica》2001,21(1):145-150
Frank and Jordán [1] proved an important min-max result on covering a crossing family of set-pairs. As an application, among
others they can solve the unweighted node-connectivity augmentation problem for directed graphs in polynomial time. In this
paper, we show how to solve the dual packing problem in polynomial time. To decompose a fractional dual optimum as a convex
combination of integer vertices, besides the ellipsoid method, we use a polynomial-time algorithm for uncrossing a family
of set-pairs. Our main result is this uncrossing algorithm.
Received November 9, 1998 / Revised October 18, 1999 相似文献
15.
This paper concerns a filter technique and its application to the trust region method for nonlinear programming (NLP) problems. We used our filter trust region algorithm to solve NLP problems with equality and inequality constraints, instead of solving NLP problems with just inequality constraints, as was introduced by Fletcher et al. [R. Fletcher, S. Leyffer, Ph.L. Toint, On the global converge of an SLP-filter algorithm, Report NA/183, Department of Mathematics, Dundee University, Dundee, Scotland, 1999]. We incorporate this filter technique into the traditional trust region method such that the new algorithm possesses nonmonotonicity. Unlike the tradition trust region method, our algorithm performs a nonmonotone filter technique to find a new iteration point if a trial step is not accepted. Under mild conditions, we prove that the algorithm is globally convergent. 相似文献
16.
Convergence of Newton's method for convex best interpolation 总被引:7,自引:0,他引:7
Summary. In this paper, we consider the problem of finding a convex function which interpolates given points and has a minimal norm of the second derivative. This problem reduces to a system of equations involving semismooth functions. We study a Newton-type
method utilizing Clarke's generalized Jacobian and prove that its local convergence is superlinear. For a special choice of
a matrix in the generalized Jacobian, we obtain the Newton method proposed by Irvine et al. [17] and settle the question of
its convergence. By using a line search strategy, we present a global extension of the Newton method considered. The efficiency
of the proposed global strategy is confirmed with numerical experiments.
Received October 26, 1998 / Revised version received October 20, 1999 / Published online August 2, 2000 相似文献
17.
We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC1) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems. 相似文献
18.
A family of variable metric proximal methods 总被引:5,自引:0,他引:5
J. F. Bonnans J. Ch. Gilbert C. Lemaréchal C. A. Sagastizábal 《Mathematical Programming》1995,68(1-3):15-47
We consider conceptual optimization methods combining two ideas: the Moreau—Yosida regularization in convex analysis, and quasi-Newton approximations of smooth functions. We outline several approaches based on this combination, and establish their global convergence. Then we study theoretically the local convergence properties of one of these approaches, which uses quasi-Newton updates of the objective function itself. Also, we obtain a globally and superlinearly convergent BFGS proximal method. At each step of our study, we single out the assumptions that are useful to derive the result concerned. 相似文献
19.
《Optimization》2012,61(6):693-713
We consider convex semiinfinite programming (SIP) problems with an arbitrary fixed index set T. The article analyzes the relationship between the upper and lower semicontinuity (lsc) of the optimal value function and the optimal set mapping, and the so-called Hadamard well-posedness property (allowing for more than one optimal solution). We consider the family of all functions involved in some fixed optimization problem as one element of a space of data equipped with some topology, and arbitrary perturbations are premitted as long as the perturbed problem continues to be convex semiinfinite. Since no structure is required for T, our results apply to the ordinary convex programming case. We also provide conditions, not involving any second order optimality one, guaranteeing that the distance between optimal solutions of the discretized subproblems and the optimal set of the original problem decreases by a rate which is linear with respect to the discretization mesh-size. 相似文献
20.
Konrad J. Swanepoel 《Monatshefte für Mathematik》2000,129(3):217-226
We show that if six translates of a convex disc C all touch C, and no two of the translates have interior points in common, then there are never more than two gaps, i.e., consecutive
non-touching pairs of translates. We also characterize the configurations where there are two, one or no gaps. This result
is then applied to show that the Steiner point in a 1-Steiner Minimum Tree in a normed plane has degree at most five if the
unit ball is not an affine regular hexagon (where Steiner points of degree six exist).
(Received 23 July 1999) 相似文献