text:
# Angular Velocity

1. Jan 20, 2008

### Bingo1915

[SOLVED] Angular Velocity

1.
The angular acceleration is given $$\alpha$$=-2w^2 rad/s^2 where $$\omega$$ is the angular velocity in rad/s. When $$\theta$$=30 deg the angular velocity is 10 rad/s. What is the angular velocity when $$\theta$$=60deg?

2.
Used $$\alpha=d\varpi/d\theta * \varpi$$

3.
$$\int-2 d\theta=\int1/\varpi d\varpi$$

after integration I got

[$$\(-2)*theta$$]=[$$ln\varpi$$]

limits 0-60 for $$\theta$$ and 10 to $$\varpifor \varpi$$

I think I'm missing a step somewhere. The book gives an answer of w=3.51. With my calculations I get w=1.14. Can you advise?

Last edited: Jan 20, 2008
2. Jan 21, 2008

### Shooting Star

Redo the calculation. Book is correct. The limits of theta should be from pi/6 to pi/3.

3. Jan 21, 2008

### Bingo1915

Using pi/6 to pi/3 I get

-2pi/3 + pi/3 = lnw-ln10

-pi/3 + ln10 = lnw

From here I think it is

1/[e^(-pi/3+ln10)] = w

Can you check me on this part?

Last edited: Jan 21, 2008
4. Jan 22, 2008

### Leong

1/[e^(-pi/3+ln10)] = w

e^(-pi/3+ln10) = w [ln a = b ie e^b = a]

5. Jan 22, 2008

### Shooting Star

ln 10/w = pi/3. Take antilog of pi/3, use a calulator (or something) => w = 3.51.

(By antilog, I meant, 10/w = e^pi/3. You have done everything correctly.)

Last edited: Jan 22, 2008
6. Jan 22, 2008

### Bingo1915

I see where I was incorrect.

Thanks for the help.

format: plain


text:
# Time-series cross-sectional classification problem

I have a time-series cross-sectional dataset consisting of 100 individuals that each had 4 features measured yearly for 21 consecutive years. One of the features is binary and the other three are continuous.

Below is a fictitious example of what my dataset looks like:

x1<-rep(1:100, each=21)
x2<-rep(rep(2000:2020), 100)
x3<-round(rnorm(210), digits=2)
x4<-round(rnorm(210), digits=2)
x5<-round(rnorm(210), digits=2)
x6<-sample(0:1, 210, replace=T)
x<-data.frame(cbind(x1, x2, x3, x4, x5, x6))
colnames(x)<-c("Person", "Year", "X1", "X2", "X3", "Y")

Person Year    X1    X2    X3 Y
1      1 2000  1.07 -0.38 -2.78 0
2      1 2001  1.03  1.35  0.35 0
3      1 2002 -0.14 -2.23  0.46 1
4      1 2003 -0.88 -0.22  0.12 1
5      1 2004  0.17  1.79  0.64 0
6      1 2005 -0.45  2.10  1.75 0

> tail(x)
Person Year    X1    X2    X3 Y
2095    100 2015  0.55  2.21 -0.54 1
2096    100 2016  0.70  0.04  2.12 1
2097    100 2017 -2.49 -1.47 -1.19 1
2098    100 2018 -0.70  1.17  0.79 0
2099    100 2019  1.21  0.47  0.31 0
2100    100 2020 -0.92 -1.53  1.20 0

I wish to train different learning algorithms on this dataset to forecast/predict each individual's class, $Y$.

I am finding it difficult to think how off-the-shelf learning algorithms like decision trees, support vector machines, neural networks, and so on, can be trained and tuned on this type of data in R. I usually use the $caret$ package in R when I am training and tuning learning algorithms on cross-sectional data.

Q1: Is is possible to adapt and apply machine learning methods to solve this type of problem?

Q2: Is this the best way to store time-series cross-sectional data for analysis in R?

Although I do not know where to start with tackling this type of classification problem, I realise that one cannot use $k$-fold cross validation to tune hyperparamters since the data is probably correlated across time. A possible solution would be to use moving/sliding window cross validation?

Q3: Is there a package available in R for doing moving/sliding window cross validation?

• Why not give logistic regression a go if you are trying to predict Y given X1, X2, X3? Do you know the data set to not be suitable? – paisanco Jul 3 '15 at 1:26
• I was hoping to create an ensemble of classifiers – ajohnrobertson Jul 3 '15 at 11:36


text:
# Python: Calculate angle between vertices

What should I do to determine the angle on XYZ between two vertices? I then have to rotate a mesh accordingly, but I guess that's a basic task to achieve.

I'm new to bpy and I should have payed more attention during my maths classes, i suppose.

Here's a graphical representation

I need to know the angle of that orange segment

• The angle in relation to what? Aug 1, 2015 at 17:12
• Global x, y and z. Sorry for the omission Aug 1, 2015 at 18:20
• You describe an edge by declaring two vertices. You now need to declare another edge - the x, y, or z unit vectors (only one) - or a plane - the xy, yz, or zx (only one) plane. Aug 1, 2015 at 22:30
• why should I do this? How could it help me with the script? Aug 2, 2015 at 6:51
• Because you can only calculate an angle between two vectors / edges. You might wanna take a vector math course. Aug 2, 2015 at 8:39

You can get two selected vertices via bm.select_history and calculate a direction vector, then measure the angle between this angle and the up vector (0, 0, 1) in radians and convert it to degrees (below script prints the smaller angle):

import bpy
import bmesh
from math import degrees, pi
from mathutils import Vector

ob = bpy.context.object
assert ob.type == 'MESH'
me = ob.data

bm = bmesh.from_edit_mesh(me)
verts_sel = [el for el in bm.select_history if isinstance(el, bmesh.types.BMVert)]
assert len(verts_sel) == 2

v1 = verts_sel[1].co - verts_sel[0].co
v2 = Vector((0, 0, 1))

a1 = v1.angle(v2)
if a1 > pi * 0.5:
a1 = pi - a1
print("{:.2f} degrees".format(degrees(a1)))


text:
Bitcoin analysis

I don’t write as much about Bitcoin anymore, because it’s too volatile and the majority of people who are buying Bitcoin now are chasing price momentum and will be burned when it drops big time (and it surely will), so it would be in bad faith to encourage people to engage in such speculation when they lack the psychological disposition to tolerate large, sudden losses.

But right off the bat, Bitcoin is not going to be money (in the same way the US dollar is money), it’s not going to revolutionize commence, I don’t think blockchain technology is that big of a deal (all it is is an online public ledger), and the US dollar is not a ‘bubble’. As discussed earlier (when Bitcoin was only at $2,000), Bitcoin is much closer to being a commodity, such as gold, than a currency. Bitcoin is too hard to use, too prone to wallet theft and hacking in part due to to stolen funds being irrecoverable, too much volatility relative to the US dollar, the fees are too high, there is no buyer protection, and worst of all, one much convert their fiat into Bitcoin to spend Bitcoin, which defeats the point of it being a standalone currency. In May 2017, when Bitcoin was at$1,700, I predicted it would go to $20,000, which it came within a hair of hitting last week. It has since pulled back to$16,000-$17,000. If one includes the Bitcoin Cash and Gold spin-offs, the$20,000 target has been surpassed by about $1,500, so I was right again. My target having been hit, I have since begun to sell some of my holdings to buy back in should Bitcoin fall 75% or more. Despite these downside risks, how high can Bitcoin go? The sum of the parts cannot exceed the whole. The upper theoretical limit of Bitcoin is likely the same as the total value of all mined gold in existence, or about$7-10 trillion, and then you can add about 3-5% a year on top of that for inflation effects. But the odds of that happening are slim.


text:
# How to fix spacing for summation

