諧波平衡法(Harmonic balance,簡稱HB)可用於分析以及預測週期性穩態解。
然而，由於HB的非凸性，我們很難從頻域上找出解決HB問題的最佳方案。
此外，現實許多案例遇到的主要困難為大尺度最佳化的計算成本。
本篇論文將討論三種解決方案。
第一種方法是在最佳化的過程中，透過半正定規劃(semidefinite programming, 簡稱SDP)預測週期解。
第二種方法則是進一步利用HB問題中SDP的稀疏特性，將較大的SDP矩陣分解成數個更小的SDP矩陣，以此加快計算速度。
從模擬結果來看，這種方式加快了3至7.5倍的運算效能，而且也大大地降低了決策變數的個數。
第三種方案，我們提出了一個基於交替方向乘子法(Alternating Direction Method of Multipliers, 簡稱ADMM)的最佳化演算法，此法核心概念是將大尺度的最佳化問題分解成數個較小的子問題，進而加快問題的解決速度。
記憶體與運算時間的減少使得最佳化演算法能處理更大尺度的問題。

The harmonic balance (HB) method is broadly employed for analyzing and predicting the periodic steady-state solution.
However, finding a global solution to the HB problem in the frequency domain is difficult due to its nonconvexity.
In addition, the computational cost of solving large-scale optimization poses a major challenge for the application in many real-world practical cases.
This dissertation introduces a novel optimization-based approach in the form of semidefinite programming to predict periodic solution.
The structural sparsity in the HB problem is exploited to improve numerical tractability and efficiency at the cost of adding smaller-sized semidefinite constraints in the problem formulation.
After exploiting sparsity, the simulation results show an improvement rate of 3 to 7.5 times for larger instance problems and the number of decision variables are greatly reduced.
We also proposed an optimization approach based on Alternating Direction Method of Multipliers for solving the HB problem.
This method consists in breaking down a large-scale optimization problem into several smaller subproblems, resulting in a significant speedup in the computational time.
The reduction in both computational cost and memory occupation allows the algorithm to solve larger-sized problems.

