Arc-search in numerical optimization

Abstract

Determining the search direction and the search step are the two main steps of the nonlinear optimization algorithm, in which the derivatives of the objective and constraint functions are used to determine the search direction, the one-dimensional search and the trust domain methods are used to determine the step length along the search direction. One dimensional line search has been widely discussed in various textbooks and references. However, there is a less-known technique—arc-search method, which is relatively new and may generate more efficient algorithms in some cases. In this paper, we will survey this technique, discuss its applications in different optimization problems, and explain its potential improvements over traditional line search method.

Keywords

Arc-search / numerical optimization / linear programming and convex quadratic programming / unconstrained optimization / constrained optimization

References

[1] Absil P-A, Baker C G, Gallivan K A. Trust-region methods on Riemannian manifolds. Found Comput Math 2007; 7(3): 303–330

[2] AbsilP-AMahony RSepulchreR. Optimization Algorithms on Matrix Manifolds. Princeton NJ: Princeton Univ Press, 2008

[3] Adler R L, Dedieu J P, Margulies J Y, Martens M, Shub M. Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J Numer Anal 2002; 22(3): 359–390

[4] Apostolopoulou M S, Sotiropoulos D G, Botsaris C A. A curvilinear method based on minimal-memory BFGS updates. Appl Math Comput 2010; 217(2): 882–892

[5] Bader B W, Schnabel R B. Curvilinear linesearch for tensor methods. SIAM J Sci Comput 2003; 25(2): 604–622

[6] Beale E M L. On minimizing a convex function subject to linear inequalities. J R Stat Soc Ser B 1955; 17(2): 173–184

[7] BertsekasD P. Nonlinear Programming, 2nd ed. Belmont, MA: Athena Scientific, 1999

[8] Boscolo R, Pan H, Roychowdhury V P. Independent component analysis based on nonparametric density estimation. IEEE Trans Neural Netw 2004; 15(1): 55–65

[9] Botsaris C A. Constrained optimization along geodesics. J Math Anal Appl 1981; 79(2): 295–306

[10] BrockettR W. Differential geometry and the design of gradient algorithms. In: Differential Geometry: Partial Differential Equations on Manifolds. Proc Sympos Pure Math, Vol 54, Part 1. Providence, RI: AMS, 1993, 69–92

[11] CaiDHeX F HanJ W. Semi-supervised discriminant analysis. In: IEEE 11th International Conference on Computer Vision. IEEE, 2007, https://doi: 10.1109/ICCV.2007.4408856

[12] Chen X Y, Zhang S G. A geometric method for a class of convex programs. J Fujian Norm Univ (Nat Sci Ed) 2012; 28(2): 7–10

[13] Chu M T. Curves on S^(n-1) that lead to eigenvalues or their means of a matrix. SIAM J Algebraic Discrete Methods 1986; 7(3): 425–432

[14] Conforti D, Grandinetti L, Musmanno R. A parallel tensor algorithm for nonlinear optimization. Optim Method Softw 1994; 3(1/2/3): 125–142

[15] Conforti D, Mancini M. A curvilinear search algorithm for unconstrained optimization by automatic differentiation. Optim Method Softw 2001; 15(3/4): 283–297

[16] DantzigG B. Maximization of a linear function of variables subject to linear inequalities. In: Activity Analysis of Production and Allocation. Cowles Commission Monograph, No 13. New York: John Wiley & Sons, 1951, 339–347

[17] Dennis J E Jr, Echebest N, Guardarucci M T, Martinez J M, Scolnik H D, Vacchino C. A curvilinear search using tridiagonal secant updates for unconstrained optimization. SIAM J Optim 1991; 1(3): 333–357

[18] Edelman A, Arias T A, Smith S T. The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 1998; 20(2): 303–353

[19] Ferris M C, Lucid S, Roma M. Nonmonotone curvilinear line search methods for unconstrained optimization. Comput Optim Appl 1996; 6(2): 117–136

[20] FiaccoA VMcCormick G P. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. New York: John Wiley & Sons, 1968

