数学代写|EE364A convex optimization
Statistics-lab™可以为您提供stanford.edu EE364A convex optimization凸优化课程的代写代考和辅导服务！
EE364A convex optimization课程简介
Concentrates on recognizing and solving convex optimization problems that arise in engineering. Convex sets, functions, and optimization problems. Basics of convex analysis. Least-squares, linear and quadratic programs, semidefinite programming, minimax, extremal volume, and other problems. Optimality conditions, duality theory, theorems of alternative, and applications. Interiorpoint methods. Applications to signal processing, control, digital and analog circuit design, computational geometry, statistics, and mechanical engineering.
PREREQUISITES
Prerequisites: Good knowledge of linear algebra. Exposure to numerical computing, optimization, and application fields helpful but not required; the engineering applications will be kept basic and simple.
- Syllabus
- DOWNLOAD All Course Materials
EE364A convex optimization HELP（EXAM HELP， ONLINE TUTOR）
Let $C \subseteq \mathbf{R}^n$ be a convex set, with $x_1, \ldots, x_k \in C$, and let $\theta_1, \ldots, \theta_k \in \mathbf{R}$ satisfy $\theta_i \geq 0$, $\theta_1+\cdots+\theta_k=1$. Show that $\theta_1 x_1+\cdots+\theta_k x_k \in C$. (The definition of convexity is that this holds for $k=2$; you must show it for arbitrary $k$.) Hint. Use induction on $k$.
Solution. This is readily shown by induction from the definition of convex set. We illustrate the idea for $k=3$, leaving the general case to the reader. Suppose that $x_1, x_2, x_3 \in C$, and $\theta_1+\theta_2+\theta_3=1$ with $\theta_1, \theta_2, \theta_3 \geq 0$. We will show that $y=\theta_1 x_1+\theta_2 x_2+\theta_3 x_3 \in C$. At least one of the $\theta_i$ is not equal to one; without loss of generality we can assume that $\theta_1 \neq 1$. Then we can write
$$
y=\theta_1 x_1+\left(1-\theta_1\right)\left(\mu_2 x_2+\mu_3 x_3\right)
$$
where $\mu_2=\theta_2 /\left(1-\theta_1\right)$ and $\mu_2=\theta_3 /\left(1-\theta_1\right)$. Note that $\mu_2, \mu_3 \geq 0$ and
$$
\mu_1+\mu_2=\frac{\theta_2+\theta_3}{1-\theta_1}=\frac{1-\theta_1}{1-\theta_1}=1 .
$$
Since $C$ is convex and $x_2, x_3 \in C$, we conclude that $\mu_2 x_2+\mu_3 x_3 \in C$. Since this point and $x_1$ are in $C, y \in C$.
The proof is by induction on $k$.
For the base case $k=2$, we have $x_1, x_2 \in C$ and $\theta_1+\theta_2=1$. Since $C$ is convex, we have that $\theta_1 x_1 + \theta_2 x_2 \in C$.
For the induction step, assume that the statement is true for $k-1$, i.e., for any $k-1$ points $y_1, \ldots, y_{k-1} \in C$ and $\alpha_1, \ldots, \alpha_{k-1} \in \mathbf{R}$ such that $\alpha_i \geq 0$ and $\alpha_1 + \cdots + \alpha_{k-1} = 1$, we have that $\alpha_1 y_1 + \cdots + \alpha_{k-1} y_{k-1} \in C$.
Now consider $k$ points $x_1, \ldots, x_k \in C$ and $\theta_1, \ldots, \theta_k \in \mathbf{R}$ such that $\theta_i \geq 0$ and $\theta_1 + \cdots + \theta_k = 1$. We want to show that $\theta_1 x_1 + \cdots + \theta_k x_k \in C$.
Without loss of generality, assume that $\theta_k \neq 1$ (if it were, we could remove it and the result would still hold by the induction hypothesis). Define $\alpha_i = \frac{\theta_i}{1-\theta_k}$ for $i=1,\ldots, k-1$, and define $y_i = x_i$ for $i=1,\ldots, k-1$ and $y_{k-1} = \frac{\theta_1}{1-\theta_k} x_1 + \cdots + \frac{\theta_{k-1}}{1-\theta_k} x_{k-1}$. Note that $\alpha_i \geq 0$ and $\alpha_1 + \cdots + \alpha_{k-1} = 1$.
By the induction hypothesis, we have that $\alpha_1 y_1 + \cdots + \alpha_{k-1} y_{k-1} \in C$. But
\begin{align*} \alpha_1 y_1 + \cdots + \alpha_{k-1} y_{k-1} &= \frac{\theta_1}{1-\theta_k} x_1 + \cdots + \frac{\theta_{k-1}}{1-\theta_k} x_{k-1} \ &= \frac{\theta_1}{1-\theta_k} x_1 + \cdots + \frac{\theta_{k-1}}{1-\theta_k} x_{k-1} + \frac{\theta_k}{1-\theta_k} x_k \ &= \theta_1 x_1 + \cdots + \theta_{k-1} x_{k-1} + \theta_k x_k \ &= \theta_1 x_1 + \cdots + \theta_k x_k, \end{align*}
so we have that $\theta_1 x_1 + \cdots + \theta_k x_k \in C$, as desired.
Show that a set is convex if and only if its intersection with any line is convex. Show that a set is affine if and only if its intersection with any line is affine.
Solution. We prove the first part. The intersection of two convex sets is convex. Therefore if $S$ is a convex set, the intersection of $S$ with a line is convex.
Conversely, suppose the intersection of $S$ with any line is convex. Take any two distinct points $x_1$ and $x_2 \in S$. The intersection of $S$ with the line through $x_1$ and $x_2$ is convex. Therefore convex combinations of $x_1$ and $x_2$ belong to the intersection, hence also to $S$.
We prove the second part. Let $A$ be an affine set. Let $L$ be a line, and let $x_1$ and $x_2$ be two points in $A \cap L$. Let $y$ be any point on $L$. We need to show that $\theta x_1 + (1-\theta) x_2 + \lambda(y-x_1)$ is in $A$ for any $\theta, \lambda \in \mathbb{R}$ with $\theta + \lambda = 1$. Note that $\lambda(y-x_1) + x_1$ is a point on $L$ that is $\lambda$ times the distance from $y$ to $x_1$ along $L$ away from $x_1$. Let $z$ be the point on $L$ that is $\theta$ times the distance from $x_1$ to $x_2$ away from $x_1$. Then $z$ is a convex combination of $x_1$ and $x_2$, so $z \in A$ by the assumption that $A \cap L$ is affine. Therefore $\lambda(y-x_1) + x_1 + z$ is a convex combination of $x_1, x_2$, and $y$, and is thus in $A$.
Conversely, suppose that $A$ intersects every line in an affine set. Let $x_1, x_2 \in A$, and let $L$ be the line through $x_1$ and $x_2$. Then $A \cap L$ is affine by assumption, so any convex combination of $x_1$ and $x_2$ that lies on $L$ is in $A$. Since any point on the line through $x_1$ and $x_2$ can be written as a convex combination of $x_1$ and $x_2$, we conclude that $A$ is affine.
Textbooks
• An Introduction to Stochastic Modeling, Fourth Edition by Pinsky and Karlin (freely
available through the university library here)
• Essentials of Stochastic Processes, Third Edition by Durrett (freely available through
the university library here)
To reiterate, the textbooks are freely available through the university library. Note that
you must be connected to the university Wi-Fi or VPN to access the ebooks from the library
links. Furthermore, the library links take some time to populate, so do not be alarmed if
the webpage looks bare for a few seconds.
Statistics-lab™可以为您提供stanford.edu EE364A convex optimization凸优化课程的代写代考和辅导服务！ 请认准Statistics-lab™. Statistics-lab™为您的留学生涯保驾护航。