[1] C. Hayashi, Nonlinear Oscillations in Physical Systems. Princeton, NJ, USA: Princeton University Press, 1986.
[2] T. Detroux, L. Renson, L. Masset, and G. Kerschen, “The harmonic balance method for bifurcation analysis of large-scale nonlinear mechanical systems,” Computer Methods in Applied Mechanics and Engineering, vol. 296, pp. 18–38, 2015.
[3] R. Mestrom, R. Fey, J. Van Beek, K. Phan, and H. Nijmeijer, “Modelling the dynamics of a mems resonator: Simulations and experiments,” Sensors and Actuators A: Physical, vol. 142, no. 1, pp. 306–315, 2008.
[4] D. A. N. Jacobson, P. W. Lehn, and R. W. Menzies, “Stability domain calculations of period1 ferroresonance in a nonlinear resonant circuit,” IEEE Transactions on Power Delivery, vol. 17, no. 3, pp. 865–871, 2002.
[5] L. Liu, E. H. Dowell, and K. C. Hall, “A novel harmonic balance analysis for the van der pol oscillator,” International Journal of Nonlinear Mechanics, vol. 42, no. 1, pp. 2–12, 2007.
[6] S. Dou and J. S. Jensen, “Optimization of nonlinear structural resonance using the incremental harmonic balance method,” Journal of Sound and Vibration, vol. 334, pp. 239–254, 2015.
[7] G. Von Groll and D. J. Ewins, “The harmonic balance method with arclength
continuation in rotor stator contact problems,” Journal of Sound and Vibration, vol. 241, no. 2, pp. 223–233, 2001.
[8] L. Xie, S. Baguet, B. Prabel, and R. Dufour, “Bifurcation tracking by harmonic balance method for performance tuning of nonlinear dynamical systems,” Mechanical Systems and Signal Processing, vol. 88, pp. 445–461, 2017.
[9] M. Akhmet and M. Fen, “Chaotic period-doubling and ogy control for the forced duffing equation,” Communications in Nonlinear Science and Numerical Simulation, vol. 17, no. 4, pp. 1929–1946, 2012.
[10] B. Bao, P. Wu, H. Bao, Q. Xu, and M. Chen, “Numerical and experimental confirmations of quasiperiodic behavior and chaotic bursting in third-order
autonomous memristive oscillator,” Chaos, Solitons & Fractals, vol. 106, pp. 161–170, 2018.
[11] Q. Wang, S. Yu, C. Li, J. Lü, X. Fang, C. Guyeux, and J. M. Bahi, “Theoretical design and FPGA-based implementation of higher-dimensional digital chaotic systems,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 63, no. 3, pp. 401–412, 2016.
[12] L. Charroyer, O. Chiello, and J.J. Sinou, “Self-excited vibrations of a nonsmooth contact dynamical system with planar friction based on the shooting method,” International Journal of Mechanical Sciences, vol. 144, pp. 90–101, 2018.
[13] L. Hou, Y. Chen, Y. Fu, H. Chen, Z. Lu, and Z. Liu, “Application of the hb-aft
method to the primary resonance analysis of a dual-rotor system,” Nonlinear Dynamics, vol. 88, no. 4, pp. 2531–2551, 2017.
[14] F. Bizzarri, A. Brambilla, and L. Codecasa, “Harmonic balance based on two-step
galerkin method,” IEEE Transactions on Circuits and Systems I: Regular Papers,
vol. 63, no. 9, pp. 1476–1486, 2016.
[15] M. Sharma, N. A. Wukie, M. Ugolotti, and M. G. Turner, “Unsteady turbomachinery
simulations using harmonic balance on a discontinuous galerkin discretization,” in Proceedings of ASME Turbo Expo 2018, pp. 1–14, 2018.
[16] M. Krack and J. Gross, Harmonic Balance for Nonlinear Vibration Problems. New
York, NY, USA: Springer, 2019.
[17] W. Yao and S. Marques, “Prediction of transonic limit cycle oscillations using an aeroelastic harmonic balance method,” AIAA Journal, vol. 53, no. 7, pp. 2040–2051, 2015.
[18] K. C. Hall, K. Ekici, J. P. Thomas, and E. H. Dowell, “Harmonic balance methods
applied to computational fluid dynamics problems,” International Journal of Computational Fluid Dynamics, vol. 27, no. 2, pp. 52–67, 2013.
[19] D. Tang, C. Lim, L. Hong, J. Jiang, and S. Lai, “Dynamic response and stability analysis with newton harmonic balance method for nonlinear oscillating dielectric elastomer balloons,” International Journal of Structural Stability and Dynamics, vol. 18, no. 12, pp. 1850152, 2018.
[20] A. Grolet and F. Thouverez, “On a new harmonic selection technique for harmonic
balance method,” Mechanical Systems and Signal Processing, vol. 30, pp. 43–60, 2012.
[21] A. Leung, H. Yang, and Z. Guo, “The residue harmonic balance for fractional-order van der pol like oscillators,” Journal of Sound and Vibration, vol. 331, no. 5, pp. 1115–1126, 2012.
[22] P. Ju, “Global residue harmonic balance method for helmholtz-duffing
oscillator,” Applied Mathematical Modelling, vol. 39, no. 8, pp. 2172–2179, 2015.
[23] Y. Cheung, S. Chen, and S. Lau, “Application of the incremental harmonic balance method to cubic nonlinearity systems,” Journal of Sound and Vibration, vol. 140, no. 2, pp. 273–286, 1990.
[24] H. Liao and W. Sun, “A new method for predicting the maximum vibration amplitude of periodic solution of nonlinear system,” Nonlinear Dynamics, vol. 71, no. 3, pp. 569–582, 2013.
[25] T. M. Cameron and J. Griffin, “An alternating frequency/time domain method for calculating the steady-state response of nonlinear dynamic systems,” Journal of Applied Mechanics, vol. 56, no. 1, pp. 149–154, 1989.
[26] H. Liao, “An approach to construct the relationship between the nonlinear normal mode and forced response of nonlinear systems,” Journal of Vibration and Control, vol. 22, no. 14, pp. 3169–3181, 2016.
[27] C. K. Luk and G. Chesi, “On the estimation of the domain of attraction for discrete-time switched and hybrid nonlinear systems,” International Journal of Systems Science, vol. 46, no. 15, pp. 2781–2787, 2015.
[28] X. Bai, H. Wei, K. Fujisawa, and Y. Wang, “Semidefinite programming for optimal
power flow problems,” International Journal of Electrical Power & Energy Systems,
vol. 30, no. 67, pp. 383–392, 2008.
[29] S. P. Tarasov and M. N. Vyalyi, “Semidefinite programming and arithmetic circuit evaluation,” Discrete applied mathematics, vol. 156, no. 11, pp. 2070–2078, 2008.
[30] D. Henrion and J. . Lasserre, “Convergent relaxations of polynomial matrix inequalities and static output feedback,” IEEE Transactions on Automatic Control, vol. 51, no. 2, pp. 192–202, 2006.
[31] T. Tanaka, P. M. Esfahani, and S. K. Mitter, “LQG control with minimum directed information: Semidefinite programming approach,” IEEE Transactions on Automatic Control, vol. 63, no. 1, pp. 37–52, 2018.
[32] R. Deits and R. Tedrake, “Computing large convex regions of obstacle-free
space through semidefinite programming,” in Algorithmic foundations of robotics XI, vol. 107 of Springer Tracts in Advanced Robotics, pp. 109–124, Cham, Switzerland: Springer, Cham, 2015.
[33] J.B. Lasserre, Moments, Positive Polynomials and Their Applications. London, UK:
Imperial College Press, 2009.
[34] J. B. Lasserre, An Introduction to Polynomial and SemiAlgebraic
Optimization. Cambridge, UK: Cambridge University Press, 2015.
[35] H. Waki, S. Kim, M. Kojima, and M. Muramatsu, “Sums of squares and semidefinite
program relaxations for polynomial optimization problems with structured sparsity,”
SIAM Journal on Optimization, vol. 17, no. 1, pp. 218–242, 2006.
[36] M. Kojima, S. Kim, and H. Waki, “Sparsity in sums of squares of polynomials,” Mathematical Programming, vol. 103, no. 1, pp. 45–62, 2005.
[37] D. Gabay and B. Mercier, “A dual algorithm for the solution of nonlinear variational problems via finite element approximation,” Computers & mathematics with applications, vol. 2, no. 1, pp. 17–40, 1976.
[38] J. Eckstein and W. Yao, “Augmented lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results,” Tech. Rep. 32, Rutgers Center for Operations Research Rutgers University, Piscataway, NJ, USA, 2012.
[39] S. P. Boyd, N. Parikh, and E. Chu, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1–122, 2010.
[40] C. H. Yang and B. S. Deng, “A semidefinite programming approach for harmonic balance method,” IEEE Access, vol. 7, pp. 99207–99216, 2019.
[41] C. Yang and B. S. Deng, “Exploiting sparsity in SDP relaxation for harmonic balance method,” IEEE Access, vol. 8, pp. 115957–115965, 2020.
[42] S. P. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge
university press, 2004.
[43] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, vol. 15 of SIAM Studies in Applied Mathematics. Philadelphia, PA, USA: SIAM, 1994.
[44] J. Lofberg, “Yalmip : a toolbox for modeling and optimization in Matlab,” in 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508), pp. 284–289, 2004.
[45] M. Grant and S. Boyd, “Cvx: Matlab software for disciplined convex programming,
version 2.1,” 2014.
[46] M. Laurent, “Semidefinite programming in combinatorial and polynomial optimization,”Nieuw Archief voor Wiskunde, vol. 4, pp. 256–262, 2008.
[47] J. F. Sturm, “Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones,” Optimization methods and software, vol. 11, no. 14,
pp. 625–653, 1999.
[48] R. H. Tütüncü, K.C. Toh, and M. J. Todd, “Solving semidefinite-quadratic-linear
programs using sdpt3,” Mathematical Programming, vol. 95, no. 2, pp. 189–217, 2003.
[49] M. ApS, The MOSEK Optimization Toolbox for MATLAB Manual. Version 9.0., 2019.
[50] K. G. Murty and S. N. Kabadi, “Some NP-complete problems in quadratic and nonlinear programming,” Tech. Rep. 8523, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI, USA, 1985.
[51] P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, Pasadena, CA, USA, 2000.
[52] M.D. Choi, T. Y. Lam, and B. Reznick, “Sums of squares of real polynomials,” in Proceedings of Symposia in Pure mathematics, vol. 58.2, pp. 103–126, 1995.
[53] S. Prajna, A. Papachristodoulou, and P. A. Parrilo, “Introducing sostools: a general purpose sum of squares programming solver,” in Proceedings of the 41st IEEE Conference on Decision and Control, 2002., vol. 1, pp. 741–746, 2002.
[54] C. Josz and D. Henrion, “Strong duality in lasserre’s hierarchy for polynomial optimization,”Optimization Letters, vol. 10, no. 1, pp. 3–10, 2016.
[55] D. Henrion and J.B. Lasserre, “Gloptipoly: Global optimization over polynomials with Matlab and sedumi,” ACM Transactions on Mathematical Software (TOMS), vol. 29,
no. 2, pp. 165–194, 2003.
[56] P. Tseng, “Second-order cone programming relaxation of sensor network localization,”SIAM Journal on Optimization, vol. 18, no. 1, pp. 156–185, 2007.
[57] T. N. Davidson, ZhiQuan Luo, and J. F. Sturm, “Linear matrix inequality formulation of spectral mask constraints with applications to fir filter design,” IEEE Transactions on Signal Processing, vol. 50, no. 11, pp. 2702–2715, 2002.
[58] H. K. Khalil, Nonlinear Systems, vol. 3rd ed. Upper Saddle River, NJ, USA: Prentice hall, 2002.
[59] A. Buscarino, C. Corradino, L. Fortuna, and L. O. Chua, “Taming spatiotemporal chaos in forced memristive arrays,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 12, pp. 2947–2954, 2018.
[60] C. Josz and D. K. Molzahn, “Lasserre hierarchy for large scale polynomial optimization in real and complex variables,” SIAM Journal on Optimization, vol. 28, no. 2, pp. 1017–1048, 2018.
[61] R. A. Jabr, “Exploiting sparsity in SDP relaxations of the OPF problem,” IEEE Transactions on Power Systems, vol. 27, no. 2, pp. 1138–1139, 2012.
[62] M. S. Andersen, L. Vandenberghe, and J. Dahl, “Linear matrix inequalities with chordal sparsity patterns and applications to robust quadratic optimization,” in 2010 IEEE International Symposium on ComputerAided Control System Design, pp. 7–12, 2010.
[63] S. Kim, M. Kojima, and H. Waki, “Exploiting sparsity in SDP relaxation for sensor network localization,” SIAM Journal on Optimization, vol. 20, no. 1, pp. 192–215, 2009.
[64] J. R. Blair and B. Peyton, “An introduction to chordal graphs and clique trees,” in Graph theory and sparse matrix computation, vol. 56 of The IMA Volumes in Mathematics and its Applications, pp. 1–29, New York, NY, USA: Springer, 1993.
[65] L. Vandenberghe and M. S. Andersen, “Chordal graphs and semidefinite optimization,” Foundations and Trends in Optimization, vol. 1, no. 4, pp. 241–433, 2015.
[66] M. Fukuda, M. Kojima, K. Murota, and K. Nakata, “Exploiting sparsity in semidefinite programming via matrix completion i: General framework,” SIAM Journal on Optimization, vol. 11, no. 3, pp. 647–674, 2001.
[67] D. J. Rose, “Triangulated graphs and the elimination process,” Journal of Mathematical Analysis and Applications, vol. 32, no. 3, pp. 597–609, 1970.
[68] M. Fukuda, M. Kojima, K. Murota, and K. Nakata, “Exploiting sparsity in semidefinite programming via matrix completion i: general framework,” SIAM Journal on Optimization, vol. 11, pp. 647–674, 2000.
[69] A. Griewank and P. L. Toint, “On the existence of convex decompositions of partially separable functions,” Mathematical Programming, vol. 28, pp. 25–49, 1984.
[70] R. Grone, C. R. Johnson, E. M. Sá, and H. Wolkowicz, “Positive definite completions of partial hermitian matrices,” Linear algebra and its applications, vol. 58, pp. 109–124, 1984.
[71] K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto, and M. Yamashita, “User’s manual for sparsecolo: conversion methods for sparse conic form linear optimization problems,” tech. rep., Research Report B453, Department of Mathematics and Computer Science, Tokyo Institute of Technology, OhOkayama,Meguroku, Tokyo, 2009.
[72] M. S. Andersen and L. Vandenberghe, CHOMPACK: A Python Package for Chordal
Matrix Computations, Version 2.1, 2014.
[73] M. Rewienski and J. White, “A trajectory piecewiselinear approach to model order reduction and fast simulation of nonlinear circuits and micromachined devices,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, vol. 22, no. 2, pp. 155–170, 2003.
[74] C. Gu, “Qlmor: A projection-based nonlinear model order reduction approach using-quadratic linear representation of nonlinear systems,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, vol. 30, no. 9, pp. 1307–1320, 2011.
[75] L. Vandenberghe and S. Boyd, “Semidefinite Programming,” SIAM review, vol. 38,
no. 1, pp. 49–95, 1996.
[76] R. Madani, A. Kalbat, and J. Lavaei, “A low-complexity parallelizable numerical algorithm for sparse semidefinite programming,” IEEE Transactions on Control of Network Systems, vol. 5, no. 4, pp. 1898–1909, 2018.
[77] N. J. Higham, “Computing a nearest symmetric positive semidefinite matrix,” Linear algebra and its applications, vol. 103, pp. 103–118, 1988.
[78] Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, “Chordal decomposition in operator-splitting methods for sparse semidefinite programs,” Mathematical Programming, vol. 180, no. 1, pp. 489–532, 2020.