23 results
Search Results
2. Globally Convergent Optimization Algorithms on Riemannian Manifolds: Uniform Framework for Unconstrained and Constrained Optimization.
- Author
-
Yang, Y.
- Subjects
- *
RIEMANNIAN manifolds , *MANIFOLDS (Mathematics) , *DIFFERENTIAL geometry , *MATHEMATICAL optimization , *MATHEMATICAL analysis , *ACCELERATION of convergence in numerical analysis , *STOCHASTIC convergence , *ALGORITHMS , *MATHEMATICS - Abstract
This paper proposes several globally convergent geometric optimization algorithms on Riemannian manifolds, which extend some existing geometric optimization techniques. Since any set of smooth constraints in the Euclidean space Rn (corresponding to constrained optimization) and the Rn space itself (corresponding to unconstrained optimization) are both special Riemannian manifolds, and since these algorithms are developed on general Riemannian manifolds, the techniques discussed in this paper provide a uniform framework for constrained and unconstrained optimization problems. Unlike some earlier works, the new algorithms have less restrictions in both convergence results and in practice. For example, global minimization in the one-dimensional search is not required. All the algorithms addressed in this paper are globally convergent. For some special Riemannian manifold other than Rn, the newalgorithms are very efficient. Convergence rates are obtained. Applications are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
3. Sufficient Optimality Criterion for Linearly Constrained, Separable Concave Minimization Problems.
- Author
-
Illés, T. and Nagy, Á B.
- Subjects
- *
LINEAR programming , *MATHEMATICAL programming , *MATRICES (Mathematics) , *BRANCH & bound algorithms , *ALGORITHMS , *MATHEMATICS - Abstract
A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimally criterion is based on the sensitivity analysis of the relaxed linear programming Problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive. In the Phillip and Rosen paper (Ref.1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimally of the current basic solution. The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithm developed for linearly-constrained concave minimization problems. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
4. Sequential Penalty Algorithm for Nonlinear Constrained Optimization.
- Author
-
Zhang, J.L. and Zhang, X.S.
- Subjects
- *
ALGORITHMS , *MATHEMATICAL optimization , *NONLINEAR theories , *STOCHASTIC convergence , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
In this paper, a new sequential penalty algorithm, based on the L[sub ∞] exact penalty function, is proposed for a general nonlinear constrained optimization problem. The algorithm has the following characteristics: it can start from an arbitrary initial point; the feasibility of the subproblem is guaranteed; the penalty parameter is adjusted automatically; global convergence without any regularity assumption is proved. The update formula of the penalty parameter is new. It is proved that the algorithm proposed in this paper behaves equivalently to the standard SQP method after sufficiently many iterations. Hence, the local convergence results of the standard SQP method can be applied to this algorithm. Preliminary numerical experiments show the efficiency and stability of the algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
5. Descent and Penalization Techniques for Equilibrium Problems with Nonlinear Constraints.
- Author
-
Bigi, Giancarlo and Passacantando, Mauro
- Subjects
- *
EQUILIBRIUM , *MATHEMATICS , *NONLINEAR analysis , *MATHEMATICAL analysis , *ALGORITHMS - Abstract
This paper deals with equilibrium problems with nonlinear constraints. Exploiting a gap function which relies on a polyhedral approximation of the feasible region, we propose two descent methods. They are both based on the minimization of a suitable exact penalty function, but they use different rules for updating the penalization parameter and they rely on different types of line search. The convergence of both algorithms is proved under standard assumptions. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
6. Hybrid Conjugate Gradient Algorithm for Unconstrained Optimization.
- Author
-
Andrei, N.
- Subjects
- *
MATHEMATICAL optimization , *ALGORITHMS , *STOCHASTIC convergence , *CONVEX functions , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
In this paper a new hybrid conjugate gradient algorithm is proposed and analyzed. The parameter β k is computed as a convex combination of the Polak-Ribière-Polyak and the Dai-Yuan conjugate gradient algorithms, i.e. β=(1− θ k) β+ θ k β. The parameter θ k in the convex combination is computed in such a way that the conjugacy condition is satisfied, independently of the line search. The line search uses the standard Wolfe conditions. The algorithm generates descent directions and when the iterates jam the directions satisfy the sufficient descent condition. Numerical comparisons with conjugate gradient algorithms using a set of 750 unconstrained optimization problems, some of them from the CUTE library, show that this hybrid computational scheme outperforms the known hybrid conjugate gradient algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
7. Proximal-Point Algorithm Using a Linear Proximal Term.
- Author
-
He, B., Fu, X., and Jiang, Z.
- Subjects
- *
MATHEMATICAL optimization , *ALGORITHMS , *MATHEMATICAL inequalities , *LAGRANGE equations , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Proximal-point algorithms (PPAs) are classical solvers for convex optimization problems and monotone variational inequalities (VIs). The proximal term in existing PPAs usually is the gradient of a certain function. This paper presents a class of PPA-based methods for monotone VIs. For a given current point, a proximal point is obtained via solving a PPA-like subproblem whose proximal term is linear but may not be the gradient of any functions. The new iterate is updated via an additional slight calculation. Global convergence of the method is proved under the same mild assumptions as the original PPA. Finally, profiting from the less restrictions on the linear proximal terms, we propose some parallel splitting augmented Lagrangian methods for structured variational inequalities with separable operators. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
8. Strong Convergence of Iterative Algorithms for Variational Inequalities in Banach Spaces.
- Author
-
Ceng, L., Schaible, S., and Yao, J.
- Subjects
- *
BANACH spaces , *STOCHASTIC convergence , *ALGORITHMS , *MATHEMATICAL inequalities , *MATHEMATICAL mappings , *MATHEMATICS - Abstract
Let C be a nonempty closed convex subset of a Banach space E with the dual E*, let T: C→ E* be a Lipschitz continuous mapping and let S: C→ C be a relatively nonexpansive mapping. In this paper, by employing the notion of generalized projection operator, we study the following variational inequality (for short, VI( T− f, C)): find x∈ C such that where f∈ E* is a given element. Utilizing the modified Ishikawa iteration and the modified Halpern iteration for relatively nonexpansive mappings, we propose two modified versions of J.L. Li’s (J. Math. Anal. Appl. 295:115–126, ) iterative algorithm for finding approximate solutions of VI( T− f, C). Moreover, it is proven that these iterative algorithms converge strongly to the same solution of VI( T− f, C), which is also a fixed point of S. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
9. Hybrid Rollout Approaches for the Job Shop Scheduling Problem.
- Author
-
Guerriero, F.
- Subjects
- *
ALGORITHMS , *MATHEMATICAL optimization , *JOB shops , *SCHEDULING , *MATHEMATICAL programming , *OPERATIONS research , *HEURISTIC programming , *MATHEMATICS - Abstract
In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically, a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration. The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods. The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
10. On Polyhedral Projection and Parametric Programming.
- Author
-
Jones, C. N., Kerrigan, E. C., and Maciejowski, J. M.
- Subjects
- *
POLYHEDRAL functions , *LINEAR programming , *ALGEBRAIC functions , *POLYNOMIALS , *ALGORITHMS , *DYNAMIC programming , *FUNCTIONAL analysis , *MATHEMATICS , *APPROXIMATION theory - Abstract
This paper brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that, given a parametric linear program (PLP), a polyhedron exists whose projection provides the solution to the PLP. Second, the converse is tackled and it is shown how to formulate a PLP whose solution is the projection of an appropriately defined polyhedron described as the intersection of a finite number of halfspaces. The input to one operation can be converted to an input of the other operation and the resulting output can be converted back to the desired form in polynomial time-this implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
11. Homotopy Method for a General Multiobjective Programming Problem.
- Author
-
Song, W. and Yao, G. M.
- Subjects
- *
HOMOTOPY theory , *INTERIOR-point methods , *MATHEMATICAL programming , *ALGORITHMS , *MATHEMATICS , *HOMOTOPY equivalences - Abstract
In this paper, we present a combined homotopy interior-point method for a general multiobjective programming problem. The algorithm generated by this method associated to Karush-Kuhn-Tucker points of the multiobjective programming problem is proved to be globally convergent under some basic assumptions. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
12. Inexact Operator Splitting Methods with Selfadaptive Strategy for Variational Inequality Problems.
- Author
-
Han, D.
- Subjects
- *
VARIATIONAL inequalities (Mathematics) , *DIFFERENTIAL inequalities , *CALCULUS of variations , *VARIATIONAL principles , *ERROR analysis in mathematics , *ALGORITHMS , *EQUATIONS , *MATHEMATICAL statistics , *MATHEMATICS - Abstract
The Peaceman-Rachford and Douglas-Rachford operator splitting methods are advantageous for solving variational inequality problems, since they attack the original problems via solving a sequence of systems of smooth equations, which are much easier to solve than the variational inequalities. However, solving the subproblems exactly may be prohibitively difficult or even impossible. In this paper, we propose an inexact operator splitting method, where the subproblems are solved approximately with some relative error tolerance. Another contribution is that we adjust the scalar parameter automatically at each iteration and the adjustment parameter can be a positive constant, which makes the methods more practical and efficient. We prove the convergence of the method and present some preliminary computational results, showing that the proposed method is promising. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
13. Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints.
- Author
-
CAFIERI, S., D'APUZZO, M., MARINO, M., MUCHERINO, A., and TORALDO, G.
- Subjects
- *
QUADRATIC programming , *NONLINEAR programming , *ITERATIVE methods (Mathematics) , *LINEAR systems , *ALGORITHMS , *FACTORIZATION , *FACTORS (Algebra) , *LINEAR differential equations , *MATHEMATICS - Abstract
In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
14. Optimization Approach to the Estimation and Control of Lyapunov Exponents.
- Author
-
Pardalos, P. M. and Yatsenko, V. A.
- Subjects
- *
LYAPUNOV exponents , *MATHEMATICAL optimization , *ESTIMATION theory , *CONTROL theory (Engineering) , *ALGORITHMS , *CHAOS theory , *DIFFERENTIAL equations , *MACHINE theory , *MATHEMATICS - Abstract
In this paper, we describe an algorithm for estimating the Lyapunov exponents from the chaotic dynamics of control systems. Attention is focused on optimization methods for estimating tangent maps from experimental time series data. Our numerical tests show that the algorithm is robust and quite effective, and that its performance is comparable with that of other algorithms. The properties of the algorithm are demonstrated by application to a range of data sets. We consider numerical and experimental data and discuss the computational aspects of the proposed algorithm. New feedback rules for use with optimization techniques in the stimulation of the epileptic brain are proposed. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
15. Convex Optimization Approach to Dynamic Output Feedback Control for Delay Differential Systems of Neutral Type.
- Author
-
Park, J. H.
- Subjects
- *
MATHEMATICAL optimization , *EXTERIOR differential systems , *CALCULUS of variations , *MATHEMATICS , *DIFFERENTIAL inequalities , *MATHEMATICAL analysis , *ALGORITHMS , *MATRICES (Mathematics) , *MATHEMATICAL inequalities - Abstract
In this paper. the design problem of the dynamic output feedback controller for the asymptotic stabilization of a class of linear delay differential systems of the neutral type is considered. A criterion for the existence of such controller is derived based on the matrix inequality approach combined with the Lyapunov method. A parametrized characterization of the controller is given in terms of the feasible solutions to certain matrix inequalities, which can be solved by various convex optimization algorithms. A numerical example is given to illustrate the proposed design method. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
16. Approximate Maximum Likelihood Estimation of Circle Parameters.
- Author
-
Chan, Y. T., Lee, B. H., and Thomas, S. M.
- Subjects
- *
APPROXIMATE identities (Algebra) , *ESTIMATION theory , *CIRCLE , *EQUATIONS , *ALGORITHMS , *MATHEMATICS - Abstract
The estimation of a circle's centre and radius from a set of noisy measurement of its circumference has many applications. It is problem of fitting a circle to the measurement and the fit can be in algebraic or geometric distance. The former gives linear equations, while the latter yields nonlinear equations. Starting from estimation theory, this paper first proves that the maximum likelihood (ML), i.e., the optimal estimation of the circle parameters, is equivalent to the minimization of the geometric distances. It then derives a pseudolinear set of ML equations whose coefficients are functions of the unknowns. An approximate ML algorithm updates the coefficients from the previous solution and selects the solution that gives the minimum cost. Simulation results show that the ML algorithm attains the Cramer-Rao lower bound (CRLB) for arc sizes as small as 90℃. For arc sizes of 15℃ and 5℃ the Ml algorithm errors are slightly above the CRLB, but lower than those of other linear estimators. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
17. Value Estimation Approach to the Iri-Imai Method for Constrained Convex Optimization.
- Author
-
Lam, S., Li, D., and Zhang, S.
- Subjects
- *
MATHEMATICAL optimization , *ALGORITHMS , *CONVEX programming , *MATHEMATICAL programming , *CONVEX domains , *MATHEMATICS - Abstract
In this paper, we propose an extension of the so-called Iri-Imai method to solve constrained convex programming problems. The Original Iri-Imai method is designed for linear programs and assumes that the optimal objective value of the optimization problem is known in advance. Zhang (Ref. 9) extends the method for constrained convex optimization, but the optimum value is still assumed to be known in advance. In our new extension, this last requirement on the optimal value is relaxed; instead, only a lower bound of the optimal value is needed. Our approach uses a multiplicative barrier function for the problem with a univariate parameter that represents an estimated optimum value of the original optimization problem. An optimal solution to the original problem can be traced down by minimizing the multiplicative barrier function. Due to the convexity of this barrier function, the optimal objective value as well as the optimal solution of the original problem are sought iteratively by applying Newton's method to the multiplicative barrier function. A new formulation of the multiplicative barrier function is further developed to acquire computational tractability and efficiency. Numerical results are presented to show the efficiency of the new method. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
18. Globally Convergent Interior-Point Algorithm for Nonlinear Programming.
- Author
-
Akrotirianakis, I. and Rustem, B.
- Subjects
- *
INTERIOR-point methods , *MATHEMATICAL programming , *ALGORITHMS , *NONLINEAR programming , *LOGARITHMIC functions , *MATHEMATICAL optimization , *MATHEMATICS - Abstract
This paper presents a primal-dual interior-point algorithm for solving general constrained nonlinear programming problems. The inequality constraints are incorporated into the objective function by means of a logarithmic barrier function. Also, satisfaction of the equality constraints is enforced through the use of an adaptive quadratic penalty function. The penalty parameter is determined using a strategy that ensures a descent property for a merit function. Global convergence of the algorithm is achieved through the monotonic decrease of a merit function. Finally, extensive computational results show that the algorithm can solve large and difficult problems in an efficient and robust way. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
19. Superlinear Convergence of a Newton-Type Algorithm for Monotone Equations.
- Author
-
Zhou, G. and Toh, K. C.
- Subjects
- *
LINEAR systems , *STOCHASTIC convergence , *ALGORITHMS , *MONOTONE operators , *EQUATIONS , *MATHEMATICS - Abstract
We consider the problem of finding solutions of systems of monotone equations. The Newton-type algorithm proposed in Ref. 1 has a very nice global convergence property in that the whole sequence of iterates generated by this algorithm converges to a solution, if it exists. Superlinear convergence of this algorithm is obtained under a standard nonsingularity assumption. The nonsingularity condition implies that the problem has a unique solution; thus, for a problem with more than one solution, such a nonsingularity condition cannot hold. In this paper, we show that the superlinear convergence of this algorithm still holds under a local error-bound assumption that is weaker than the standard nonsingularity condition. The local error-bound condition may hold even for problems with nonunique solutions. As an application, we obtain a Newton algorithm with very nice global and superlinear convergence for the minimum norm solution of linear programs. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
20. Conic Formulation for lp-Norm Optimization.
- Author
-
Glineur, F. and Terlaky, T.
- Subjects
- *
MATHEMATICAL optimization , *INTERIOR-point methods , *DUALITY theory (Mathematics) , *MATHEMATICAL programming , *ALGORITHMS , *MATHEMATICS - Abstract
In this paper, we formulate the lp-norm optimization problem as a conic optimization problem, derive its duality properties (weak duality, zero duality gap, and primal attainment) using standard conic duality and show how it can be solved in polynomial time applying the framework of interior-point algorithms based on self- concordant barriers. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
21. Nonmonotone Trust-Region Method for Nonlinear Programming with General Constraints and Simple Bounds.
- Author
-
Xu, D. C., Han, J. Y., Chen, Z. W., and Tseng, P.
- Subjects
- *
ALGORITHMS , *MATHEMATICAL optimization , *MATHEMATICS , *MATHEMATICAL analysis , *NONLINEAR programming , *MATHEMATICAL programming - Abstract
In this paper, we propose a nonmonotone trust-region algorithm for the solution of optimization problems with general nonlinear equality constraints and simple bounds. Under a constant rank assumption on the gradients of the active constraints, we analyze the global convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
22. Globally and Quadratically Convergent Algorithm for Minimizing the Sum of Euclidean Norms.
- Author
-
Zhou, G., Toh, K.C., and Sun, D.
- Subjects
- *
ALGORITHMS , *STOCHASTIC convergence , *NUMERICAL analysis , *MATHEMATICAL analysis , *MATHEMATICS , *MATHEMATICAL functions - Abstract
For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
23. Geometric Algorithm for Multiparametric Linear Programming.
- Author
-
Borrelli, F., Bemporad, A., and Morari, M.
- Subjects
- *
ALGORITHMS , *LINEAR programming , *SENSITIVITY theory (Mathematics) , *MATHEMATICS , *GEOMETRY , *DISCRETE-time systems - Abstract
We propose a novel algorithm for solving multiparametric linear programming problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.