Icke konvexa optimeringsproblem stöter ofta på i mycket av statistik, affärer, vetenskap och teknik, men de är ännu inte allmänt erkända som en teknik. En orsak till denna relativt låga popularitet är bristen på ett väl utvecklat system av teori och algoritmer för att stödja applikationerna, som är fallet för dess konvexa motsvarighet. Detta dokument syftar till att ta ett steg i riktning mot disciplinerad icke konvex optimering. I synnerhet anser vi i detta dokument vissa begränsade icke konvexa optimeringsmodeller i block beslut variabler, med eller utan kopplade affina begränsningar. I avsaknad av kopplade begränsningar uppvisar vi en sublinjär konvergenshastighet till en -stationär lösning i form av variationell ojämlikhet för en generaliserad villkorad gradientmetod, där konvergenskvoten visas vara beroende av den Hölderianska kontinuiteten i gradienten för den släta delen av målet. För modellen med kopplade affina begränsningar, introducerar vi motsvarande -stationaritet villkor, och föreslå två proximala-typ varianter av ADMM för att lösa en sådan modell, förutsatt att de proximala ADMM uppdateringar kan genomföras för alla blockvariabler utom för det sista blocket, för vilka antingen en gradient steg eller en majorization-minimization steg genomförs. Vi visar en iteration komplexitet bunden av O(1/2 ) för att nå en -stationär lösning för båda algoritmer. Dessutom visar vi att samma iteration komplexitet av en proximal BCD-metod följer omedelbart. Numeriska resultat ges för att illustrera effekten av de föreslagna algoritmerna för tensor robust PCA.
Nyligen, Jiang et al. REF har föreslagit två varianter av ADMM-typ för att lösa de strukturerade icke-konvexa och icke-smooth-problemen.
Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}