[21] FletcherR. Practical Methods of Optimization, 2nd ed. Chichester: John Wiley & Sons, 1987

[22] Gabay D. Minimizing a differentiable function over a differentiable manifold. J Optim Theory Appl 1982; 37(2): 177–219

[23] Goldfarb D. Curvilinear path steplength algorithms for minimization which use directions of negative curvature. Math Program 1980; 18(1): 31–40

[24] Gould N I M, Lucidi S, Roma M, Toint Ph L. Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optim Method Softw 2000; 14(1/2): 75–98

[25] GrandinettiL. Nonlinear optimization by a curvilinear path strategy. In: System Modeling and Optimization. Lect Notes Control Inf Sci, Vol 59. Berlin: Springer-Verlag, 1984, 289–298

[26] HendersonN W. Arc search methods for linearly constrained optimization. Ph D Thesis. Stanford, CA: Stanford University, 2012

[27] HockWSchittkowski K. Test Examples for Nonlinear Programming Codes. Lecture Notes in Econom and Math Systems, Vol 187. Berlin: Springer-Verlag, 1981

[28] IsidoriA. Nonlinear Control Systems, 3rd ed. Berlin: Springer-Verlag, 1995

[29] James L D, Heath R W. Limited feedback unitary precoding for spatial multiplexing systems. IEEE Trans Inform Theory 2005; 51(8): 2967–2976

[30] Kantorovich L V. Mathematical methods of organizing and planning production. Manag Sci 1960; 6(4): 366–422

[31] Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorics 1984; 4(4): 373–395

[32] KleeVMinty G J. How good is the simplex algorithm? In: Inequalities, III (Shisha O ed). New York: Academic Press, 1972, 159–175

[33] KuhnH WTucker A W. Nonlinear programming. In: Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (Neyman J ed). Berkeley, CA: Univ California Press, 1951, 481–492

[34] LeeP Y. Geometric optimization for computer vision. Ph D Thesis. Canberra: Austral Nat Univ, 2005

[35] Li G W, Liu Y P, Yin J, Shi Z L. Planar object recognition based on Riemannian manifold. Acta Autom Sin 2010; 36(4): 465–474

[36] Lucidi S, Rochetich F, Roma M. Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization. SIAM J Optim 1998; 8(4): 916–939

[37] LuenbergerD G. Introduction to Linear and Nonlinear Programming. Reading, MA: Addison Wesley, 1972

[38] LuenbergerD GYeY Y. Linear and Nonlinear Programming, 3rd ed. New York: Springer Science+Business Media, 2008

[39] Ma Y, Košecká J, Sastry S. Optimization criteria and geometric algorithms for motion and structure estimation. Int J Comput Vis 2001; 44(3): 219–249

[40] Manton J H. Optimization algorithms exploiting unitary constraints. IEEE Trans Signal Process 2002; 50(3): 635–650

[41] Martìnez J M, Santos R F. An algorithm for solving nonlinear least-squares problems with a new curvilinear search. Computing 1990; 44(1): 83–90

[42] McCormick G P. A modification of Armijo’s step-size rule for negative curvature. Math Program 1977; 13(1): 111–115

[43] MeggidoN. Pathways to the optimal set in linear programming. In: Progress in Mathematical Programming: Interior-point and Related Methods. New York: Springer-Verlag, 1989, 131–158

[44] Mehrotra S. On the implementation of a primal-dual interior point method. SIAM J Optim 1992; 2(4): 575–601

[45] Mizuno S, Todd M, Ye Y Y. On adaptive-step primal-dual interior-point algorithms for linear programming. Math Oper Res 1993; 18(4): 964–981

[46] Monteiro R D C, Adler I, Resende M G C. A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math Oper Res 1990; 15(2): 191–214

[47] Moré J J, Sorensen D C. On the use of directions of negative curvature in a modified Newton method. Math Program 1979; 16(1): 1–20

[48] Netlib. Netlib linear programming library, 2016