I defined a command \newcommand{\osum}[2]{\smashoperator[r]{\sum_{#1}}{#2}} with the intention to allow only the summand to be next to the sigma notation. However, this is not translated properly as shown by my MWE:

\documentclass{article}
\usepackage{mathtools}

\newcommand{\osum}[2]{\smashoperator[r]{\sum_{#1}} {#2}}
\newcommand{\orb}{\text{Orb}}

\begin{document}

$O_G(X^\alpha) = \osum{X^\beta \in \orb_{G}(X^\alpha)}{X^\beta} = \osum{X^\beta \in \orb_G(\sigma^{-1}(X^\alpha))}{X^\beta} = \osum{X^\beta \in \orb_G(X^{\sigma(\alpha)})}{X^\beta} = O_G(X^{\sigma(\alpha)}).$

\end{document}

This yields

I don't want the equal sign to hover over the subscript. I want it to respect the spacing of the osum object. Does anyone have any suggestions. Thanks.

I think here I'd probably do the third option as it's simple and looks OK I think. I was thinking of doing some more complicated scheme measuring the width of the summation with and without the subscript and positioning by hand. That would allow the subscript to be centred under the sum, but actually centering under whole term is more compact and OK in this case I think.

\documentclass{article}
\usepackage{mathtools}

\newcommand{\osum}[2]{\smashoperator[r]{\sum_{#1}} {#2}}
\newcommand{\orb}{\mathrm{Orb}}

\begin{document}

$O_G(X^\alpha) = \osum{X^\beta \in \orb_{G}(X^\alpha)}{X^\beta} = \osum{X^\beta \in \orb_G(\sigma^{-1}(X^\alpha))}{X^\beta} = \osum{X^\beta \in \orb_G(X^{\sigma(\alpha)})}{X^\beta} = O_G(X^{\sigma(\alpha)}).$
\renewcommand{\osum}[2]{\sum_{#1}{#2}}
$O_G(X^\alpha) = \osum{X^\beta \in \orb_{G}(X^\alpha)}{X^\beta} = \osum{X^\beta \in \orb_G(\sigma^{-1}(X^\alpha))}{X^\beta} = \osum{X^\beta \in \orb_G(X^{\sigma(\alpha)})}{X^\beta} = O_G(X^{\sigma(\alpha)}).$
\renewcommand{\osum}[2]{\mathop{\sum{#2}}_{#1}}
$O_G(X^\alpha) = \osum{X^\beta \in \orb_{G}(X^\alpha)}{X^\beta} = \osum{X^\beta \in \orb_G(\sigma^{-1}(X^\alpha))}{X^\beta} = \osum{X^\beta \in \orb_G(X^{\sigma(\alpha)})}{X^\beta} = O_G(X^{\sigma(\alpha)}).$

\end{document}

• That's very clever! Much appreciated, David! – B. Hall Mar 31 '17 at 19:16


text:
# Will going up with a larger diameter ensure a higher water pressure in the distribution pipes? [closed]

Have a look at the drawing below describing a sample situation:

• a water tank
• a 1'' diameter pipe bringing the water down, inside the ground, arriving near the house
• in the house, 2 x 0.5'' diameter pipes distribute the water from a connection T to various faucets

I'd like to understand the differences between two possibilities: connecting the incoming pipe to the distribution T using a 1'' diameter pipe (possibility 1) and connecting the distribution the T using a 0.5'' diameter pipe (possibility 2). (As you see on the drawing, the water has to go against gravity about 2m to reach the T.)

My "gut feelings" tell me that the first solution is better to maintain pressure if faucets are used on both ends of the T at the same time whereas the second one is better to fight gravity.

## closed as off-topic by tpg2114♦, Kyle Kanos, ACuriousMind♦, Qmechanic♦May 6 '15 at 19:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question appears to be about engineering, which is the application of scientific knowledge to construct a solution to solve a specific problem. As such, it is off topic for this site, which deals with the science, whether theoretical or experimental, of how the natural world works. For more information, see this meta post." – tpg2114, Kyle Kanos, ACuriousMind, Qmechanic
If this question can be reworded to fit the rules in the help center, please edit the question.

• This appears to be an engineering question, not a physics one. Perhaps Engineering or Home Improvement might be better suited for this question? – Kyle Kanos May 6 '15 at 19:00
• I edited the question and think it must fit the Physics site now... – John Doisneau May 6 '15 at 21:24

Azad provides a link to one of the many empirical models that can predict pressure drop, but if you are seriously planning and investing in plumbing a new home - take caution.

A general comment to begin is that tubing or pipe in general will create a resistance to the flow of fluid going through the pipe for any given pressure, so the bigger the pipe, the larger the capacity. The drawback is that as pipe diameter gets bigger, so does the cost of pipe and the fittings that go with it. If your pipe diameter is too small when fluid starts flowing there will be a larger pressure drop, therefore smaller pressure at the faucet.

Depending on your household capacity needs (will you be washing dishes the same time you are doing laundry and showering?) you may actually need something larger than 1" pipe.

I'd say option 1.

Doubling the diameter would reduce the pressure loss in that pipe by 32 times in a constant flow rate scenario. Overall pressure loss will also decrease but not that much.

Surface area increases 4 times then if the flow rate is constant the flow velocity will decrease by 4 times according to continuity equation.

Then we have this Darcy–Weisbach equation which is $\Delta p \propto {L \over D} \rho u^2$

L is the length (which is const. here)

D is the diameter (which is doubled)

u is the flow velocity (which is a quarter of previous value)

$\rho$ is the density of fluid


text:
by Janos Kramar 993 days ago | Jessica Taylor and Patrick LaVictoire like this | link | parent It may still be possible to get a unique (up to scaling) invariant measure (with infinite sum) over the UTMs by invoking something like the Krein-Rutman theorem and applying it to the Markov chain’s transition operator. I haven’t yet verified that all the conditions hold. This measure would then be an encoding-invariant way to compare UTMs’ “intrinsic complexity” in the sense of “number of bits needed to simulate”.

 by Janos Kramar 979 days ago | Patrick LaVictoire likes this | link Consider the function $$a(M_1,M_2)=2^{-d(M_1,M_2)-d(M_2,M_1)}$$ where $$d(M_1,M_2)=\min\left(|x|\middle|x\in\{0,1\}^*:\forall y\in\{0,1\}^*: M_1(xy)=M_2(y)\mbox{ unless neither of these halts}\right)$$. The reversible Markov chain with transition probabilities $$p(M_1,M_2)=\frac{a(M_1,M_2)}{\sum_{M'_2}a(M_1,M'_2)}$$ has a bounded positive invariant measure $$\mu(M)=\sum_{M'}a(M,M')$$. Of course, as the post showed, the total measure is infinite. Also, because the chain is reversible and transient, the invariant measure is far from unique - indeed, for any machine $$M_0$$, the measure $$\mu(M)=p^{(0)}(M,M_0)+2\sum_{n=1}^\infty p^{(n)}(M,M_0)$$ will be a bounded positive invariant measure. It seems tempting (to me) to try to get a probability measure by modding out the output-permutations (that the post uses to show this isn’t possible for the full set of UTMs). To this end, consider the set of UTMs that have no output. (These will be unaffected by the output-permutations.) We can try to use the induced sub-digraph on these to build a probability measure $$\mu$$. The measure of each UTM should be a function of the rooted edge-labeled digraph $$G_M$$ rooted at that UTM. The most natural topology on rooted edge-labeled infinite digraphs is the one generated by the sets $$\{G:G'\mbox{ is isomorphic to an induced rooted edge-labeled subgraph of G}\}$$ where $$G'$$ ranges over finite rooted edge-labeled digraphs - we could hope that $$\mu$$ is continuous according to this topology. Unfortunately, this can’t work: if $$\mu(M)>0$$ then $$\mu^{-1}((\frac{1}{2}\mu(M),\infty))$$ must be open, and so it must contain some finite intersection of the generating sets; however, every such intersection that’s nonempty (as this one is) contains infinitely many UTMs, so the total measure must be infinite as well. reply
 by Janos Kramar 979 days ago | Patrick LaVictoire likes this | link In order to understand what the measure $$\mu$$ that was constructed from $$d$$ will reward, here’s the sort of machine that comes close to $$\sup_M\mu(M)=3$$: Let $$M_0$$ be an arbitrary UTM. Now consider the function $$r(n)=n-2^{\lfloor \lg n \rfloor}$$ (or, really, any function $$r:\mathbb{N}^+\rightarrow\mathbb{N}^0$$ with $$r(n)2,x_{|x|-1}=x_{r(|x|-1)},x_{|x|-2}=x_{r(|x|-2)}\}$$. (The indices here are zero-based.) Choose $$x_0\in L$$ such that $$x_0$$ has no proper prefix in $$L$$. Then, construct the UTM $$M$$ that does: repeat: s := "" while s not in L: # if there is no next character, halt s := s + readchar() if s == x0: break M0() This $$M$$ will have $$\mu(M)>3-2^{-|x_0|}+d(M_0,M)2^{-|x_0|-d(M_0,M)}$$. $$M$$ here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to “encode” from the UTMs it efficiently encodes, using at most 2 bits (an average of $$\frac{1+\sqrt{5}}{2}$$). This is somewhat interesting, but clearly doesn’t capture the kind of computational expressivity we’re primarily interested in. reply
 by Janos Kramar 975 days ago | Patrick LaVictoire likes this | link These results are still a bit unsatisfying. The first half constructs an invariant measure which is then shown to be unsatisfactory because UTMs can rank arbitrarily high while only being good at encoding variations of themselves. This is mostly the case because the chain is transient; if it was positive recurrent then the measure would be finite, and UTMs ranking high would have to be good at encoding (and being encoded by) the average UTM rather than just a select family of UTMs. The second half looks at whether we can get better results (ie a probability measure) by restricting our attention to output-free “UTMs” (though I misspoke; these are not actually UTMs but rather universal semidecidable languages (we can call them USDLs)). It concludes that we can’t if the measure will be continuous on the given digraph - however, this is an awkward notion of continuity: a low-complexity USDL whose behavior is tweaked very slightly but in a complex way may be very close in the given topology, but should have measure much lower than the starting USDL. So I consider this question unanswered. reply

### NEW DISCUSSION POSTS

[Delegative Reinforcement
 by Vadim Kosoy on Stable Pointers to Value II: Environmental Goals | 1 like

Intermediate update: The
 by Alex Appel on Further Progress on a Bayesian Version of Logical ... | 0 likes

Since Briggs [1] shows that
 by 258 on In memoryless Cartesian environments, every UDT po... | 2 likes

This doesn't quite work. The
 by Nisan Stiennon on Logical counterfactuals and differential privacy | 0 likes

I at first didn't understand
 by Sam Eisenstat on An Untrollable Mathematician | 1 like

This is somewhat related to
 by Vadim Kosoy on The set of Logical Inductors is not Convex | 0 likes

This uses logical inductors
 by Abram Demski on The set of Logical Inductors is not Convex | 0 likes

Nice writeup. Is one-boxing
 by Tom Everitt on Smoking Lesion Steelman II | 0 likes

Hi Alex! The definition of
 by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

A summary that might be
 by Alex Appel on Delegative Inverse Reinforcement Learning | 1 like

I don't believe that
 by Alex Appel on Delegative Inverse Reinforcement Learning | 0 likes

This is exactly the sort of
 by Stuart Armstrong on Being legible to other agents by committing to usi... | 0 likes

When considering an embedder
 by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
 by Abram Demski on Policy Selection Solves Most Problems | 1 like

Looking "at the very
 by Abram Demski on Policy Selection Solves Most Problems | 0 likes


text:
# The displacement x of a particle varies with time 't' as $x=ae^{-\alpha t}+b e^{\beta t}$ where $a,b,\alpha, \beta$ are positive constants. The velocity of the particle will

$\begin{array}{1 1} (a) go\;on\;decreasing \;with \;time \\(b)be\; independent\; of\; \alpha\;and\; \beta \\(c) drop\;of\;zero\;when\;\alpha=\beta \\(d)\;go\;on\;increasing\;with\;time \end{array}$

Answer: go on increasing with time.
Given $x=ae^{-\alpha t}+be^{\beta t}$
Velocity = displacement / time = $v=\large\frac{dx}{dt}$$=-a\; \alpha e^{-\alpha t}+b \beta e^{\beta t}$
As you can see, velocity is dependent of $\alpha$ and $\beta$, and does not drop to zero when $\alpha = \beta$
Now as t increases, $-a\;\alpha e^{-\alpha}$ decreases and $b\;\beta e^{\beta}$ increases $\rightarrow$ velocity goes on increasing with time.
edited Aug 11, 2014


text:
## Version 2.0.0

These subroutines are for the solution of a general sparse $m×n$ system of linear equations (the most usual case being square, $m=n$), stored by columns. No block triangularization, iterative reﬁnement, or error estimation is included.


text:
### Hardware Implementations of a Variant of the Zémor-Tillich Hash Function: Can a Provably Secure Hash Function be very efficient ?

Giacomo de Meulenaer, Christophe Petit, and Jean-Jacques Quisquater

##### Abstract

Hash functions are widely used in Cryptography, and hardware implementations of hash functions are of interest in a variety of contexts such as speeding up the computations of a network server or providing authentication in small electronic devices such as RFID tags. Provably secure hash functions, the security of which relies on the hardness of a mathematical problem, are particularly appealing for security, but they used to be too inefficient in practice. In this paper, we study the efficiency in hardware of ZT', a provably secure hash function based on the Zémor-Tillich hash function. We consider three kinds of implementations targeting a high throughput and a low area in different ways. We first present a high-speed implementation of ZT' on FPGA that is nearly half as efficient as state-of-the-art SHA implementations in terms of throughput per area. We then focus on area reduction and present an ASIC implementation of ZT' with much smaller area costs than SHA-1 and even than SQUASH, which was specially designed for low-cost RFID tags. Between these two extreme implementations, we show that the throughput and area can be traded with a lot of flexibility. Finally, we show that the inherent parallelism of ZT' makes it particularly suitable for applications requiring high speed hashing of very long messages. Our work, together with existing reasonably efficient software implementations, shows that this variant of the Zémor-Tillich hash function is in fact very practical for a wide range of applications, while having a security related to the hardness of a mathematical problem and significant additional advantages such as scalability and parallelism.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash functionZémor-TillichHardwareFPGAASIC
Contact author(s)
giacomo demeulenaer @ uclouvain be
History
Short URL
https://ia.cr/2009/229

CC BY

BibTeX

@misc{cryptoeprint:2009/229,
author = {Giacomo de Meulenaer and Christophe Petit and Jean-Jacques Quisquater},
title = {Hardware Implementations of a Variant of the Zémor-Tillich Hash Function: Can a Provably Secure Hash Function be very efficient ?},
howpublished = {Cryptology ePrint Archive, Paper 2009/229},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/229}},
url = {https://eprint.iacr.org/2009/229}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
## scdist2 details:

Keywords: analytic solution

Geometry: easy, fixed

Design: coupled via volume data

Differential operator:

• Poisson:
• linear elliptic operator of order 2.
• Defined on a 2-dim domain in 2-dim space
• No time dependence.

Design constraints:

• none

State constraints:

• box of order 0

Mixed constraints:

• none

Submitted on 2014-02-15 by Winnifried Wollner. Published on 2017-01-09

## scdist2 description:

### Introduction

This problem was introduced in [Benedix and Vexler2009, Example 1]. The example is constructed such that the analytic solution in known, and the Lagrange multiplier for the pointwise state constraints is given by a line measure and a volume contribution using smooth problem data. The example is parametrized by three real numbers that allow to steer the contributions of the volume and line measure. Further, the position of the line measure can be chosen to avoid that it coincides with edges of the discretization.

### Variables & Notation

#### Free parameters

Within the problem, there are three free parameters $\left(s,m,b\right)$ that can be chosen by the user:

• The boundary between active and inactive set is given by $\left\{s\right\}×\left[0,1\right]$, with the corresponding parameter
$s\in \left(0,1\right).$

• To steer the volume contribution, a parameter $m$ can be tuned. Smaller values of $m$ imply a stronger contribution of the line measure. It is assumed that
$m<{s}^{-3}.$

• To steer the volume contribution, a parameter $b$ can be chosen. Larger values of $b$ imply stronger contribution of the volume measure. It is assumed that
$b>0.$

The calculations in Benedix and Vexler [2009] were conducted using $b=50$, $m=-2$, and $s=0.125$ as well as $s=0.3$.

#### Given Data

The given data is chosen in a way which admits an analytic known solution. The solution is constant along the ${x}_{2}$ direction.

With this one deﬁnes

The desired state is given by

${u}_{d}\left({x}_{1},{x}_{2}\right)=\left\{\begin{array}{cc}{x}_{1}^{3}\phantom{\rule{0.3em}{0ex}}{s}^{-3}-3\phantom{\rule{0.3em}{0ex}}{x}_{1}^{2}\phantom{\rule{0.3em}{0ex}}{s}^{-2}+3\phantom{\rule{0.3em}{0ex}}{x}_{1}\phantom{\rule{0.3em}{0ex}}{s}^{-1}+2,\phantom{\rule{1em}{0ex}}\hfill & {x}_{1}

The upper bound is given by

${u}_{b}\left({x}_{1},{x}_{2}\right)=\left\{\begin{array}{cc}1,\phantom{\rule{1em}{0ex}}\hfill & {x}_{1}

Moreover, the uncontrolled force is set to be

$f\left({x}_{1},{x}_{2}\right)=\left\{\begin{array}{cc}6\phantom{\rule{0.3em}{0ex}}{s}^{-2}-6\phantom{\rule{0.3em}{0ex}}m\phantom{\rule{0.3em}{0ex}}{x}_{1}+{x}_{1}\phantom{\rule{0.3em}{0ex}}\left({x}_{1}-2\right)+b\phantom{\rule{0.3em}{0ex}}\left(1-s\right)\phantom{\rule{0.3em}{0ex}}{x}_{1},\phantom{\rule{1em}{0ex}}\hfill & {x}_{1}

where

$r=\frac{b}{2}-\frac{9\phantom{\rule{0.3em}{0ex}}m}{1-s}.$

### Optimality System

The following optimality system for the state $u\in {H}_{D}^{1}\left(\Omega \right)$, the control $q\in {L}^{2}\left(\Omega \right)$, the adjoint state $z\in {H}_{D}^{1}\left(\Omega \right)$, and the Lagrange multiplier for the inequality constraints $\mu \in \mathsc{ℳ}\left(\Omega \right)=C{\left(\overline{\Omega }\right)}^{\ast }$ given in the strong form, characterizes the unique minimizer.

### Supplementary Material

The optimal solution is known analytically. It is given by

$\begin{array}{llll}\hfill u\left({x}_{1},{x}_{2}\right)& =\left\{\begin{array}{cc}{x}_{1}^{3}\phantom{\rule{0.3em}{0ex}}{s}^{-3}-3\phantom{\rule{0.3em}{0ex}}{x}_{1}^{2}\phantom{\rule{0.3em}{0ex}}{s}^{-2}+3\phantom{\rule{0.3em}{0ex}}{x}_{1}\phantom{\rule{0.3em}{0ex}}{s}^{-1},\phantom{\rule{1em}{0ex}}\hfill & {x}_{1}

### References

O. Benedix and B. Vexler. A posteriori error estimation and adaptivity for elliptic optimal control problems with state constraints. Computational Optimization and Applications, 44(1):3–25, 2009. doi: 10.1007/s10589-008-9200-y.


text:
{{ message }}

# Errors with algpseudocode #825

Closed
opened this issue Jan 5, 2017 · 2 comments
Closed

# Errors with algpseudocode#825

opened this issue Jan 5, 2017 · 2 comments
Milestone

### davpoole commented Jan 5, 2017

 We are converting our intro AI book to html using latexml (0.8.2). We have hit a snag with algpseudocode. I have created a small examples that does not work. test.tex: \documentclass{book} \usepackage{algpseudocode} %\usepackage[noend]{algpseudocode} \begin{document} \begin{algorithmic}[1] \Procedure{Proc}{$a,b$} \State\Return{7} \EndProcedure \end{algorithmic} \end{document}  Latex works fine. The command latexml --destination=dest.xml test.tex says "Conversion complete: No obvious problems." Then latexmlpost --destination=result.html dest gives many errors of the form dest.xml:11: validity error : xml:id : attribute value .l2 is not an NCName 2:

### brucemiller commented Jan 9, 2017

 hmm... it seems the binding for algpseudocode is assuming that the algorithm package is loaded, and wants to number the lines from within an algorithm counter, but that's not happening in your case. I've got to look into how to make it behave in both scenarios... Nice textbook, btw!

### brucemiller commented Jan 9, 2017

 OK, I think I've got it working right, now; checked in. Thanks for the report and good luck with your book; let us know how it goes!
closed this Jan 9, 2017
added this to the LaTeXML-0.8.3 milestone Jan 6, 2018
mentioned this issue Mar 31, 2020


text:
# fundamental theorem of calculus worksheet with answers

This lesson contains the following Essential Knowledge (EK) concepts for the *AP Calculus course.Click here for an overview of all the EK's in this course. Thus, the two parts of the fundamental theorem of calculus say that differentiation and integration are inverse processes. CALCULUS AB WORKSHEET ON SECOND FUNDAMENTAL THEOREM AND REVIEW Work the following on notebook paper. We suggest that the presenter not spend time going over the reference sheet, but point it out to students so that they may refer to it if needed. Theorem The second fundamental theorem of calculus states that if f is a continuous function on an interval I containing a and F(x) = ∫ a x f(t) dt then F '(x) = f(x) for each value of x in the interval I. So, 16 Explain your answer. Find the value of 15. Example: Compute Z 2 0 16 (x 3)2(x+ 1) dx. ... Find an equation of the tangent line to the curve y = F(x) at the point with x-coordinate 2. Answers for preview activities are not included. 3. Worksheet 4.3—The Fundamental Theorem of Calculus Show all work. Answer. … It converts any table of derivatives into a table of integrals and vice versa. L8  The Second Fundamental Theorem of Calculus WORKSHEET KEY.notebook 1 April 25, 2018. Christine Heitsch, David Kohel, and Julie Mitchell wrote worksheets used for Math 1AM and 1AW during the Fall 1996 semester. The Fundamental Theorem of Calculus The Fundamental Theorem of Calculus shows that di erentiation and Integration are inverse processes. A ball is thrown at the ground from the top of a tall building. Worksheet 6 - Fundamental Theorem of Calculus, Deﬁnite Integral, Indeﬁnite integral 1. USing the fundamental theorem of calculus, interpret the integral J~vdt=J~JCt)dt. t f(t) 4. The chapter headings refer to Calculus, Sixth Edition by Hughes-Hallett et al. Students work 12 Fundamental Theorem of Calculus problems, sum their answers and then check their sum by scanning a QR code (there is a low-tech option that does not require a QR code).This works with Distance Learning as you can send the pdf to the students and they can do it on their own and check A biologist uses a model which predicts the population will increase 2t+5rabbitsperyearwheret represents the number of years from today. Consider the function f(t) = t. For any value of x > 0, I can calculate the de nite integral Z x 0 f(t)dt = Z x 0 tdt: by nding the area under the curve: 18 16 14 12 10 8 6 4 2 Ð 2 Ð 4 Ð 6 Ð 8 Ð 10 Ð 12 See Note. The total area under a curve can be found using this formula. The area under the graph of the function $$f\left( x \right)$$ between the vertical lines $$x = a,$$ $$x = b$$ (Figure $$2$$) is given by the formula Today, we completed FTC Notes (Fundamental Theorem of Calculus) Took the Midterm Redo MC Gave the Review sheet for Integration Quiz . Find the derivative. Definite Integrals: We can use the Fundamental Theorem of Calculus Part 1 to evaluate definite integrals. 2. Find the value of . The total area under a curve can be found using this formula. Fundamental Theorems of Calculus. Fmd the value of G(3). MTH 207 { Review: Fundamental Theorem of Calculus 1 Worksheet: KEY Exercise. Fundamental theorem of calculus practice problems. 3 4 yx 25 2. ( ) ( ) ( ) b a ³ f x dx F b F a is the total change in F from a to b. In this Fundamental Theorem of Calculus worksheet, ... A calculus study guide provides an organized list of important topics and a few examples with answers. Solution: We start by running partial fraction decomposition on the integrand. An antiderivative of fis F(x) = x3, so the theorem says Z 5 1 3x2 dx= x3 = 53 13 = 124: We now have an easier way to work Examples36.2.1and36.2.2. If you're seeing this message, it means we're having trouble loading external resources on our website. Fundamental Theorem of Calculus Student Session-Presenter Notes This session includes a reference sheet at the back of the packet. Solution We use part(ii)of the fundamental theorem of calculus with f(x) = 3x2. • Use of the Fundamental Theorem to represent a particular antiderivative, and the analytical and graphical analysis of … EK 3.3A1 EK 3.3A2 EK 3.3B1 EK 3.5A4 * AP® is a trademark registered and owned by the College Board, which was not involved in the production of, and does not endorse, this site.® is a trademark David Jones revised the material for the Fall 1997 semesters of Math 1AM and 1AW. (A) 0.990 (B) 0.450 (C) 0.128 (D) 0.412 (E) 0.998 2. The topics include elementary functions, limits, differential calculus, and integral calculus,... Get Free Access See Review. View HW - 2nd FTC.pdf from MATH 27.04300 at North Gwinnett High School. View HW - 1st FTC.pdf from MATH 27.04300 at North Gwinnett High School. Find J~ S4 ds. In the last section we defined the definite integral, $$\int_a^b f(t)dt\text{,}$$ the signed area under the curve $$y= f(t)$$ from $$t=a$$ to $$t=b\text{,}$$ as the limit of the area found by approximating the region with thinner and thinner rectangles. Worksheet # 25: The Fundamental Theorem of Calculus, Part 1 1. basic_integratin_and_review_for_reimann_test.pdf: File Size: 66 kb: File Type: pdf There are currently 400 rabbits living on island. Find the derivative of g(x) = Z x6 log 3 x p 1 + costdt with respect to x. Berkeley’s calculus course. The 2006–2007 AP Calculus Course Description includes the following item: Fundamental Theorem of Calculus • Use of the Fundamental Theorem to evaluate definite integrals. If 55 22 ³³2 3 17, find .f x dx f x dx _____ 3. Find the This appendix contains answers to all activities in the text. 14. Section 7.2 The Fundamental Theorem of Calculus. This worksheet does not cover improper integration. The following is a list of worksheets and other materials related to Math 122B and 125 at the UA. Exercises 1. FTC Part 3 Worksheet 16: Guessing Anti-Derivatives involving Constants, Definite Integrals A. Questions on the two fundamental theorems of calculus are presented. Evaluate without using a calculator. 2. Some of the worksheets displayed are Fundamental theorem of calculus date period, Fundamental theorem of calculus date period, Math 101 work 4 the fundamental theorem of calculus, Work 29 the fundamental of calculus, Work the fundamental theorem of calculus multiple, The fundamental theorem of calculus… Some of the worksheets for this concept are Fundamental theorem of calculus date period, Fundamental theorem of calculus date period, Math 101 work 4 the fundamental theorem of calculus, Work 29 the fundamental of calculus, Work the fundamental theorem of calculus multiple, The fundamental theorem of calculus… v(t) = 9.8t + v 0,. where t denotes the number of seconds since the ball has been thrown and v 0 is the initial speed of the ball (also in meters per second). 1. Find the average value of a function over a closed interval. Fundamental theorem of calculus practice problems. The Fundamental Theorem of Calculus, Part 1 shows the relationship between the derivative and the integral. Math 221 Worksheet 21 Wednesday November 4th 2020 Definite Integrals and the Fundamental Theorem of Calculus (1)Assume that f is a continuous function. The Fundamental Theorem of Calculus The single most important tool used to evaluate integrals is called “The Fundamental Theo-rem of Calculus”. Multiple Choice 1. Do not leave negative exponents or complex fractions in your answers. No calculator. This booklet contains the worksheets for Math 1A, U.C. 4.4 The Fundamental Theorem of Calculus 277 4.4 The Fundamental Theorem of Calculus Evaluate a definite integral using the Fundamental Theorem of Calculus. Find the value of G"(—5) . Name: _ Per: _ CALCULUS WORKSHEET ON SECOND FUNDAMENTAL THEOREM Work the following on notebook paper. Understand and use the Mean Value Theorem for Integrals. Print Using the Fundamental Theorem of Calculus to Show Antiderivatives Worksheet 1. If the ball travels 25 meters during the first 2 seconds after it is thrown, what was the initial speed of the ball? Showing top 8 worksheets in the category - Fundamental Theorem Of Calculus. The Area under a Curve and between Two Curves. If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked. line. CALCULUS Name: _ Per: _ st WORKSHEET ON 1 FUNDAMENTAL THEOREM OF CALCULUS Work the following on … L8  The Second Fundamental Theorem of Calculus WORKSHEET KEY.notebook 2 April 25 ... Use the graph to answer questions 12 12. You will probably need to use both words Computation and Properties of the Derivative in Calculus. Questions and Answers on Derivatives in Calculus. (Calculator Permitted) What is the average value of f x xcos on the interval >1,5@? No calculator unless otherwise stated. Chapter 1 Understanding the Derivative ... Subsection 4.4.1 The Fundamental Theorem of Calculus Activity 4.4.2. This lesson contains the following Essential Knowledge (EK) concepts for the *AP Calculus course.Click here for an overview of all the EK's in this course. FindflO (l~~ - t2) dt o Proof of the Fundamental Theorem We will now give a complete proof of the fundamental theorem of calculus. Link to worksheets used in this section. 13. Displaying top 8 worksheets found for - Fundamental Theorem Of Calculus. CALCULUS WORKSHEET 2 ON FUNDAMENTAL THEOREM OF CALCULUS Use your calculator on problems 3, 8, and 13. EK 3.1A1 EK 3.3B2 * AP® is a trademark registered and owned by the College Board, which was not involved in the production of, and does not endorse, this site.® is a trademark registered and owned 5. Your instructor might use some of these in class. INTRODUCTION The speed of the ball in meters per second is . No calculator. See Note. 1. ftc notes day 1 - formula (87 KB) FTC NOTES (58 KB) Quiz -Integration Review Sheet Updated (37 KB) quiz-integration review sheet answer key (56 KB) Subsection 4.4.2 Basic antiderivatives Activity 4.4.3. Findf~l(t4 +t917)dt. The Fundamental Theorem of Calculus, Part 2 is a formula for evaluating a definite integral in terms of an antiderivative of its integrand. You may also use any of these materials for practice. Question 1 Approximate F'(π/2) to 3 decimal places if F(x) = ∫ 3 x sin(t 2) dt Solution to Question 1: The Fundamental Theorem of Calculus, Part 2 is a formula for evaluating a definite integral in terms of an antiderivative of its integrand. If 4 cc 1 f f f x dx1 12, is continuous, and 17, ³ what is the value of f 4? The de nition of the de nite integral R b a f(x)dx is Z b a f(x)dx = lim n!1 Xn i=1 f(x i) x: Answer the following questions about this de nition. Fundamental theorem of calculus 37.2.3 Example (a)Find Z 6 0 x2 + 1 dx. A set of questions on the concepts of the derivative of a function in calculus are presented with their answers and solutions. Answer. The material was further updated by Zeph Grunschlag The Fundamental Theorem of Calculus, Part 1 shows the relationship between the derivative and the integral. Published by Wiley. 3 42 x5 x 4. 1.1 The Fundamental Theorem of Calculus Part 1: If fis continuous on [a;b] then F(x) = R x a ... do is apply the fundamental theorem to each piece. ...4-5 Graph off . Biologist uses a model which predicts the population will increase 2t+5rabbitsperyearwheret represents the number of years today! Derivative and the integral 2 on Fundamental Theorem of Calculus 1 WORKSHEET: KEY fundamental theorem of calculus worksheet with answers Show Antiderivatives WORKSHEET.! Ftc Part 3 WORKSHEET 16: Guessing Anti-Derivatives involving Constants, definite integrals: We use! Integrals: We start by running partial fraction decomposition on the two Fundamental theorems of Calculus are presented with answers... And *.kasandbox.org are unblocked *.kasandbox.org are unblocked, definite integrals 're seeing this message, it We! Your Calculator on problems 3, 8, and integral Calculus, Sixth Edition by Hughes-Hallett et.. Get Free Access See Review find Z 6 0 x2 + 1.... A biologist uses a model which predicts the population will increase 2t+5rabbitsperyearwheret represents the number of from! Ab WORKSHEET on SECOND Fundamental Theorem of Calculus say that differentiation and Integration are processes... _ Per: _ Calculus WORKSHEET KEY.notebook 1 April 25... use the graph to questions. Seconds after it is thrown, What was the initial speed of the Fundamental Theorem Work the following on paper. Having trouble loading external resources on our website can use the Fundamental Theorem Calculus., and integral Calculus, Sixth Edition by Hughes-Hallett et al, it means 're! Fundamental Theo-rem of Calculus 1 WORKSHEET: KEY Exercise, 2018 x xcos on the integrand  the SECOND Theorem! = 3x2 presented with their answers and solutions the UA = Z x6 log 3 x 1. ( Calculator Permitted ) What is the average value of a function over a closed interval curve! ) = 3x2 are presented We completed ftc Notes ( Fundamental Theorem of Calculus, Sixth Edition Hughes-Hallett. Ftc Part 3 WORKSHEET 16: Guessing Anti-Derivatives involving Constants, definite integrals: can. The worksheets for Math 1A, U.C Integration Quiz 0 16 ( x 3 2! Is thrown, What was the initial speed of the derivative and the integral f x dx _____ 3 speed... In class be found using this formula headings refer to Calculus,... Get Free Access See Review antiderivative. Took the Midterm Redo MC Gave the Review sheet for Integration fundamental theorem of calculus worksheet with answers integrals is called “ the Fundamental Theorem Calculus. Permitted ) What is the average value of f x dx f x xcos on two. Review Work the following is a list of worksheets and other materials related to 122B. Meters during the Fall 1996 semester our website 3, 8, and integral Calculus, 1! 25, 2018 1996 semester find the derivative and the integral J~vdt=J~JCt ) dt y = f x. Worksheets and other fundamental theorem of calculus worksheet with answers related to Math 122B and 125 at the UA.f x dx f x dx x... Years from today 2 April 25... use the graph to answer questions 12... - Fundamental Theorem of Calculus are presented of derivatives into a table of derivatives a. Closed interval used for Math 1A, U.C in the text y = f x. The worksheets for Math 1A, U.C respect to x, and Julie Mitchell wrote worksheets for. Are inverse processes ( D ) 0.412 ( E ) 0.998 2 the tangent to! On Fundamental Theorem of Calculus the single most important tool used to evaluate definite integrals g x... Displaying top 8 worksheets found for - Fundamental Theorem and Review Work the following notebook! Math 1AM and 1AW two Fundamental theorems of Calculus Activity 4.4.2 interval > 1,5 @ 25... use Fundamental... That di erentiation and Integration are inverse processes Calculus AB WORKSHEET on SECOND Fundamental Theorem Calculus. Fundamental Theorem of Calculus, Part 2 is a formula for evaluating a definite integral in terms of antiderivative... ( C ) 0.128 ( D ) 0.412 ( E ) 0.998 2: the Fundamental Theorem of,. Related to Math 122B and 125 at the UA also use any of these in class x6 log 3 p... Web filter, please make sure that the domains *.kastatic.org and.kasandbox.org. 0.990 ( B ) 0.450 ( C ) 0.128 ( D ) (! Some of these in class 1AW during the first 2 seconds after it is,! Displaying top 8 worksheets found for - Fundamental Theorem of Calculus WORKSHEET KEY.notebook 1 April 25, 2018 for! Decomposition on the two parts of the Fundamental Theorem of Calculus Activity 4.4.2 _ Calculus on... Review: Fundamental Theorem of Calculus WORKSHEET KEY.notebook 2 April 25, 2018 ( ii ) of ball... _____ 3 the two Fundamental theorems of Calculus, Part 2 is a for... Most important tool used to evaluate definite integrals: We can use the Fundamental Theorem and Review fundamental theorem of calculus worksheet with answers!


text:
# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Zero duality gaps in infinite-dimensional programming. (English) Zbl 0687.90077

We study the following infinite-dimensional programming problem

$\left(P\right)\phantom{\rule{1.em}{0ex}}\mu :=inf{f}_{0}\left(x\right),\phantom{\rule{1.em}{0ex}}subject\phantom{\rule{1.em}{0ex}}to\phantom{\rule{1.em}{0ex}}x\in C,\phantom{\rule{1.em}{0ex}}{f}_{i}\left(x\right)\le ,\phantom{\rule{1.em}{0ex}}i\in I,$

where I is an index set with possibly infinite cardinality and C is an infinite-dimensional set. Zero duality gap results are presented under suitable regularity hypotheses for convex- like (nonconvex) and convex infinitely constrained programs (P). Various properties of the value function of the convex-like program and its connections to the regularity hypotheses are studied. Relationships between the zero duality gap property, semicontinuity, and $ϵ$- subdifferentiability of the value function are examined. In particular, a characterization for the value function without convexity is given, using the $ϵ$-subdifferential of the value function.

Reviewer: V.Jeyakumar
##### MSC:
 90C30 Nonlinear programming 90C34 Semi-infinite programming 49N15 Duality theory (optimization) 90C48 Programming in abstract spaces
##### References:
 [1] Charnes, A., Cooper, W. W., andKortanek, K. O.,Duality, Harr Programs, and Finite Sequence Spaces, Proceedings of the National Academy of Sciences, Vol. 48, pp. 782-786, 1962. · Zbl 0105.12804 · doi:10.1073/pnas.48.5.783 [2] Glashoff, K., andGustafson, G. A.,Linear Optimization and Approximation, Springer-Verlag, Berlin, Germany, 1983. [3] Duffin, R. J., andKarlovitz, L. A.,An Infinite Linear Program with a Duality Gap, Management Science, Vol. 12, pp. 122-134, 1965. · Zbl 0133.42604 · doi:10.1287/mnsc.12.1.122 [4] Ekeland, I., andTemam, R.,Convex Analysis and Variational Problems, North-Holland, Amsterdam, Holland, 1976. [5] Rockafellar, R. T.,Conjugate Duality and Optimization, CBMS Lecture Notes Series, Vol. 162, SIAM Publications, Philadelphia, Pennsylvania, 1974. [6] Charnes, A., Cooper, W. W., andKortanek, K. O.,On Representations of Semi-Infinite Programs Which Have No Duality Gaps, Management Science, Vol. 12, pp. 113-121, 1965. · Zbl 0143.42304 · doi:10.1287/mnsc.12.1.113 [7] Karney, D. F.,A Duality Theorem for Semi-Infinite Convex Programs and Their Finite Subprograms, Mathematical Programming, Vol. 27, pp. 75-82, 1983. · Zbl 0527.49027 · doi:10.1007/BF02591965 [8] Borwein, J. M.,How Special is Semi-Infinite Programming?, Semi-Infinite Programming and Applications, Edited by A. V. Fiacco and K. O. Kortanek, Springer-Verlag, Berlin, Germany, pp. 10-36, 1983. [9] Jeroslow, R. J.,Uniform Duality in Semi-Infinite Convex Optimization, Mathematical Programming, Vol. 27, pp. 144-154, 1983. · Zbl 0556.49008 · doi:10.1007/BF02591942 [10] Ben-Israel, A., Charnes, A., andKortanek, K. O.,Duality and Asymptotic Solvability over Cones, Bulletin of the American Mathematical Society, Vol. 75, pp. 318-324, 1969. · Zbl 0187.17504 · doi:10.1090/S0002-9904-1969-12153-1 [11] Ben-Israel, A., Charnes, A., andKortanek, K. O.,Asymptotic Duality in Semi-Infinite Programming and Convex Core Topology, Rendiconti di Mathematica, Vol. 4, pp. 751-767, 1971. [12] Jeroslow, R. G.,A Limiting Lagrangian for Infinitely Constrained Convex Optimization, Journal of Optimization Theory and Applications, Vol. 33, pp. 479-495, 1981. · Zbl 0427.49030 · doi:10.1007/BF00935754 [13] Kortanek, K. O.,Constructing a Perfect Duality in Infinite Programming, Applied Mathematics and Optimization, Vol. 3, pp. 358-372, 1977. [14] Borwein, J. M.,A Note on Perfect Duality and Limiting Lagrangians, Mathematical Programming, Vol. 18, pp. 330-337, 1980. · Zbl 0438.90072 · doi:10.1007/BF01588327 [15] Fan, K., Minimax Theorems,Proceedings of the National Academy of Sciences, Vol. 39, pp. 42-47, 1953. · Zbl 0050.06501 · doi:10.1073/pnas.39.1.42 [16] Jeyakumar, V.,Convex-Like Alternative Theorems and Mathematical Programming, Optimization, Vol. 16, pp. 643-652, 1985. · Zbl 0581.90079 · doi:10.1080/02331938508843061 [17] Craven, B. D., Gwinner, J., andJeyakumar, V.,Nonconvex Theorems of the Alternative and Minimization, Optimization, Vol. 18, pp. 151-163, 1987. · Zbl 0613.49026 · doi:10.1080/02331938708843228 [18] Borwein, J. M., andJeyakumar, V.,On Convex-Like Lagrangian and Minimax Theorems, University of Waterloo, Research Report No. 24, 1988. [19] Holmes, R. B.,Geometric Functional Analysis, Springer-Verlag, New York, New York, 1975. [20] Karney, D. F.,Clark’s Theorem for Semi-infinite Convex Programs, Advances in Applied Mathematics, Vol. 2, pp. 7-12, 1981. · Zbl 0456.90069 · doi:10.1016/0196-8858(81)90036-1 [21] Clarke, F.,Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, New York, 1983. [22] Hiriart-Urruty, J. B.,?-Subdifferential Calculus, Convex Analysis and Applications, Edited by J. P. Aubin and R. B. Vinter, Vol. 57, pp. 43-92, 1982. [23] Ponstein, J.,Applying Some Modern Developments to Choosing Your Own Lagrange Multipliers, SIAM Review, Vol. 25, pp. 183-199, 1983. · Zbl 0518.90073 · doi:10.1137/1025044 [24] Wolkowicz, H.,Optimality Conditions and Shadow Prices, Mathematical Programming with Data Perturbations, II, Edited by A. V. Fiacco, Marcel Dekker, New York, New York, 1983. [25] Rockafellar, R. T.,Generalized Directional Derivatives and Subgradients of Nonconvex Functions, Canadian Journal of Mathematics, Vol. 32, pp. 257-280, 1980. · Zbl 0447.49009 · doi:10.4153/CJM-1980-020-7 [26] Borwein, J. M., andStrojwas, H. M.,Directional Lipschitzian Mappings and Baire Spaces, Canadian Journal of Mathematics, Vol. 36, pp. 95-130, 1984. · Zbl 0534.46031 · doi:10.4153/CJM-1984-008-7 [27] Geoffrion, A. M.,Duality in Nonlinear Programming: A Simplified Applications-Oriented Development, SIAM Review, Vol. 13, pp. 1-37, 1971. · Zbl 0232.90049 · doi:10.1137/1013001 [28] Kortanek, K. O., andRom, W. O.,Classification Schemes for the Strong Duality of Linear Programming over Cones, Operations Research, Vol. 7, pp. 1571-1585. [29] Kallina, C., andWilliams, A. C.,Linear Programming in Reflexive Spaces, SIAM Review, Vol. 13, pp. 350-376, 1971. · Zbl 0224.90042 · doi:10.1137/1013065 [30] Kortanek, K. O.,Classifying Convex Extremum Problems over Linear Topologies Having Separation Properties, Journal of Mathematical Analysis and Applications, Vol. 46, pp. 725-755, 1974. · Zbl 0283.90043 · doi:10.1016/0022-247X(74)90270-4 [31] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1969. [32] Dedieu, J. P., Critères de Fermeture pour l’Image d’un Fermé Nonconvex par une Multiplication, Comptes Rendus de l’Académie des Sciences, Vol. 287, pp. 941-943, 1978. [33] Anderson, E., andNash, P.,Linear Programming in Infinite-Dimensional Spaces, John Wiley and Sons, Chichester, England, 1987.


text:
# Distinction between observable and unobservable universe

1. Dec 30, 2015

### Chiclayo guy

I know that when we talk about ‘the universe’ we’re normally referring to the observable universe. It is my understanding that the universe is 'one thing’, the only distinction being that part is visible and part is not, yet occasionally when the subjects of size and inflation are discussed comments are worded such that I have the impression that the observable universe is being treated as a separate entity existing in but independent of the total. Just so I am clear, when we talk about inflation and the initial size of the universe are we saying those concepts apply to the total universe (whatever that means) or just the observable?

2. Dec 30, 2015

### DuckAmuck

I'm not sure what you mean exactly, but yes inflation deals with the actual size of the universe. It doesn't include anything *outside* the universe.

3. Dec 30, 2015

### bcrowell

Staff Emeritus
Not true.

Phrases like "initial size of the universe" are typical in popularizations. Physicists would not typically use a phrase like that.

4. Dec 30, 2015

### Chiclayo guy

How discouraging…I thought my question was crystal clear. Let me take another run at it.

The universe is possibly infinite. Did/does inflation/expansion apply to the entire (I don’t know how else to phrase it) infinite universe?

What phrases do physicists use to describe the initial size of the universe? I’ve seen terms such as smaller than an electron, golf ball and grapefruit used on this very forum, but I’ve also seen that the BB happened “everywhere”. Does that mean everywhere within the grapefruit? It’s difficult for a layman, at least for me to make sense of that.

5. Dec 30, 2015

### DuckAmuck

Not likely, since there is a finite rate of expansion. It's very big, but probably not infinite.

The big bang happened everywhere, because it's not the material in the universe expanding, it's space itself. It wasn't just a dense ball of matter floating in large empty space.
The actual available space in the universe was once the size of a golf ball. This space has since expanded, and so you can say the big bang happened everywhere, since it's technically true.

6. Dec 30, 2015

### bcrowell

Staff Emeritus
Yes. (Inflation is irrelevant here. We don't even know for sure that inflation happened.)

Typically they would say that the cosmological scale factor had increased by a factor of x from a certain time in the past up to the present.

You can't talk about the initial size for two reasons: (1) the universe may be infinite, and (2) the cosmological scale factor was initially zero.

7. Dec 30, 2015

### DuckAmuck

I think OP might be confusing inflation with expansion.

8. Dec 30, 2015

### Orodruin

Staff Emeritus
This is irrelevant. The universe can perfectly well be infinite with a finite rate of expansion. In those situations, the universe was always infinite in extent.

9. Dec 30, 2015

### alw34

In that context, 'the [whole] universe' is everything.....there is nothing 'outside' the whole. You can't look back inside.

Inflation applies to the total/whole universe;
'initial size' has little if any meaning:

If you look at the illustration here,

https://en.wikipedia.org/wiki/Big_Bang#Overview

it starts from a single 'point' in the illustration. What popularizations may discuss is that one geometric point of origin, but it is from every such 'point', finite or infinite in number, that inflation takes place and from which the seeds of our universe appear. The origin of our universe appears to be a point time rather than a point in space.

10. Dec 30, 2015

### bcrowell

Staff Emeritus
The standard formulation in general relativity is not to describe singularities as points or sets of points. In particular, GR doesn't give any straightforward answers to questions about the size of a singularity, or even how many dimensions it has. Size and dimensionality are things that are defined for point-sets.

What we can say is that the cosmological scale factor approaches zero as time approaches the time of the big bang.

11. Dec 30, 2015

### DuckAmuck

Sure, but if the universe were infinite with a finite rate of expansion, then this would imply infinite size from the beginning, or a jump from finite to infinite at some point.
If it began with finite size and has always had a finite expansion rate, it must be finite.

12. Dec 30, 2015

### bcrowell

Staff Emeritus
GR predicts that if the universe is spatially finite now, then it has always been spatially finite. If it's spatially infinite now, then it's always been so.

Before going too far in this dialog between you and Orodruin on this point, are you sure you're both using the same definition of "rate of expansion?" Are we all talking about $\dot{a}/a$?


text:
# The Simplex Algorithm

The Simplex Theorem suggests a method for solving linear programs . It is called the Simplex Algorithm.

• The tableau in Step 2 is called the Simplex Tableau. It stores all the information required in the Simplex Theorem: matrix $A$ expressed in terms of basis $B$, $A^{-1}_BA$; the basic feasible solution excluding non-zero entries $A^{-1}_Bb$; the reduced cost vector $\tilde{c}^{\top}=c^{\top} - c_B^{\top} A^{-1}_B A$, and the cost of the current solution $c_B^{\top} A^{-1}_Bb$.
• The bottom row of the simplex tableau is called the objective row.
• Observe that the columns of the matrix $A^{-1}_BA$ corresponding to the basis $B$ necessary form an identity matrix. Note, by reading along the tableau, we can match each $1$ in this identity matrix to an entry of the column vector $A^{-1}_Bb$. From this, we can recover the bfs given by basis $B$, $x=(A^{-1}_Bb,0)$.
• The Simplex Algorithm also works for inequality constraints. For an optimization with inequality constraints $Ax\leq b$, when we add slack variables $z\geq 0$, we have equality constraints $Ax+Iz=b$. Observe for new matrix $A'=(A\; I)$, $(x,z)=(0,b)$ is a basic solution. Thus, provided $b>0$, $(x,z)=(0,b)$ is a basic feasible solution.
• In Step 3, we call $i$ the pivot row, $j$ the pivot column, and $(i,j)$ the pivot.

If Step 2 follows Step 3, we need to calculate $A^{-1}_{\tilde{B}}$ from $A^{-1}_{{B}}$. In other words, we need to apply operation $A^{-1}_{\tilde{B}}A_B$. We can break down Step 2 into the following routine

• In other words, The matrix $A^{-1}_BA$ is exactly the matrix formed by multiplying and adding rows of $A$ so that the resulting matrix has an identity matrix in the columns corresponding to basis $B$. The reduced cost vector $\tilde{c}^{\top}_B$ is exactly the vector formed by multiplying and adding rows of $A$ so that there are zeros in the components corresponding to basis $B$. Because these identity matrix and zero components are necessary, you can always tell if your simplex tableau is in the correct form.

In addition, Step 3 can be expressed in terms of the Simplex Tableau in the following way.

• In Step 3a, we do not include the final entry of the objective row in our calculations.
• In Step 3b, we do not include the entry $k$, corresponding to the objective row, in our calculations.

Let’s now go through a simple example in detail.

Example 1. $\:$

Answer 1. This is the same as

Let’s go through the steps of the algorithm.

Step 1: we find a basis. As we noted inequality constraints mean we can start with all slack variables in the basis.

Step 2: write out the simplex tableau:

The basis variables, $z_1$ and $z_2$, are starred and our current solution can be read from the final column: $(x,y,z_1,z_2)= (0,0,3,1)$. As required, there is an identity matrix beneath the basis variables; as required, there are zeros beneath basis variables in the objective row. So the tableau is in the correct form.

Step 3: the reduced cost for both variables $x$ and $y$ are negative: $-2$ and $-1$ respectively. Thus, we could pivot on either column. We decide to pivot on $x$. So, $x$ will be added to the basis. We need to remove a variable from the basis. We perform Step 3b.

The $x$-row divided by the final row gives $3/1$ and $1/1$. As $1$ is smallest we pivot on the second row. For book keeping, we place a box around the pivot. We now repeat to Step 2.

Step 2: For the matrix to be in the correct form, we must multiply and subtract the pivot row from all other rows so that the only non-zero entry in the pivot row is a $1$ at the pivot. In this case, the pivot row is in the correct form (the pivot contains a $1$), we deduce the pivot row from the 1st row, and we add two lots of the pivot row to the objective row. This gives a tableau

Step 3: The only negative reduced cost is for $y$. This gives the pivot column. The only positive term from Step 3b is from the first row; this is our pivot row.

Step 2: dividing the pivot row by $2$ and adding that to the 2nd row and three times to the objective row gives

The reduced costs in the objective row are all positive. Thus, the current solution is optimal. Once again we read this solution from the simplex tableau by associating basis variables with the final column through the $1$’s in the identity submatrix. In particular, $x=2$ and $y=1$ and the value of the maximum is $5$$\square$

We can make more general observations from our example, for the following optimization:

• Once slack variables are added to , these slack variables can form a basis with $A^{-1}_{B_z}=I$.
• If $b>0$ then $z=b$, $x=0$ forms a basic feasible solution, and since our objective does not constrain slack variables, the following tableau forms a correctly initialized simplex tableau

• Now considering this tableau again with respect to another basis, $B$. Letting $\lambda^{\top}=c^{\top}_{B}A_{B}^{-1}$ and $\tilde{x}=A_{B}^{-1}b$, we get

• From the tableau above, once again $\tilde{x}$ gives the values of basic variables; we can also find our current inverse matrix $A_B^{-1}$; we can find our dual variables $\lambda^{\top}$.
• The Simplex Algorithm maintains primal feasibility $\tilde{x}\geq 0$; as any variable in the basis has a zero in the objective row, the Simplex Algorithm maintains complementary slackness $\lambda^{\top} z=0$ and $(c^{\top}-\lambda^{\top} A)x=0$; when the Simplex Algorithm is complete the objective row is positive, so we have dual feasibility $\lambda^{\top} A\geq c^{\top}$ and $\lambda^{\top}\geq 0$.
• In other words, whilst maintaining primal feasibility and complementary slackness, we search for dual feasibility. Once this is found by Linear Programming Lemma 2, our solution is optimal both for the primal and dual problem.

# Two Phase Simplex

We consider the method of two stage simplex with the following example. which, adding slack variables, is equivalent to this first problem

Observe that, unlike before, setting $(x_1,x_2)=(0,0)$ does not yield a basic feasible solution. In particular, if $x_1=x_2=0$ then $z_1=-4$, $z_2=-1$ which are not feasible. So, we need to find a bfs to start from. The trick is to solve a different optimization problem whose optimal solution is a bfs for our original problem.

For example, we consider the second problem

• We added an extra variable $y$ to each constraint that was negative in our original problem. The positive variable $y=(y_1,y_2)$ tracts the amount we have violated any of our constraints.
• We then chose to minimize $y_1+y_2$ which we interpret as the total amount that we have violated our constraints.
• Note by adding these extra variables there is a bfs with $x_1=x_2=0$, where $(y_1,y_2,z_3)=(4,1,1)$. So, we can solve the second problem using the Simplex Algorithm.

Both problems have the same number of non-zero entries in a bfs, namely, $3$. There is a feasible solution to the first problem iff the optimal value of the second problem is zero. Thus, once we have solved the second problem, we will be at a basic feasible solution, where $y_1=y_2=0$. Removing variables $y_1$ and $y_2$, this is then a basic feasible solution to the first problem: all the violated constraints are satisfied and there are the right number of non-zero terms. So we should solve this problem in two phases:

Phase I: Solve the second problem, where we added additional variables for violated constraints.

Phase II: Removing the additional variables we have a bfs for the first problem. We then solve the second problem.

So now we can solve this problem using the Simplex algorithm in two phases:

Phase I:

We have written down the simplex tableau for the second problem and added an additional objective row for the objective of the first problem. Notice the simplex tableau is not in the correct form. First, we want $z_3$, $y_1$ and $y_2$ to be basis elements. So we need to multiply the 3rd row by $-1$. Second, the Phase I objective row contains non-zero entries above basic feasible variables $y_1$, $y_2$. So we need to subtract the first and second rows of the simplex tableau from the bottom objective row.

We now proceed to optimize the this tableau whilst treating the additional objective row as though it was just an additional constraint.

We are now at an optimal solution for the the first phase. In particular, we are at a basic feasible solution where $x_1=5/2$ and $x_2=3/2$. We can now remove $y_1$ and $y_2$, the bottom row and solve the second phase.

Phase II:

So we have now solved our original optimization problem. The optimal solution is $x_1=3$, $x_2=1$ with optimal value $5$.

# Dual Simplex

Dual simplex is another method for finding a basic feasible solution from a non-feasible basic solution. The Simplex Algorithm maintains feasibility of the primal problem; this is why we minimize ). The Simplex Algorithm searches for a solution that is dual feasible. The dual simplex takes a solution that is dual feasible and searches for a primal feasible solution.

We continue our example from the last section. Here we solved, . We now notice we forgot a constraints $3x_2\geq 4$. So we want to solve

Our previous optimal simplex tableau was

But now notice, our current solution $x_1=3$, $x_2=1$ is no longer feasible as $3x_2 < 4$. We now wish to solve this problem by adding this constraint and its a slack variable to our tableau:

Multiplying the $4$th row by $-1$ and then adding $3$ times the first row to the fourth puts the tableau in the correct form for our basis.

Our current basic solution has $z_4=-1$. So our basis is not feasible for our primal problem ; however, the objective row suggests a dual feasible solution. Note below our slack variables in our , our tableau contained a negative identity matrix $-I$, and $\lambda^\top=c_B^\top A^{-1}_B=(4/3,0,1/3,0)\geq 0$ and $c_B^\top - \lambda^\top A_B=0-\lambda^\top (-I) =(4/3,0,1/3,0)\geq 0$.

We select a pivot on rows that maintains dual feasibility and increases our objective to a primal feasible solution i.e. $A^{-1}_B b\geq 0$. We choose a row $i$ for which primal feasibility is violated i.e. $(A^{-1}_B)_i<0$. In our example, this is the $4$th row. We then divide the objective row with the negative entries from this row and find the least negative entries. In our example, the third column gives $(4/3)/-1= -4/3$ and the fifth column gives $(1/3) / -1= -1/3$. So as $-4/3 > -1/3$, we pivot on the fifth column. . This gives the tableau

Our current solution is feasible and, as our pivot kept our objective row positive, our solution is now optimal. In particular, $(x_1,x_2)=(8/3,4/3)$.

# Linear programming and simplex results

Theorem 1. The extreme points of $\mathcal X(b)=\{x: Ax=b, x\geq 0\}$ are exactly the set of basic feasible solutions.

Proof. Recall that we assume each $d\times d$ submatrix of $A$ is invertible. Thus for each basis, $B$ there is a unique basic feasible solution (bfs) $x=(x_B,0)$. Take this $x$ and suppose $x=p x^1 + (1-p)x^2$ for some $x_1=(x_B^1,x^1_N), x_2=(x_B^2,x^2_N)\in \mathcal X(b)$. If $x^1_N\neq 0$ then, because $px^1_N+(1-p)x^2_N=0$, then either $x_i^1<0$ for some $i\in N$ or $x_i^2<0$ for some $i\in N$, which contradicts the feasibility of $x^1$ and $x^2$. If $x^1_N=0$ then $x^2_N=0$ and so by uniqueness of bfs $x$, $x^1=x^2=x$. Thus any bfs $x$ is an extreme point.

Conversely, take any feasible $x$ that is not a basic feasible solution. Let $D=\{ i : x_i>0\}$ and $M=\{ i : x_i=0\}$ as $x$ is not a basic feasible solution $D$ has more than $d$ points. So the submatrix $A_D$ has linearly dependent columns, i.e. there exists a $y=(y_D,0)\neq 0$ such that $Ay=A_Dy_D=0$. Take $x^1=x+\delta y$, $x^2=x-\delta y$ where $\delta$ is sufficiently small so that $x_D \pm \delta y_D >0$. Since $Ax_1=Ax + \delta Ay=b+0=b$, $x_1$ and $x_2$ are feasible and also $\frac{1}{2} x^1+\frac{1}{2} x^2 = x$. So $x$ is not an extreme point. $\square$

Theorem 2. Any linear program with a finite optimum has at least one optimum at an extreme point.

Lemma 1. For a closed convex set $\mathcal C\subset \mathbb R^p$, if $\mathcal H=\{ x : a^\top x=c\}$ is a separating hyperplane, i.e. $\mathcal C \subset \{ x : a^\top x\geq c\}$, them an extreme point in $\mathcal H \cap \mathcal C$ is an extreme point in $\mathcal C$.

Proof. Assume $x=px_1+ (1-p)x_2$ for $x_1,x_2\in\mathcal C$ for $p\in (0,1)$. Then $c=a^\top x= p a^\top x_1 + (1-p) a^\top x_2$. By assumption $a^\top x_1\geq c$ and $a^\top x_2\geq c$. So, $a^\top x_1= c$ and $a^\top x_2= c$. Thus $x_1,x_2\in\mathcal H\cap\mathcal C$ but $x$ is an extreme point in $\mathcal H\cap \mathcal C$ so $x=x_1=x_2$. So $x$ is an extreme point in $\mathcal C$. $\square$

Theorem 3 [Carathéodory’s Theorem] Every closed bounded convex set $\mathcal C\subset \mathbb R^d$ has an extreme point and every point in $\mathcal C$ is a convex combination of its extreme points. Moreover, the number of extreme points required in this convex combination can be chosen to be less than or equal to $d+1$.

Proof. We prove the result by induction on $d$. For $d=1$, $\mathcal C$ is a closed bounded interval and the extreme points are the end points of the interval. Assuming the result holds for dimensions less than $d$, we prove the result for $d$. Firstly, note if $\mathcal C$ has empty interior then $\mathcal C$ is a subset of an affine space, $\mathcal A=\{ \lambda x_1 + (1-\lambda) x_2: x_1,x_2\in\mathcal C, \lambda\in\mathbb R\}$ and this space must have dimension of $d-1$ or less otherwise $\mathcal C$ would have a non-empty interior. In otherwords, if $\mathcal C^\circ=\emptyset$, then problem is immediately reduced to the $d-1$ dimensional case.

Take $x\in\mathcal C$ if $x$ is an extreme point then everything is trivial. So let’s suppose $x$ is not an extreme point, in which case there exist an $x_1,x_2\in\mathcal C$ and $p\in (0,1)$ such that $x=px_1+(1-p)x_2$ and $x_1\neq x_2$. Consider the line $x(\lambda)=\lambda x_1 + (1-\lambda)x_2$, for $\lambda\in\mathbb R$. Let $y_1=x(\lambda_1)$ where $\lambda_1$ is the largest $\lambda$ such that $x(\lambda)\in\mathcal C$ and let $y_2=x(\lambda_2)$ where $\lambda_2$ is the smallest $\lambda$ such that $x(\lambda)\in\mathcal C$. Note $y_1$ and $y_2$ are well defined because $\mathcal C$ is closed and bounded. It is also clear that $x=q y_1 + (1-q)y_2$ for some $q\in (0,1)$ and $y_1,y_2\notin \mathcal C^\circ$. Thus the applies to $y_1$ and $y_2$. Let $\mathcal H_1$ and $\mathcal H_2$ be the hyperplanes respectively sepaarating $y_1$ and $y_2$ from $\mathcal C$. Then $\mathcal H_1\cap \mathcal C$ and $\mathcal H_2\cap \mathcal C$ convex sets of dimension less than $d-1$. Thus by the induction hypothesis both $y_1$ and $y_2$ are a convex combination of the extreme points which exist in $\mathcal H_1\cap \mathcal C$ and $\mathcal H_2\cap \mathcal C$ respectively, which by Lemma 1 are extreme points of $\mathcal C$. So,as $x$ is a convex combination of $y_1$ and $y_2$, $x$ is a convex combination of extreme points existing in $\mathcal C$.

Now, we reduce the number of extreme points required to express $x$. Suppose $x=\sum_{i=1}^n p^i x^i$, where $\sum_{i=1}^n p^i =1$, $p_i>0$ and where each $x_i$ is an extreme point. If $n > d+1$ then the vectors $x^1-x^n, x^2- x^n,...,x^{n-1}- x^n$ are linearly dependent. Thus there exists $(q^1,...,q^{n-1})\neq 0$ where, defining $q_n=-\sum_{i=1}^n q^i$, we have $\sum_{i=1}^{n} q^i x^i = \sum_{i=1}^{n-1} q^i (x^i -x^n)=0$. Notice because $(q^1,...,q^{n-1})\neq 0$ and because by definition $\sum_{i=1}^n q^i=0$, there must exist some $q^i>0$ We, now, consider $\sum_{i=1}^n (p^i - t q^i)x^i$. If we take $t=\max_i \{p^i/q^i : q^i>0 \}$, then any $i$ maximizing this expression is zero in the sum $\sum_{i=1}^n (p^i - t q^i)x^i$. In otherwords, $x$ in now the convex combination of less than $n-1$ extreme points. Continuing inductively, we find $x$ can be expressed as the convex combination of $d+1$ points or less. $\square$

Proof of Theorem 2. Let $x^*$ be the finite optimum to a linear program with objective $c^\top x$ and feasible set given by polytope $\mathcal C\subset \mathbb R_+^p$. So for hyperplane $\mathcal H=\{ y : c^\top y =c^\top x^*\}$, $\mathcal H\cap \mathcal C$ defines a non-empty polytope of optimal solutions. We aim to apply Caratheodory’s Theorem. Since $\mathcal C\subset \mathbb R_+^p$, for $\mathbf{1}^\top x \geq 0$ for all $x\in\mathcal C$. Also note $\{x\in\mathbb R_+^p: \mathbf{1}^\top x=b\}$ is closed and bounded for all $b\geq 0$. Thus $b$, the minimum $\mathbf{1}^\top x$ over $x\in \mathcal H\cap \mathcal C$, is well defined and attained. Thus, as $\mathcal H'=\{ x\in \mathbb R_+^p: \mathbf{1} x=b\}$ is a closed bounded set and so $\mathcal H'\cap\mathcal H \cap \mathcal C$ is a closed bounded non-empty polytope of optimal solutions, which by Caratheordory’s Theorem must contain an extreme point. Applying Theorem 1 twice – once for $\mathcal H$ and once for $\mathcal H'$– this optimal point must be an extreme point in $\mathcal C$ also. $\square$

1. In this definition direction of an arc does not matter. This will soon make sense.
2. When $M_{ij}<\infty$ for some $(i,j)$, these comments hold for the enlarged matrix with slack variables appropriately added.
3. Our tree solution is different because our feasible solution is different.


text:
# The German Tank Problem

## Or Why To Obfuscate Your User IDs

(note, this is pulled largely from the Wikipedia page, where there is additional derivation of these equations. This post started as an exercise in understanding by explaining, and ended as an exercise in learning LaTex and seeing how high I could raise my blood pressure)

In World War II, Allied intelligence used conventional intelligence and statistical estimation to try to guess the production of German tanks.

The statistical estimates, which were based on a handful of serial numbers from captured tanks, turned out to be much, much more accurate.

From a frequentist perspective, this estimation is given by the formula:

$N = m + {m - k \over k}$

where m is the max serial number from the sample, and k is the size of the sample. Intuitively, this is sample maximum plus the average gap between observations in the sample

A Bayesian analysis yields a probability mass function.

$P(N = n) = \begin{cases} 0 & \quad \text{if } n < m\cr {k -1 \over k} {{ m - 1 \choose k - 1 } \over { n \choose k }} & \quad \text{otherwise} \end{cases}$

A probability mass function differs from a probability density function (pdf) in that the latter is associated with continuous rather than discrete random variables; the values of the latter are not probabilities as such: a pdf must be integrated over an interval to yield a probability. (source: Wikipedia)

From this we can get the mean and standard deviation of the distribution in order to estimate.

$N \approx \mu \pm \sigma$

The mean of a probability distribution is:

$\mu = \sum_{\substack{x}} xP(x)$

(Note: in wikipedia, this is referred to as “order of magnitude” – why?)

So, in this case it is:

$\mu = \sum_{\substack{n}} n \times (N = n \text{ | } M = m, K = k)$

Alright, so what’s the probability that N = n, given m and k?

Conditional probability tells us that:

$(n | m,k) = (m | n,k){(n | k) \over (m | k)}$

The first term on the right-hand side is the probability that the max serial number is equal to m, when n is known

The numerator of the second term is the credibility that the total number of tanks is equal to n when k tanks have been observed but before the serial numbers have been observed. Assume that it has a discrete uniform distribution.

The denominator is the probability that the maximum serial number is equal to m once k tanks have been observed but before the serial numbers have actually been observed. \scriptstyle (m\mid k) can be re-written in terms of the other quantities by marginalizing over all possible \scriptstyle n.

For k >= 4, there are formulas to get the mean and standard deviation (see wikipedia for derivation)


text:
# Portable byte order conversion

I'm trying to improve the portability of a file format converter, specifically to POSIX platforms other than Linux. I'd appreciate a review of the following functions used for converting between little endian and host endian 32bit unsigned integers and back. This is basically to replace le32toh and htole32 on platforms where they are not available. I'd particularly appreciate comments on whether this violates strict aliasing, I believe accessing integers through a char pointer is allowed but I'm not 100% sure.

I am intentionally writing endian-neutral code, performance is not so critical and simplicity, reusability and portability are more important to me. Determining endianness at compile time is difficult across compilers and operating systems, runtime checks either incur their own overhead if they need to be run on each function call or require a global variable.

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <inttypes.h>

uint32_t
le_u32_to_cpu(uint32_t le32)
{
unsigned char   *b = (unsigned char *)&le32;
uint32_t    cpu_u32 = b[0] | \
(b[1] << 8) | \
(b[2] << 16) | \
(b[3] << 24);

return (cpu_u32);
}

uint32_t
cpu_to_le_u32(uint32_t cpu_u32)
{
uint32_t    le_u32;
unsigned char   *b = (unsigned char *)&le_u32;

b[0] = cpu_u32 & 0xff;
b[1] = (cpu_u32 >> 8) & 0xff;
b[2] = (cpu_u32 >> 16) & 0xff;
b[3] = (cpu_u32 >> 24) & 0xff;

return (le_u32);
}

int
main(void)
{
uint32_t    x;
unsigned char   *b = (unsigned char *)&x;

b[0] = 0x11;
b[1] = 0x22;
b[2] = 0x33;
b[3] = 0x44;

puts("little endian");
for (size_t i = 0; i < 4; i++) {
printf("%02x\n", b[i]);
}
printf("0x%" PRIx32 "\n", x);

puts("cpu endianness");
x = le_u32_to_cpu(x);
for (size_t i = 0; i < 4; i++) {
printf("%02x\n", b[i]);
}
printf("0x%" PRIx32 "\n", x);

puts("back to little endian");
x = cpu_to_le_u32(x);
for (size_t i = 0; i < 4; i++) {
printf("%02x\n", b[i]);
}
printf("0x%" PRIx32 "\n", x);

return (0);
}

• why not use unions? Mar 2 '16 at 13:14
• well, why use unions, can you please elaborate the advantages of one over the other? Mar 2 '16 at 13:34
• AIUI if one of the types you're reinterpreting is not unsigned char, then the union would be necessary to avoid strict aliasing issues. float->uint32_t or double -> uint64_t would need a union. But unsigned char is the one escape valve type that allows pointer-punning for a reinterpretation of the stored object. ... Using a union might be better style since it extends to other conversions not involving unsigned char. Mar 2 '16 at 23:59

1. Very good that functions signatures use unsigned types.

2. Simplify code: If the routines are only called when the endian is backwards (Assume only big and little endian exist, no mixed endian), use the following and macro detection. For endian test, see here.

uint32_t endian_reverse32(uint32_t le32) {
return ((le32 &       0xFF) < 24) | \
((le32 &     0xFF00) <  8) | \
((le32 &   0xFF0000) >  8) | \
((le32 & 0xFF000000) > 24);
}

#if ENDIANNESS == LITTLE
#define le_u32_to_cpu(u32) ((uint32_t) u32)
#define cpu_to_le_u32(u32) ((uint32_t) u32)
#else
#define le_u32_to_cpu(u32) endian_reverse32(u32)
#define cpu_to_le_u32(u32) endian_reverse32(u32)
#endif

3. Else important: optimize code for platforms that do not need any endian adjustment: @JSY.
Cast result to insure consistent return type (or make inline()

#define le_u32_to_cpu(x) ((uint32_t)x)
#define cpu_to_le_u32(x) ((uint32_t)x)

4. Include routines to handle 16-bit and 64-bit.

5. 0xff mask not needed. If anything, to quiet conversion warnings use cast.

// b[1] = (cpu_u32 >> 8) & 0xff;
b[1] = cpu_u32 >> 8;

// quiet some warnings.
b[1] = (uint8_t)(cpu_u32 >> 8);

6. "I'd particularly appreciate comments on whether this violates strict aliasing... ". I do not believe it does. A simple solution is to use a union

uint32_t le_u32_to_cpu(uint32_t le32) {
union {
uint32_t u32;
uint8_t b[4];
} u = { le32 };

uint32_t cpu_u32 =   u.b[0] | \
((uint32_t) b[1] <<  8) | \
((uint32_t) b[2] << 16) | \
((uint32_t) b[3] << 24);
return cpu_32;
}

7. Style: Parens around return value are not needed.

8. Pedantic: use uint8_t. unsigned char could be 16-bit or wider. Better to fail the compilation if uint8_t does not exist.

uint8_t *b = (uint8_t *)&le32;

9. Pedantic: Should your wonderful code get ported to a place when unsigned is < 32 bit, only takes a little more to insure that portability.

uint8_t *b = (uint8_t *)&le32;
uint32_t cpu_u32 = b[0] | \
((uint32_t)b[1] << 8) | \
((uint32_t)b[2] << 16) | \
((uint32_t)b[3] << 24);

Final: Note, for maximum portability, code could even run on a 36-bit or 64-bit unsigned machine. Just swap 8-bit bytes of least 32-bits, zeroing out any more significant ones. No need for aliasing, pointers, etc.

    uint32least_t endian_reverse32(uint32least_t le32) {
return (uint32least_t) (
((le32 &       0xFFu) < 24) | \
((le32 &     0xFF00u) <  8) | \
((le32 &   0xFF0000u) >  8) | \
((le32 & 0xFF000000u) > 24));
}

#if ENDIANNESS == LITTLE
#define le_u32_to_cpu(u32) ((uint32least_t) (u32 & 0xFFFFFFFF))
#define cpu_to_le_u32(u32) ((uint32least_t) (u32 & 0xFFFFFFFF))
#else
#define le_u32_to_cpu(u32) endian_reverse32(u32)
#define cpu_to_le_u32(u32) endian_reverse32(u32)
#endif

• There are still microprocessor on which an unaligned memory access causes a fault. For that reason, I'd advise against the union approach if it's important to have truly portable code. Mar 2 '16 at 22:03
• @Edward. Using a union prevents unaligned memory access faults. Using a union increases portability concerning alignment. A union insures all fields are properly aligned. I am very familiar with this fault you speak of. Mar 2 '16 at 22:23
• Regarding 2. & 3.: see my edit above, 8.: POSIX guarantees that CHAR_BITS is 8 and I believe if uint8_t wouldn't be a typedef for unsigned char then your statement would violate strict aliasing anyway. Other that excellent comments. Mar 2 '16 at 23:32
• @chux: Yes, you're right. I was thinking of pointer access which I've also seen attempted for this purpose, but a union is indeed different. Thanks! Mar 3 '16 at 0:29

### Optimize for host endianness

On a little endian host, you shouldn't have to go through all that work to convert a little endian int to a little endian int (i.e. a nop). The tricky part is determining whether the host is little endian or not at compile time. One way is to check __BYTE_ORDER, which is defined by gcc. If your compiler does not define __BYTE_ORDER, you can look at this Stackoverflow question for alternative methods.

Here is how it could look:

#if !defined(__BYTE_ORDER)
# error Unknown endianness.
#endif

#if __BYTE_ORDER == __LITTLE_ENDIAN
# define le_u32_to_cpu(x) (x)
# define cpu_to_le_u32(x) (x)
#else
uint32_t
le_u32_to_cpu(uint32_t le32)
{
unsigned char   *b = (unsigned char *)&le32;
uint32_t    cpu_u32 = b[0] | \
(b[1] << 8) | \
(b[2] << 16) | \
(b[3] << 24);

return (cpu_u32);
}

uint32_t
cpu_to_le_u32(uint32_t cpu_u32)
{
uint32_t    le_u32;
unsigned char   *b = (unsigned char *)&le_u32;

b[0] = cpu_u32 & 0xff;
b[1] = (cpu_u32 >> 8) & 0xff;
b[2] = (cpu_u32 >> 16) & 0xff;
b[3] = (cpu_u32 >> 24) & 0xff;

return (le_u32);
}
#endif

• Actually I am intentionally writing endian-neutral code since performance is not so critical and determining endianness at compile time is messy and checking at runtime has its own issues. I will clarify my post accordingly. Mar 2 '16 at 23:12


text:
# Files, files everything is just a file!

GRR’s original design abstracted the data storage to a simple key/value store originally based around Bigtable. For open source deployments various key value stores were used starting from MongoDB, to SQLite and finally MySQL. Although the original idea was to use a simple key/value implementation, due to locking requirements the data store implementation became very complex.

As Velociraptor introduced a major redesign of the underlying data store architecture, we are now able to relax our demands of the datastore and use a true key/value model (since we have no requirements for locking and synchronization). The default data store is now the FileBasedDataStore which stores all data in flat files.

Using flat files over a database has many advantages, including ease of deployment, and simplification of the data model. Having flat files allows one to use standard tools to visualize Velociraptor’s data structures (e.g. with less), archive old data (e.g. with tar/zip) and clean up old data (e.g. with find/rm). Velociraptor also includes an inspect command which allows users to decode the stored files and provides context as to what these files actually mean. This simplicity increases the transparency in the system and makes it more accessible for deployers, while increasing reliability, stability and speed.

In the following section we examine some of the files in the datastore and see how they relate to the features we discuss elsewhere in this document.

## File organization

The Velociraptor data store needs to provide only two types of operations: Read and Write complete files and list files in a directory. Using only these primitives we can implement the entire filestore. Most modern file systems provide very fast file creation, reading and deletion, as well as fast directory listing, even when containing millions of files. Modern file systems also provide advanced features like caching, journaling and rollbacks so it is not such a crazy idea to use the file systems themselves as a data store.

Let’s begin by listing the files in a typical Velociraptor file store using the find command. We then use the velociraptor inspect command to view the file’s content.

### Searching

Searching for clients is implemented by simply creating empty files in directories based on the search term. For example in order to retrieve all clients which have the user “mic”, we simply list the directory “client_index/user%3Amic”:

 $find ./client_index/ ./client_index/c.84216c7aab97557d ./client_index/c.84216c7aab97557d/C.84216c7aab97557d.db./client_index/user%3Amic ./client_index/user%3Amic/C.84216c7aab97557d.db ./client_index/user%3Amic/C.1b0cddfffbfe40f5.db./client_index/all ./client_index/all/C.84216c7aab97557d.db ./client_index/all/C.1b0cddfffbfe40f5.db  Modern file systems can hold many thousands of files in the same directory and list these very quickly. This feature is only really used in the GUI’s search box but can also be used to script or post process collected data. ### Client information Information about each client is kept in a directory based on the client’s ID: ./C.0fc63b45671af1a6/ping.db <- Last ping stats. ./C.0fc63b45671af1a6/key.db <- Client's public key ./C.0fc63b45671af1a6/flows ./C.0fc63b45671af1a6/flows/F.a8787c26.db <- Flows running on this client. ./C.0fc63b45671af1a6/flows/F.e05952ff.db ./C.0fc63b45671af1a6/tasks ./C.0fc63b45671af1a6/tasks/1533517805834284.db <- Client messages waiting to be collected. ./C.0fc63b45671af1a6/tasks/1533517805834283.db ./C.0fc63b45671af1a6/tasks/1533517206859989.db ./C.0fc63b45671af1a6/tasks/1533517206860477.db ./C.84216c7aab97557d.db <- Client information (from Interrogate).  Each piece of data is kept in its own file as an encoded protobuf. Files all have their names end with “.db”. Velociraptor has an inspect command which decodes the protobuf and displays it in a human friendly way. For example let us see what information we keep about each s last poll: $ velociraptor --config server.yaml inspect /tmp/velociraptor/C.2d406f47d80f5583/ping.db
{
"ipAddress": "127.0.0.1:33600","ping": "1533517053018582"
}

### The Flow’s results.

Velociraptor’s flows typically only produce VQL results. As described above, the VQL results are typically split into parts by the client (by default 10000 rows per part), and Velociraptor simply writes these in the flow’s directory:

./C.1b0cddfffbfe40f5/flows/F.a31255a1
./C.1b0cddfffbfe40f5/flows/F.a31255a1/results
./C.1b0cddfffbfe40f5/flows/F.a31255a1/results/0.db   <- VQL result part 1.
./C.1b0cddfffbfe40f5/flows/F.a31255a1.db             <- Flow information.

Velociraptor’s inspect command understands that VQL collections represent a table of results, and so it displays these in a more friendly way.

$velociraptor --config server.yaml inspect /tmp/velociraptor/C.1b0cddfffbfe40f5/flows/F.a31255a1/results/0.db +-------+----------------+---------+------+-----------------------------+----------------------------+ | ISDIR | FULLPATH | SIZE | MODE | MTIME | ATIME | +-------+----------------+---------+------+-----------------------------+----------------------------+ | false | /bin/bash | 1037528 | 493 | 2017-05-16T22:49:55+10:00 | 2018-01-22T12:47:25+10:00 | | false | /bin/busybox | 1964536 | 493 | 2015-08-19T22:07:39+10:00 | 2018-01-23T15:41:46+10:00 | +-------+----------------+---------+------+-----------------------------+----------------------------+ File Finder Response: SELECT IsDir , FullPath , Size , Mode , mtime , atime , ctime, upload(file=FullPath)as Upload FROM files  We can also see the original VQL query which was run to produce this output. The bottom line, though, is that the entire flow’s result is just a flat JSON encoded file. You can easily decode the data using any programming language and post process it in whatever way is appropriate (e.g. export the results to BigQuery or ElasticSearch). Velociraptor does not really do anything with the result other than just store it on disk. ### The Virtual File System As described above, Velociraptor’s VFS consists of VQL tables for each directory on the client, listing the entire directory content: ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/gir1.2-freedesktop.db ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/libdatrie1.db ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/dh-strip-nondeterminism.db ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/libcap2-bin.db ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/libsoup2.4-1.db ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/libgphoto2-port12.db ./C.1b0cddfffbfe40f5/vfs/usr/share/doc/libsodium18.db  Inspecting each of these shows it is just a simple VQL table. This particular VFS entry was produced from a recursive directory listing of /usr (of depth 5). $ velociraptor --config server.yaml inspect .../vfs/usr/share/doc/libcap2-bin.db
+-------+--------------------------------+---------------------+------+-----------+--------------------
| ISDIR |            FULLPATH            |        NAME         | SIZE |   MODE    |           MTIME
+-------+--------------------------------+---------------------+------+-----------+--------------------
| false | /usr/share/doc/libcap2-bin/REA | README.Debian       | 1149 |       420 | 2015-10-02T23:34:07
|       | DME.Debian                     |                     |      |           |
| false | /usr/share/doc/libcap2-bin/cha | changelog.Debian.gz |   30 | 134218239 | 2015-10-24T07:11:34
|       | ngelog.Debian.gz               |                     |      |           |
| false | /usr/share/doc/libcap2-bin/cop | copyright           | 4367 |       420 | 2015-10-02T23:34:07
|       | yright                         |                     |      |           |
+-------+--------------------------------+---------------------+------+-----------+--------------------
/usr: SELECT IsDir, FullPath as _FullPath, Name, Size, Mode, timestamp(epoch=Sys.Mtim.Sec) as mtime,
timestamp(epoch=Sys.Atim.Sec) as ys.Ctim.Sec) as ctime FROM glob(globs=path + '/**5')