共查询到20条相似文献,搜索用时 31 毫秒
1.
Javier Peña 《Mathematical Programming》2002,93(1):55-75
We study two issues on condition numbers for convex programs: one has to do with the growth of the condition numbers of the
linear equations arising in interior-point algorithms; the other deals with solving conic systems and estimating their distance
to infeasibility.?These two issues share a common ground: the key tool for their development is a simple, novel perspective
based on implicitly-defined barrier functions. This tool has potential use in optimization beyond the context of condition numbers.
Received: October 2000 / Accepted: October 2001?Published online March 27, 2002 相似文献
2.
Summary. This paper proposes a validation method for solutions of linear complementarity problems. The validation procedure consists
of two sufficient conditions that can be tested on a digital computer. If the first condition is satisfied then a given multidimensional
interval centered at an approximate solution of the problem is guaranteed to contain an exact solution. If the second condition
is satisfied then the multidimensional interval is guaranteed to contain no exact solution. This study is based on the mean
value theorem for absolutely continuous functions and the reformulation of linear complementarity problems as nonsmooth nonlinear
systems of equations.
Received August 21, 1997 / Revised version July 2, 1998 相似文献
3.
Jing Zhou Shu-Cherng Fang Wenxun Xing 《Computational Optimization and Applications》2017,66(1):97-122
This paper proposes a conic approximation algorithm for solving quadratic optimization problems with linear complementarity constraints.We provide a conic reformulation and its dual for the original problem such that these three problems share the same optimal objective value. Moreover, we show that the conic reformulation problem is attainable when the original problem has a nonempty and bounded feasible domain. Since the conic reformulation is in general a hard problem, some conic relaxations are further considered. We offer a condition under which both the semidefinite relaxation and its dual problem become strictly feasible for finding a lower bound in polynomial time. For more general cases, by adaptively refining the outer approximation of the feasible set, we propose a conic approximation algorithm to identify an optimal solution or an \(\epsilon \)-optimal solution of the original problem. A convergence proof is given under simple assumptions. Some computational results are included to illustrate the effectiveness of the proposed algorithm. 相似文献
4.
Leo Liberti 《Discrete Applied Mathematics》2009,157(6):1309-1318
This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms. 相似文献
5.
Liqun Qi 《Journal of Global Optimization》2006,35(2):343-366
The Karush-Kuhn-Tucker (KKT) system of the variational inequality problem over a set defined by inequality and equality constraints
can be reformulated as a system of semismooth equations via an nonlinear complementarity problem (NCP) function. We give a
sufficient condition for boundedness of the level sets of the norm function of this system of semismooth equations when the
NCP function is metrically equivalent to the minimum function; and a sufficient and necessary condition when the NCP function
is the minimum function. Nonsingularity properties identified by Facchinei, Fischer and Kanzow, 1998, SIAM J. Optim. 8, 850–869, for the semismooth reformulation of the variational inequality problem via the Fischer-Burmeister function,
which is an irrational regular pseudo-smooth NCP function, hold for the reformulation based on other regular pseudo-smooth
NCP functions. We propose a new regular pseudo-smooth NCP function, which is piecewise linear-rational and metrically equivalent
to the minimum NCP function. When it is used to the generalized Newton method for solving the variational inequality problem,
an auxiliary step can be added to each iteration to reduce the value of the merit function by adjusting the Lagrangian multipliers
only.
This work is supported by the Research Grant Council of Hong Kong
This paper is dedicated to Alex Rubinov on the occasion of his 65th Birthday 相似文献
6.
Our study concerns thalamo-cortical systems which are modelled by nonlinear systems of Volterra integro-differential equations of convolution type. The thalamo-cortical systems describe a new architecture for a neurocomputer. Such a computer employs principles of human brain. It consists of oscillators which have different frequencies and are weakly connected via a common medium forced by an external input. Since a neurocomputer consists of many interconnected oscillators (referred also as neurons), the thalamo-cortical systems include large numbers of Volterra integro-differential equations. Solving such systems numerically is expensive not only because of their large dimensions but also because of many kernel evaluations which are needed over the whole interval from the initial point, where the initial condition is imposed, up to the present point, where the computations are currently executed. Moreover, the whole computed history of the solution has to be stored in the memory of the computing machine. Therefore, robust and efficient numerical algorithms are needed for computer simulations for the solutions to the thalamocortical systems. In this paper, we illustrate an iteration technique to solve the thalamo-cortical systems. The proposed successive iterates are vector functions of time, which change the original problems into systems of easier and separated equations. Such separated equations can then be solved in parallel computing environments. Results of numerical experiments are presented for large numbers of oscillators. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
7.
Nonsmooth Equation Based BFGS Method for Solving KKT Systems in Mathematical Programming 总被引:2,自引:0,他引:2
Li D. H. Yamashita N. Fukushima M. 《Journal of Optimization Theory and Applications》2001,109(1):123-167
In this paper, we present a BFGS method for solving a KKT system in mathematical programming, based on a nonsmooth equation reformulation of the KKT system. We split successively the nonsmooth equation into equivalent equations with a particular structure. Based on the splitting, we develop a BFGS method in which the subproblems are systems of linear equations with symmetric and positive-definite coefficient matrices. A suitable line search is introduced under which the generated iterates exhibit an approximate norm descent property. The method is well defined and, under suitable conditions, converges to a KKT point globally and superlinearly without any convexity assumption on the problem. 相似文献
8.
Javier Peña 《Operations Research Letters》2004,32(5):463-467
It is known that linear conic systems are a special case of set-valued sublinear mappings. Hence the latter subsumes the former. In this note we observe that linear conic systems also contain set-valued sublinear mappings as a special case. Consequently, the former also subsumes the latter. 相似文献
9.
In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective. 相似文献
10.
In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range. 相似文献
11.
A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical
learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by
second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral
conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that
solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the
branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order
conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are
nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear
cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming.
We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance
capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that
conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer
programs and, hence, improving their solvability.
This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation. 相似文献
12.
D. Sun 《Applied Mathematics and Optimization》1999,40(3):315-339
In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P
0
-function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution
set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic)
without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are
provided and further applications to other problems are discussed.
Accepted 25 March 1998 相似文献
13.
M. J. Todd 《Mathematical Programming》2008,111(1-2):301-313
We observe a curious property of dual versus primal-dual path-following interior-point methods when applied to unbounded linear
or conic programming problems in dual form. While primal-dual methods can be viewed as implicitly following a central path
to detect primal infeasibility and dual unboundedness, dual methods can sometimes implicitly move away from the analytic center of the set of infeasibility/unboundedness detectors.
Dedicated to Clovis Gonzaga on the occassion of his 60th birthday. 相似文献
14.
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. 相似文献
15.
We introduce and characterize a class of differentiable convex functions for which the Karush—Kuhn—Tucker condition is necessary for optimality. If some constraints do not belong to this class, then the characterization of optimality generally assumes an asymptotic form.We also show that for the functions that belong to this class in multi-objective optimization, Pareto solutions coincide with strong Pareto solutions,. This extends a result, well known for the linear case.Research partly supported by the National Research Council of Canada. 相似文献
16.
17.
This paper is concerned with iterative solution methods for large linear systems of equations with a matrix of ill-determined rank and an error-contaminated right-hand side. The numerical solution is delicate, because the matrix is very ill-conditioned and may be singular. It is natural to require that the computed iterates live in the range of the matrix when the latter is symmetric, because then the iterates are orthogonal to the null space. Computational experience indicates that it can be beneficial to require that the iterates live in the range of the matrix also when the latter is nonsymmetric. We discuss the design and implementation of iterative methods that determine iterates with this property. New implementations that are particularly well suited for use with the discrepancy principle are described. 相似文献
18.
In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω of the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips, and disks. We refer to this problem as the nearest Ω‐stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time‐invariant systems. In order to achieve this goal, we parameterize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples. 相似文献
19.
K.A. Ariyawansa 《Numerische Mathematik》1998,80(3):363-376
Summary. Many successful quasi-Newton methods for optimization are based on positive definite local quadratic approximations to the
objective function that interpolate the values of the gradient at the current and new iterates. Line search termination criteria
used in such quasi-Newton methods usually possess two important properties. First, they guarantee the existence of such a
local quadratic approximation. Second, under suitable conditions, they allow one to prove that the limit of the component
of the gradient in the normalized search direction is zero. This is usually an intermediate result in proving convergence.
Collinear scaling algorithms proposed initially by Davidon in 1980 are natural extensions of quasi-Newton methods in the sense
that they are based on normal conic local approximations that extend positive definite local quadratic approximations, and
that they interpolate values of both the gradient and the function at the current and new iterates. Line search termination criteria that guarantee the existence
of such a normal conic local approximation, which also allow one to prove that the component of the gradient in the normalized
search direction tends to zero, are not known. In this paper, we propose such line search termination criteria for an important
special case where the function being minimized belongs to a certain class of convex functions.
Received February 1, 1997 / Revised version received September 8, 1997 相似文献
20.
In this paper, a new backward error criterion, together with a sensitivity measure, is presented for assessing solution accuracy of nonsymmetric and symmetric algebraic Riccati equations (AREs). The usual approach to assessing reliability of computed solutions is to employ standard perturbation and sensitivity results for linear systems and to extend them further to AREs. However, such methods are not altogether appropriate since they do not take account of the underlying structure of these matrix equations. The approach considered here is to first compute the backward error of a computed solution X? that measures the amount by which data must be perturbed so that X? is the exact solution of the perturbed original system. Conventional perturbation theory is used to define structured condition numbers that fully respect the special structure of these matrix equations. The new condition number, together with the backward error of computed solutions, provides accurate estimates for the sensitivity of solutions. Optimal perturbations are then used in an iterative refinement procedure to give further more accurate approximations of actual solutions. The results are derived in their most general setting for nonsymmetric and symmetric AREs. This in turn offers a unifying framework through which it is possible to establish similar results for Sylvester equations, Lyapunov equations, linear systems, and matrix inversions. 相似文献