[49] NocedalJWright S J. Numerical Optimization. New York: Springer-Verlag, 1999

[50] Olivares A, Moguerza J M, Prieto F J. Nonconvex optimization using negative curvature within a modified linesearch. European J Oper Res 2008; 189(3): 706–722

[51] Rapcsák T. Geodesic convexity in nonlinear optimization. J Optim Theory Appl 1991; 69(1): 169–183

[52] Ring W, Wirth B. Optimization methods on Riemannian manifolds and their application to shape space. SIAM J Optim 2012; 22(2): 596–627

[53] SmithS T. Geometric optimization methods for adaptive filtering. Ph D Thesis. Cambridge, MA: Harvard University, 1993

[54] SmithS T. Optimization techniques on Riemannian manifolds. In: Hamiltonian and Gradient Flows, Algorithms and Control (Bloch A ed). Fields Inst Commun, Vol 3. Providence, RI: AMS, 1994, 113–136

[55] Sun W Y, Zhou Q Y. An unconstrained optimization method using nonmonotone second order Goldstein’s line search. Sci China Math 2007; 50(10): 1389–1400

[56] Tits A L, Wachter A, Bakhtiari S, Urban T J, Lawrence C T. A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties. SIAM J Optim 2003; 14(1): 173–199

[57] UdrişteC. Convex Functions and Optimization Methods on Riemannian Manifolds. Mathematics and Its Applications, Vol 297. Dordrecht: Kluwer Acad Publ, 1994

[58] Vasconcelos J F, Elkaim G, Silvestre C, Oliveira P, Cardeira B. Geometric approach to strapdown magnetometer calibration in sensor frame. IEEE Trans Aerosp Electron Syst 2011; 47(2): 1293–1306

[59] WrightS J. Primal-dual Interior-point Methods. Philadelphia, PA: SIAM, 1997

[60] Yang X M, Liu H W, Liu C H. Arc-search interior-point algorithm. J Jilin Univ Sci 2014; 52(4): 693–697

[61] YangY G. Robust system design: pole assignment approaches. Ph D Thesis. College Park, MD: Univ Maryland, 1996

[62] Yang Y G. Globally convergent optimization algorithms on Riemannian manifolds: uniform framework for unconstrained and constrained optimization. J Optim Theory Appl 2007; 132(2): 245–265

[63] YangY G. Arc-search path-following interior-point algorithms for linear programming. Optimization Online, 2009

[64] Yang Y G. A polynomial arc-search interior-point algorithm for convex quadratic programming. European J Oper Res 2011; 215(1): 25–38

[65] Yang Y G. A polynomial arc-search interior-point algorithm for linear programming. J Optim Theory Appl 2013; 158(3): 859–873

[66] Yang Y G. A globally and quadratically convergent algorithm with efficient implementation for unconstrained optimization. Comput Appl Math 2015; 34(3): 1219–1236

[67] Yang Y G. Attitude determination using Newton’s method on Riemannian manifold. Proc IMechE Part G. J Aerosp Eng 2015; 229(14): 2737–2742

[68] YangY G. Curve LP—a MATLAB implementation of an infeasible interior-point algorithm for linear programming. Numer Algorithms, 2016, doi: 10.1007/s11075-016-0180-1

[69] Yang YiG. Uniform framework for unconstrained and constrained optimization: optimization on Riemannian manifolds. In: 2010 International Conference on E-Product E-Service and E-Entertainment. Piscataway, NJ: IEEE, 2010 (in Chinese)

[70] YeY Y. Interior-point Algorithms: Theory and Analysis. New York: John Wiley & Sons, 1997

[71] Zhang J J, Cao J, Wang Y Y. Gradient algorithm on Stiefel manifold and application in feature extraction. J Radars 2013; 2(3): 309–313

[72] Zhou Q Y, Sun W Y. A nonmonotone second-order steplength method for unconstrained minimization. J Comput Math 2007; 25(1): 104–112

RIGHTS & PERMISSIONS

2023 Higher Education Press 2023