New theory to find the global optimum for nonconvex optimization problems

Katoh, Hisao

doi:10.51094/jxiv.159

##article.authors##

Katoh, Hisao Freelance

DOI:

https://doi.org/10.51094/jxiv.159

キーワード:

nonconvex optimization、 global optimum、 probability-one homotopy method、 minimax theorem、 fixed point theorem

抄録

This paper proposes a new theory for calculating the global optimum of
nonconvex optimization problem.
Key idea used in this paper is a combination of probability-one homotopy method and von Neumann's minimax theorem.
Brouwer's fixed point theorem is used for the connection of these two theories.

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

I.I.Dikin, "Iterative solutions of problems of linear and quadratic programming," Soviet Mathematics Doklady, vol.8, pp.674-675, 1967.

Khachiyan, "A polynomial algorithm in linear programming," Soviet Mathematics Doklady, vol.20, pp.191-194, 1979.

N.Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatrica, vol. 4, pp.373-395, 1984.

P.Gahinet and P.Apkarian, "A LMI-based parametrization of all H_infinity controllers with applications," Proc. IEEE Conf. on Decision and Control, San Antonio, Texas, 1993, pp.656-661.

S.Boyd, L.E.Ghaoui, E.Feron and V.Balakrishnan, Linear Matrix Inequalities and Control Theory. SIAM, Philadelphia, PA, 1994.

W.Karush, "Minima of functions of several variables with inequalities as side conditions," Master's Thesis, University of Chicago, 1939.

H.W.Kuhn and A.W.Tucker, "Non-linear programming," in Proc. Second Berkley Symposium on Mathematical Statistics and Probability, University of California Press, 1951, pp.481-493.

S.N.Chow, J.Marret-Paret and J.A.Yorke, "Finding zeros of maps: homotopy methods that are constructive with probabilitu one," Mathematics of computation, vol. 32, pp.887-899, 1978.

L.T.Watson, "Probability-one homotopies in computational science," Journal of Computational and Applied Mathematics, vol. 140, pp. 785-807, 2002.

L.T.Watson, S.C.Billups and J.P.Morgan, "HOMPACK: a suite of codes for globally convegent homotopy algorithm," ACM Trans. Math. Software, vol. 31, pp. 281-310, 1987.

J.von Neumann and O.Morgenstern, Theory of games and economic behavior. Princeton University Press, Princeton, NJ, 1944.

D.P.Bertsekas, Convex Optimization Theory. Universities Press, India, 2010.

T.H.Kjeldsem, "John von Neumann's conception of the minimax theorem: a journey through different mathematical context," Arch. Hist. Exact Sci., vol. 56, pp. 39-68, 2001 .

L.E.J.Brouwer, "Uber Abbinldungen von Mannigfaltigkeiten," Math. Ann. vol. 71, pp. 97-115, 1912.

E.K.P.Chong and S.H.Zak, An Introduction to Optimization. 2nd edition, Wily and Sons, New York, NY, 2001.

R.A.Horn and C.R.Johnson, Matrix Analysis. Cambridge University Press, New York, NY, 1985.

M.Danilova, P.Dvurechensky, A.Gasnikov, E.Gorbunov, S.Guminov, D.Kamzolov and I.Shibaev, "Recent Theoretical Advances in Non-Convex Optimization," arXiv preprint arXiv:2012.06188, 2020.

Y.Li, K.Lee and Y.Bresler, "Identifiability in blind deconvolution with subspace or sparsity constraints," IEEE Transactions on Information Theory, vo.62, no.7, pp.4266-4275, 2016.

E.J.candes and T.Tao, "Decoding by linear programming," IEEE Transactions on Information Theory, vol.51, no.12, pp.4203-4215, 2005.

W.Tao, Z.Pan, G.Gu and Q.Tao, "Primal averaging: a new gradient evaluation step to attein the optimal individual convergence," IEEE Transactions on Cybernetics, vol.50, no.2, pp.835-845, 2018.