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.

Key words： 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