Arc-search in numerical optimization

doi:10.3868/s140-DDD-023-0022-x

Front. Math. China

2023, Vol. 18

Issue (5) : 313-326 https://doi.org/10.3868/s140-DDD-023-0022-x

Arc-search in numerical optimization

Yiguang YANG(

)

College of Information and Safety Engineering, Zhongnan University of Economics and Law, Wuhan 430073, China

Download: PDF(321 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Online First Date: 27 December 2023 Issue Date: 11 January 2024

Cite this article:

Yiguang YANG. Arc-search in numerical optimization[J]. Front. Math. China, 2023, 18(5): 313-326.

URL:

https://academic.hep.com.cn/fmc/EN/10.3868/s140-DDD-023-0022-x
https://academic.hep.com.cn/fmc/EN/Y2023/V18/I5/313

1	P-A Absil, C G Baker, K A Gallivan. Trust-region methods on Riemannian manifolds. Found Comput Math 2007; 7(3): 303–330
2	P-A AbsilR MahonyR Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton NJ: Princeton Univ Press, 2008
3	R L Adler, J P Dedieu, J Y Margulies, M Martens, M Shub. Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J Numer Anal 2002; 22(3): 359–390
4	M S Apostolopoulou, D G Sotiropoulos, C A Botsaris. A curvilinear method based on minimal-memory BFGS updates. Appl Math Comput 2010; 217(2): 882–892
5	B W Bader, R B Schnabel. Curvilinear linesearch for tensor methods. SIAM J Sci Comput 2003; 25(2): 604–622
6	E M L Beale. On minimizing a convex function subject to linear inequalities. J R Stat Soc Ser B 1955; 17(2): 173–184
7	D P Bertsekas. Nonlinear Programming, 2nd ed. Belmont, MA: Athena Scientific, 1999
8	R Boscolo, H Pan, V P Roychowdhury. Independent component analysis based on nonparametric density estimation. IEEE Trans Neural Netw 2004; 15(1): 55–65
9	C A Botsaris. Constrained optimization along geodesics. J Math Anal Appl 1981; 79(2): 295–306
10	R W Brockett. 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	D CaiX F He J W Han. Semi-supervised discriminant analysis. In: IEEE 11th International Conference on Computer Vision. IEEE, 2007, https://doi: 10.1109/ICCV.2007.4408856
12	X Y Chen, S G Zhang. A geometric method for a class of convex programs. J Fujian Norm Univ (Nat Sci Ed) 2012; 28(2): 7–10
13	M T Chu. 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	D Conforti, L Grandinetti, R Musmanno. A parallel tensor algorithm for nonlinear optimization. Optim Method Softw 1994; 3(1/2/3): 125–142
15	D Conforti, M Mancini. A curvilinear search algorithm for unconstrained optimization by automatic differentiation. Optim Method Softw 2001; 15(3/4): 283–297
16	G B Dantzig. 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	J E Jr Dennis, N Echebest, M T Guardarucci, J M Martinez, H D Scolnik, C Vacchino. A curvilinear search using tridiagonal secant updates for unconstrained optimization. SIAM J Optim 1991; 1(3): 333–357
18	A Edelman, T A Arias, S T Smith. The geometry of algorithms with orthogonality constraints. SIAM J Matrix Anal Appl 1998; 20(2): 303–353
19	M C Ferris, S Lucid, M Roma. Nonmonotone curvilinear line search methods for unconstrained optimization. Comput Optim Appl 1996; 6(2): 117–136
20	A V FiaccoG P McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. New York: John Wiley & Sons, 1968
21	R Fletcher. Practical Methods of Optimization, 2nd ed. Chichester: John Wiley & Sons, 1987
22	D Gabay. Minimizing a differentiable function over a differentiable manifold. J Optim Theory Appl 1982; 37(2): 177–219
23	D Goldfarb. Curvilinear path steplength algorithms for minimization which use directions of negative curvature. Math Program 1980; 18(1): 31–40
24	N I M Gould, S Lucidi, M Roma, L Toint Ph. Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optim Method Softw 2000; 14(1/2): 75–98
25	L Grandinetti. 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	N W Henderson. Arc search methods for linearly constrained optimization. Ph D Thesis. Stanford, CA: Stanford University, 2012
27	W HockK Schittkowski. Test Examples for Nonlinear Programming Codes. Lecture Notes in Econom and Math Systems, Vol 187. Berlin: Springer-Verlag, 1981
28	A Isidori. Nonlinear Control Systems, 3rd ed. Berlin: Springer-Verlag, 1995
29	L D James, R W Heath. Limited feedback unitary precoding for spatial multiplexing systems. IEEE Trans Inform Theory 2005; 51(8): 2967–2976
30	L V Kantorovich. Mathematical methods of organizing and planning production. Manag Sci 1960; 6(4): 366–422
31	N Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorics 1984; 4(4): 373–395
32	V KleeG J Minty. How good is the simplex algorithm? In: Inequalities, III (Shisha O ed). New York: Academic Press, 1972, 159–175
33	H W KuhnA W Tucker. 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	P Y Lee. Geometric optimization for computer vision. Ph D Thesis. Canberra: Austral Nat Univ, 2005
35	G W Li, Y P Liu, J Yin, Z L Shi. Planar object recognition based on Riemannian manifold. Acta Autom Sin 2010; 36(4): 465–474
36	S Lucidi, F Rochetich, M Roma. Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization. SIAM J Optim 1998; 8(4): 916–939
37	D G Luenberger. Introduction to Linear and Nonlinear Programming. Reading, MA: Addison Wesley, 1972
38	D G LuenbergerY Y Ye. Linear and Nonlinear Programming, 3rd ed. New York: Springer Science+Business Media, 2008
39	Y Ma, J Košecká, S Sastry. Optimization criteria and geometric algorithms for motion and structure estimation. Int J Comput Vis 2001; 44(3): 219–249
40	J H Manton. Optimization algorithms exploiting unitary constraints. IEEE Trans Signal Process 2002; 50(3): 635–650
41	J M Martìnez, R F Santos. An algorithm for solving nonlinear least-squares problems with a new curvilinear search. Computing 1990; 44(1): 83–90
42	G P McCormick. A modification of Armijo’s step-size rule for negative curvature. Math Program 1977; 13(1): 111–115
43	N Meggido. 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	S Mehrotra. On the implementation of a primal-dual interior point method. SIAM J Optim 1992; 2(4): 575–601
45	S Mizuno, M Todd, Y Y Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Math Oper Res 1993; 18(4): 964–981
46	R D C Monteiro, I Adler, M G C Resende. 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	J J Moré, D C Sorensen. 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	J NocedalS J Wright. Numerical Optimization. New York: Springer-Verlag, 1999
50	A Olivares, J M Moguerza, F J Prieto. Nonconvex optimization using negative curvature within a modified linesearch. European J Oper Res 2008; 189(3): 706–722
51	T Rapcsák. Geodesic convexity in nonlinear optimization. J Optim Theory Appl 1991; 69(1): 169–183
52	W Ring, B Wirth. Optimization methods on Riemannian manifolds and their application to shape space. SIAM J Optim 2012; 22(2): 596–627
53	S T Smith. Geometric optimization methods for adaptive filtering. Ph D Thesis. Cambridge, MA: Harvard University, 1993
54	S T Smith. 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	W Y Sun, Q Y Zhou. An unconstrained optimization method using nonmonotone second order Goldstein’s line search. Sci China Math 2007; 50(10): 1389–1400
56	A L Tits, A Wachter, S Bakhtiari, T J Urban, C T Lawrence. 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	C Udrişte. Convex Functions and Optimization Methods on Riemannian Manifolds. Mathematics and Its Applications, Vol 297. Dordrecht: Kluwer Acad Publ, 1994
58	J F Vasconcelos, G Elkaim, C Silvestre, P Oliveira, B Cardeira. Geometric approach to strapdown magnetometer calibration in sensor frame. IEEE Trans Aerosp Electron Syst 2011; 47(2): 1293–1306
59	S J Wright. Primal-dual Interior-point Methods. Philadelphia, PA: SIAM, 1997
60	X M Yang, H W Liu, C H Liu. Arc-search interior-point algorithm. J Jilin Univ Sci 2014; 52(4): 693–697
61	Y G Yang. Robust system design: pole assignment approaches. Ph D Thesis. College Park, MD: Univ Maryland, 1996
62	Y G Yang. Globally convergent optimization algorithms on Riemannian manifolds: uniform framework for unconstrained and constrained optimization. J Optim Theory Appl 2007; 132(2): 245–265
63	Y G Yang. Arc-search path-following interior-point algorithms for linear programming. Optimization Online, 2009
64	Y G Yang. A polynomial arc-search interior-point algorithm for convex quadratic programming. European J Oper Res 2011; 215(1): 25–38
65	Y G Yang. A polynomial arc-search interior-point algorithm for linear programming. J Optim Theory Appl 2013; 158(3): 859–873
66	Y G Yang. A globally and quadratically convergent algorithm with efficient implementation for unconstrained optimization. Comput Appl Math 2015; 34(3): 1219–1236
67	Y G Yang. Attitude determination using Newton’s method on Riemannian manifold. Proc IMechE Part G. J Aerosp Eng 2015; 229(14): 2737–2742
68	Y G Yang. 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	G Yang Yi. 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	Y Y Ye. Interior-point Algorithms: Theory and Analysis. New York: John Wiley & Sons, 1997
71	J J Zhang, J Cao, Y Y Wang. Gradient algorithm on Stiefel manifold and application in feature extraction. J Radars 2013; 2(3): 309–313
72	Q Y Zhou, W Y Sun. A nonmonotone second-order steplength method for unconstrained minimization. J Comput Math 2007; 25(1): 104–112

[1]	ZHOU Qunyan, SUN Wenyu. Adaptive nonmonotone line search method for unconstrained optimization[J]. Front. Math. China, 2008, 3(1): 133-148.

Viewed

Full text

Abstract

Cited

Shared

Discussed