Debian Codegraph @

texmf-dist/doc/pdftex/tests/38-interword-space-at-font-switch/a3.tex

raw
1 \documentclass[a4paper,11pt]{article}
2
3 %\usepackage[margin=1in]{geometry}
4 \usepackage[utf8]{inputenc}
5 \usepackage{amsthm,amsmath,amssymb}
6 \usepackage{tikz}
7 \usepackage{graphicx,subcaption,caption}
8 \usepackage{algorithm,algorithmic}
9 \usepackage{pgfplots}
10 \usepackage{multirow}
11 \usepackage[T1]{fontenc}
12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13 %% If your tex system is less than 2 years old (in 2012) the following
14 %% font options are available. If not comment them out.
15 \usepackage{tgtermes}
16 % otherwise use alternative journal fonts
17 %\renewcommand{\rmdefault}{ptm} % system default Times font
18 \usepackage{mathptmx}
19 %%% additional fonts
20 \usepackage[scaled=.92]{helvet}
21 %\setoptfont{enc={T1},fam={pop}} % if You have Optima font, uncomment this line
22 %%% MATH
23 %\usepackage{amsthm,amsmath,amssymb}
24 \usepackage{mathrsfs}
25 %%% BIBLIOGRAPHY
26 %\usepackage{natbib} %% numbers is required.
27 %%% LINKS
28 \usepackage[colorlinks,citecolor=blue,urlcolor=blue]{hyperref} %%check
29
30 \usepackage{enumerate}
31
32 %\artstatus{am} %%% leave this alone!! That means you, too!!
33 %%%%%%%%theorems%%%%%
34
35 %%%% feel free to changes these%%%%%%%
36 \newtheorem{theorem}{Theorem}[section]
37 \newtheorem{lemma}[theorem]{Lemma}
38 \newtheorem{problem}[theorem]{Problem}
39 \newtheorem{conjecture}[theorem]{Conjecture}
40 \newtheorem{condition}[theorem]{Condition}
41 \newtheorem{claim}[theorem]{Claim}
42 \newtheorem{question}[theorem]{Question}
43 \newtheorem{corollary}[theorem]{Corollary}
44 \theoremstyle{definition}
45 \newtheorem{definition}[theorem]{Definition}
46 \newtheorem{statement}[theorem]{Statement}
47 \newtheorem{notation}[theorem]{Notation}
48 \theoremstyle{remark}
49 \newtheorem{remark}[theorem]{Remark}
50
51
52 %\tikzexternalize
53 %\newtheorem{theorem}{Theorem}
54 %\newtheorem{proposition}{Proposition}
55 %\newtheorem{lemma}{Lemma}
56 %\newtheorem{assumption}{Assumption}
57 %\newtheorem{remark}{Remark}
58 %\newtheorem{corollary}{Corollary}
59 %\newtheorem{definition}{Definition}
60 %\usepackage{hyperref}
61 %\providecommand{\keywords}[1]{\textbf{\textit{Keywords---}} #1}
62
63 %\firstpageno{1}
64
65 \begin{document}
66 % \begin{frontmatter}
67 \title{Computability of Approximate Optima of Nonconvex Functions}
68 \author{K. Lakshmanan \\ Department of Computer Science and Engineering, \\ Indian Institute of Technology (BHU) Varanasi, 221005 India. \\ Email: [email protected]}
69 \date{}
70
71 \maketitle
72
73 \begin{abstract}
74 It is known that finding approximate optima of non-convex functions is intractable. We give a simple proof to show that this problem is not even computable. \\
75 \textbf{Keywords:} Computablity of Approximate Optima, Non-convex functions
76 \end{abstract}
77
78 \section{Introduction and Preliminaries}
79 We consider the problem of finding the global minima of a non-convex continuous function $f: C \rightarrow \mathbb{R}$, where $ C \subset \mathbb{R}^d$ is a closed, compact subset. Global minima is the point $x^* \in C$ which satisfies the following property: $f(x^*) \leq f(x)$ for all $x \in C$. The function $f$ attains this minimum at least once by extreme value theorem. Our goal is to find one such point. This problem is well-studied with many books written on the subject, see for example \cite{globook}.
80
81 We note that we consider an oracle setting, where the function values are given by an oracle. This is different from the computablity of optima computable real functions studied for example in \cite{pour}. It is easy to see that a simple grid search will output a sequence of points converging to the global optima. And for a Lipschitz continuous function, it requires an exponential number of oracle calls \cite{nest} if the Lipschitz constant is known. % that the approximations to optima are not computable too. %This is also the case if we are looking for points close to approximate optima.
82
83 Let us define $S = \{x||f(x)-f(x^*)|\leq \epsilon\}$ and term the members of $S$ as $\epsilon$-optima. In optimization literature \cite{foster2019complexity,zhang2020complexity}, it is known that finding approximations to optima is not tractable for non-convex functions. For non-convex functions, $\epsilon$-stationary point which is weaker than $\epsilon$-optima is also known to be not tractable \cite{zhang2020complexity}. We show more in this paper, that this set $S$ is not computable. This is much stronger than saying they it is intractable. We assume for formality finite-precision numbers. This assumption of finite-precision numbers is useful to model real-world systems and we show is not restrictive.
84
85 %and $T = \{y|\exists x \mbox{ s.t., } |x-y| \leq \delta \mbox{ and } |f(x)-f(x^*)|\leq \epsilon \}$.
86 % and that of $T$ as $(\epsilon,\epsilon)$-optima.
87 %Our proof is through simple reductions.
88
89 %\begin{table}[ht]\label{table1}
90 % \centering
91 % \begin{tabular}{|p{4cm}|c c|}
92 % \hline
93 % \multirow{2}{*}{Function Type} & \multicolumn{2}{c}{Function Oracle} \\
94 % & Yes & No \\
95 % \hline
96 % Computable-Real & No & No \\
97 % Computable-Real (Isolated minimum) & \multirow{2}{*}{Yes} & \multirow{2}{*}{Yes}\\
98 % Lipschitz Continuous & Yes & No \\
99 % Differentiable/Smooth & No & No \\
100 % Continuous & No & No \\
101 % \hline
102 % \end{tabular}
103 % \caption{Computable Convergence to Global Minimum }
104 % \label{tab1}
105 %\end{table}
106
107 \subsection{Finite Precision Reals}
108 We now briefly explain what we mean by this.
109 Consider any real number $x \in \mathbb{R}$. Let $r_0$ be the largest integer such that $r_0 \leq x$. Having chosen $r_0,r_1,\ldots,r_{k-1}$ choose largest positive integer $r_k$ such that
110 \[ r_0 + \frac{r_1}{10} + \frac{r_2}{10^2} + \ldots \frac{r_k}{10^k} \leq x. \]
111
112 This is the decimal expansion of the number. We can check that this expansion is unique. We define precision length to be the number $k$.
113 Now for finite precision representaion of a real we need to specify this precision length $k$. And we say for any real $x \in \mathbb{R}$, the numbers $r_0,r_1,\ldots,r_k$ is its finite precision representation. Note that $r_i, 0\leq i \leq k$ can be zero. %We can consider this finite-precision real number as a natural number by representing it as $r_0*10^k+r_1*10^{k-1}+\ldots+r_k$. For $x \in \mathbb{R}^d$,%all finite-precision lengths of its coordinates.
114 For a point $x \in \mathbb{R}^d$, given a precision length $k$ we can have decimal expansions for all it's co-ordinates.
115 Note that though we give binary representations to the Turing machine, for simplicity we assume precisions denote the decimal precisions.
116
117 \begin{remark}\label{gaprem}
118 Suppose $r_1,\ldots,r_k$ is the finite precision representation with length $k$ of some real $x$. Let $\bar x$ be the number with decimal expansion $r_1,\ldots,r_k$ as $x$ and $r_{l}=9$ for $l \geq k+1$. And let $\underline x$ be the number with decimal expansion $r_1,\ldots,r_k$ as $x$ and $r_{l}=0$ for $l \geq k+1$. %We can see that for all reals in $[\underline x,\bar x]$ we have the same finite length representation.
119 And the length of this interval $[\underline x,\bar x]$ is $\epsilon = 10^{-k}$. We then say with precision length $k$ we can represent consecutive numbers with gap greater than or equal to $\epsilon$.
120 \end{remark}
121
122 \subsection{The Problem}
123 We assume there is an oracle for our continuous function $f$. This oracle gives the value $f(x)$ up to any finite-precision for an given finite-precision $x$. The Turing-machine has access to this function oracle. We give also give a value $\epsilon > 0$ as input to the Turing machine. Our main problem is to write any point $x_{o}$ of the finite precision length such that $|f(x_{o})-f(x*)| < \epsilon$ i.e., it should find $\epsilon-$ approximation of the global optima. We show that this problem is not computable.
124
125 Let us assume we have a three-tape Turing machine, one is used for calculations, second is for the giving the finite precision real and the precision length required to the function oracle and third one has the value returned from the oracle \cite{sorbook}. Note that the third tape can also store the previous values. That is suppose we start with $x_0$ and find $x_1,\ldots,x_{k}$ this tape can store all these and also the corresponding function values obtained from the function oracle $f(x_0),\ldots,f(x_k)$ for finding $x_{k+1}$. We now give definition of the standard Turing machine here:
126
127 \begin{definition}
128 Turing machine has a three infinite tapes divided into cells, a reading head which scans one cell of the tape at a time, and a finite set of internal states $Q=\{q_0,q_1,\ldots,q_n\}, \, n \geq 1$. Each cell is either blank or has symbol 1 written on it. In a single step the machine may simultaneously (1) change the from one state to another; (2) change the scanned symbol $s$ to another symbol $s'\in S = \{1,B\}$; (3) move the reading head one cell to the right (R) or left (L). This operation of machine is controlled by a partial map $\Gamma : Q \times S^3 \rightarrow Q \times (S \times \{R,L\})^3$.
129 \end{definition}
130
131 \begin{remark}
132 The map $\Gamma$ viewed as a finite set of quintuples is called a Turing program. The interpretation is that if $(q,s_1,s_2,s_3,q',s'_1,X_1,s'_2,X_2,s'_3,X_3) \in \Gamma$, in state $q$, scanning symbols $s_1, s_2, s_3$ changes state to $q'$ and in the tape $i$ input symbol to $s'_i$ and moves to scan one square to the right if $X_i=R$ (or left if $X_i=L$.) in the tape $i$.
133 \end{remark}
134
135 We consider this problem in the paper.
136
137 \begin{problem}
138 Given a continuous, nonconvex function $f$, is there a Turing machine with access to the function oracle which can find a $\epsilon-$ approximation to the global optima of the function $f$ ?
139 \end{problem}
140
141 \section{Main Theorem}
142
143 %Given a input $x$ of finite precision length $n$, the oracle can return $f(x)$ to any specified precision.
144 Given the objective function $f$, let the set of global minima be denoted by $G^f$. Now consider $\epsilon$-approximation to the global minima. %We consider finite length approximation of the set $G'_{\epsilon}$.
145
146 \begin{lemma}\label{preclem}
147 For all $\epsilon > 0$ there exists a point $x_n^*$ of finite precision length $n$ such that $|f(x^*)-f(x_n^*)| < \epsilon$.
148 \end{lemma}
149
150 \begin{proof}
151 Let $\delta > 0$ be such that $|x-y| < \delta$ implies $|f(x)-f(y)| < \epsilon$. Such an $\delta > 0$ exists for all $\epsilon > 0$ because the function $f$ is continuous. Let $n$ be the precision length required to represent numbers with gap $\epsilon/10$ between consecutive numbers (Remark \ref{gaprem}). Then we see for the global minima $x^*$ (like for all other points) it's finite precision representation $x_n^*$ with precision length $n$ is such that $|x_n^*-x^*|<\epsilon$.
152 \end{proof}
153
154 \begin{definition}
155 Let $G^f_{\epsilon,k}$ be the set of points with given finite precision length $k \geq 1$ where the function value is $\epsilon > 0$ close to the global minima. And $G^f_{\epsilon}$ be the union of all such sets.
156 \end{definition} % We show that this set $G'_{\epsilon}$ is not limit computable.
157 We consider only finite-precision numbers. %As the domain is a compact set, this can be regarded as a subset of natural numbers by multiplying by an appropriate constant. And in particular
158 As there are only finite number of points with precision length $k$, the set $G^f_{\epsilon,k}$ is finite.
159 Since we would like an algorithm to computably converge to a single point, for simplicity we assume the global optima is unique i.e., $G^f$ is a singleton. This is not uncommon in optimization literature as strict convexity gives unique local (global) minima and is assumed for objective functions. Now we state the main theorem.
160
161 \begin{lemma}\label{checklem}
162 There is no algorithm to check if a point $x_k$ is a $\epsilon-$ approximation to the global optima.
163 \end{lemma}
164
165 \begin{proof}
166 We consider an equivalent problem. We define
167 \begin{equation*}
168 h_{x_k}^{\epsilon}(x) := \max \{0,f(x_k)-f(x)-\epsilon\}.
169 \end{equation*}
170 Since our objective function $f$ is continuous, $h_{x_k}^{\epsilon}(\cdot)$ is also continuous.
171 This function is identically zero if and only if $|f(x_k) - f(x)| < \epsilon$, for all $x$. This happens only if $x_k$ is a $\epsilon-$ approximation to the optimum (See Figure \ref{illusfig}). Note that $x_k$ and $x$ are represented with some finite precision. % then $h_{x_k}^{\epsilon}(\cdot)$ is identically zero. %Or to find a finite-precision point $y$ which is $\epsilon-$ approximation to the optimum is same as finding a function $h_y^{\epsilon}(\cdot)$ which is identically zero for some $y$. But this cannot be checked for any particular value of $y$.
172 \begin{figure}[!ht]
173 \centering
174 % \includegraphics{fig1-crop.pdf}
175 \caption{The figure on the right shows a sample objective function. The figure of the left is the function $ \max \{0,f(60)-f(x) \}$. This function is not identically zero as $x=60$ is not the global minima of $f(x)$.}
176 \label{illusfig}
177 \end{figure}
178
179
180 Thus the set $G^f_{\epsilon}$ of all points with finite precision that are $\epsilon$ close to the global minima, is precisely the set of all points $x_k$ where the function $h_{x_k}^{\epsilon}(\cdot)$ is identically zero.
181 That is,
182 \[ x_k \in G^f_{\epsilon} \Leftrightarrow h_{x_k}^{\epsilon}(x) = 0 \mbox{ for all } x \in C \]
183 But this cannot be checked for a particular $x_k$ unless it is checked for all $x$ of any finite precision length. As there are infinitely many such points, there is no Turing machine which can compute (halt) if a function is zero at infinitely many points.
184 So given any point $x_k$, it is not possible to say if it is an $\epsilon-$ approximation to the global optima or not.
185 \end{proof}
186
187 \begin{theorem}\label{mainthm}
188 We assume the objective function we wish to minimize is known by its oracle. There is no algorithm which can compute the $\epsilon$-approximate optima of a continuous, non-convex objective function on a compact domain.
189 \end{theorem}
190
191 \begin{proof}
192 Let $x'_k$ be any point of some finite precision length $n_k$ such that $|f(x^*)-f(x'_k)| < \epsilon$. Such a point exists by Lemma \ref{preclem} i.e., the set $G^f_{\epsilon,n_k}$ is non-empty for $\epsilon > 0$. Suppose that we have an algorithm to find a $\epsilon/2-$ approximation point $x'_k$.% This length $n_k$ can increase with $k$.
193
194 Now for any point $x_k \in C$ we can say it is $\epsilon$ close to optimum if $|f(x_k)-f(x'_k)| < \epsilon/2$ else it is not. Thus we have an algorithm to check if a point is an $\epsilon-$ approximation to the global optima or not. This is a contradiction to Lemma \ref{checklem}. Thus for a $\epsilon > 0$, there is no algorithm to find a $\epsilon-$ approximation to the global optima.
195
196 %we can not compute any $N$ such that for all $n \geq N$ with $\{x_n\}$ having finite precision, $|f(x_n) - f(x^*)| < \epsilon$.
197 %In other words, we see that there is no computable sequence with finite precision length $\{ x_k \}$ converging to the global optimum (Definition \ref{ccdef}). Thus we have shown the theorem.
198 %there is no sequence of computable $\{x_k\}$ with finite-precision length converging to the global minima.
199 \end{proof}
200
201 \begin{corollary}
202 The finite-precision assumption is not restrictive. If there is an algorithm to find a general real number which is $\epsilon-$ approximation, we can take the first $k$ digits which gives $\epsilon-$ approximation to get a finite precision approximation. %If an algorithm outputs real vectors $\{x_k\}$ converging to the global minimum, then by taking the first $k$ digits of each co-ordinate in $x_k$ it can output a sequence of real vectors with finite-precision length converging to the same point. By contra-positive, if there is no algorithm which can output finite-precision points then there can be no algorithm which outputs any sequence of points converging to the global minimum.
203 \end{corollary}
204
205 %\begin{corollary}
206 % The problem of approximating the global minima of a continuous function by an arbitrary $\epsilon > 0$ is not computable.
207 %\end{corollary}
208
209 \begin{corollary}
210 The problem of checking whether local minima $z$ is global is not computable as this also involves checking whether $h_z^{\epsilon}(\cdot)$ is identically zero.
211 \end{corollary}
212
213 \begin{remark}
214 Even in presence of higher order oracles, i.,e oracles which give derivatives of the function, the equivalent problem of checking if $h_z^{\epsilon}(\cdot)$ is identically zero remains. Hence global optima even in presence of these higher-order function oracle is not computable. %(\#\#\# if bound on gradient is not known \~ Lipschitz)
215 \end{remark}
216
217 \begin{remark}
218 As we mentioned before, our result is for algorithms having access to the function oracle. This is different from the setting of computable function and reals studied in computable analysis. \cite{pour}
219 \end{remark}
220
221 \begin{remark}
222 As we can find an ball of some radius $\omega$ where the continuous function $h_z^{\epsilon}(\cdot)$ is non-zero around a local optima. The same proof does not hold for converging to local optima as we can check if $h_z^{\epsilon}(\cdot)$ is identically zero in steps of size less than $\omega$.
223 \end{remark}
224
225 \section{Global Optima Property}
226 In this section, we see a simple property a function satisfies if the global optima is computable. For this let us first define the set $G^f$ of global optima of the function $f:C\rightarrow \mathbb{R}$, $C\subset \mathbb{R}^d$ as
227 \[ G^f := \{x\,| \, \mbox{ for all } y, \, f(x) \leq f(y), \, x \in C \}.\]
228
229 This set $G^f$ is a subset of $C$. As we are interested in finding only one optima, we call $G^f$ computable if atleast one of it's member is. %We now claim that if the global optima is computable then function must satisfy a property of a particular form.
230
231 \begin{definition}
232 A function $f$ satisfies global property if there is a first order (3-ary) predicate $P_{\zeta}(y,x)$ and a $\zeta \in \mathbb{R}$ such that $P_{\zeta}(y,x)$ is True for all $y,x$ in the domain $C$ of the function $f$.
233 \end{definition}
234
235 We say a property $P_{\zeta}(y,x)$ can be computed if $\zeta$ in the definition can be computed.
236
237 \begin{definition}
238 A set of functions $\mathcal{F}$ satisfies a global property if there is a first order predicate $P_{\zeta}(y,x)$ satisfied by all the functions $\mathcal{F}$.% such that the predicate is True for all $y, x$ in the domain $C$ of the function $f$.
239 \end{definition}
240
241 %We represent True by 1 and False by 0. For example if we let
242 %We can see that this property $Q^f_{x^*}(y)$ defines the global minima and is satisfied by all continuous functions on compact domain.
243
244 %\begin{theorem}[Global Optima Property]
245 % There is a algorithm to converge to the global optima of a set of functions $\mathcal{F}$ if and only if there exists a computable global property $P_{\zeta} (y,x)$ that is satisfied by all the functions in $\mathcal{F}$.% for some computable $\zeta \in \mathbb{R}$. %satisfies the property $P_\zeta (y,x)$.% for all $y$ and $x$ in the domain $C$. Note that here the property $P^f_\zeta (y,x)$ need to be satisfied for all $x \in C$ not just the set $G^f$ of global optima.
246 %\end{theorem}
247
248 \begin{remark}
249 %Here we assume we are finding minima. There could be more than one global minima and we need to find one.
250 If the global minima is computable for a function $f$, we can easily define the $\zeta$ to be the norm of a member of $G^f$ which is computable, say $x^*$ and the global property to be
251 \[ P_{\zeta}(y,x) \mbox{ is True for all } x, \, y \mbox{ if there exists a } x \mbox{ s.t. } \parallel x \parallel = \zeta.\]
252 %\begin{table}[h]
253 % \centering
254 % \begin{tabular}{cl}
255 % \multirow{2}{1.4cm}{$P^f_{\zeta}(y,x) =$} &1 if $\parallel x \parallel = \zeta$ \\ %, \mbox{for some } x^* \in G^f, $ \\
256 % &0 o.w.
257 % \end{tabular}
258 %\end{table}
259 It is clear that if global optima is computable then this $P_{\parallel x^* \parallel}(y,x)$ is satisfied by the function $f$ and $\parallel x^* \parallel$ can be computed.
260
261 %Now for the other direction, assume that global minima is not computable. But there is some property $P_{\zeta}(y,x)$ where one can find a computable $\zeta \in \mathbb{R}$ such that the property is satisfied by the function $f$. Now we look at the definition of global minima and define another global property for $f$ as
262
263 %\[P_{\zeta}(y,x) \mbox{ is True for all } x, y, \zeta \mbox{ if there exists a } x \mbox{ s.t. for all } y, f(x) \leq f(y). \]
264
265 %\begin{table}[h]
266 % \centering
267 % \begin{tabular}{cl}
268 % \multirow{2}{1.1cm}{$P^f_{\varepsilon}(y,x)=$} & 1 if $f(x) \leq f(y), \forall y$ \\
269 % &0 o.w.
270 % \end{tabular}
271 %\end{table}
272
273 %And by assumption we can not find a computable $\zeta$, such that $P_{\zeta}(y,x)$ is satisfied by $f$. But this is a contradiction to the existence of global optima $x^*$, as $P_{\zeta}(y,x^*)$ is satisfied by $f$ for all $\zeta$ and this property can be computed if $x^*$ is computable. Thus we have shown the structure of the global property which must be satisfied for the global optima to be computable.
274 %independent of the value of $\varepsilon$
275 \end{remark}
276
277 \begin{remark}
278 Lipschitz continuity is another example of such a global property. Let $P_L(y,x)$ be
279 \[|f(x)-f(y)| \leq L \parallel x - y \parallel, \, \mbox{ for all } x,y \, \in C.\]
280 And here the number $\zeta$ is the Lipschitz constant $L$. Let the set of functions on some compact domain $C$ satisfying the Lipschitz property be denoted by $\mathcal{L}$. It is known that if the Lipschitz constant or an upper bound to it is known then the global optima for this class of functions $\mathcal{L}$ is computable. (For example refer to Theorem 1.1.2 of \cite{nest}). Another example of a global property is bounded derivatives. If a bound on the gradient is known then the global minima can be computed.
281 \end{remark}
282
283 \section{Conclusion}
284 We have proved that there is no algorithm which finds a $\epsilon-$ approximation to the optima of nonconvex function $f$. This result holds even if the function has higher-order derivatives.
285
286 \bibliographystyle{plain}
287 \bibliography{glosub}
288
289 %\begin{thebibliography}{}
290 %\bibitem{bishop} C.M. Bishop., Pattern Recognition and Machine Learning, Springer (2006).
291
292 %\bibitem{chembook} T.F. Edgar and D.M. Himmelblau., Optimization of Chemical Processes, McGraw Hill (1988).
293
294 %\bibitem{globook} R. Horst and H. Tuy., Global Optimization: Deterministic Approaches, Springer-Verlag (1996).
295
296 %\bibitem{sorbook} R.I. Soare., Turing Computability: Theory and Applications, Springer-Verlag (2016).
297
298 %\bibitem{nest} Y. Nesterov., Introductory Lectures on Convex Optimization A Basic Course, Kluwer Academic Publishers (2003).
299
300 %\bibitem{pour} M. Pour-El and J. Richards., Computability in analysis and physics, Springer, Heidelberg (1989).
301 %\end{thebibliography}
302
303 \end{document}