数学代写|ENGG5501 Convex Optimization

MY-ASSIGNMENTEXPERT™可以为您提供users.cse.umn.edu Math8306 Algebraic topology 代数拓扑的代写代考和辅导服务！

ENGG5501课程简介

Announcements

NEW: Here is the solution to Homework 5.

Here is the midterm solution.

The lecture videos can be accessed from Blackboard or via the link provided on Piazza.

Welcome to ENGG 5501! Students who are interested in taking the course but have not yet registered (or are not able to register) should contact the course instructor.

To better facilitate discussions and Q&As, we have set up a forum on Piazza. Please follow this link to sign up.

Prerequisites 

Course Description

In this course we will develop the basic machinery for formulating and analyzing various optimization problems. Topics include convex analysis, linear and conic linear programming, nonlinear programming, optimality conditions, Lagrangian duality theory, and basics of optimization algorithms. Applications from different fields, such as combinatorial optimization, communications, computational economics and finance, machine learning, and signal and image processing, will be used to complement the theoretical developments. No prior optimization background is required for this class. However, students should have workable knowledge in multivariable calculus, real analysis, linear algebra and matrix theory.

ENGG5501 Convex Optimization HELP（EXAM HELP， ONLINE TUTOR）

We can formulate the problem as a linear program as follows:

\begin{align*} \max \quad & \sum_{i=1}^{n} y_i \ \text{s.t.} \quad & Ax = \mathbf{0} \ & x_i \geq 0, \quad i=1,2,\dots,n \ & y_i \geq x_i, \quad i=1,2,\dots,n \end{align*}

The decision variables are $x_i$ and $y_i$, for $i=1,2,\dots,n$. The objective function maximizes the number of positive components of $x$, which is equivalent to maximizing the sum of $y_i$ over all $i$.

The first constraint ensures that $Ax=\mathbf{0}$, i.e., $x$ is a feasible solution to the system of linear equations $Ax=\mathbf{0}$.

The second constraint enforces that each component of $x$ is nonnegative.

The third constraint ensures that $y_i$ is at least as large as $x_i$ for all $i$, so that the number of positive components of $x$ is maximized.

To see why this formulation is correct, suppose $x$ is a feasible solution to the system of linear equations $Ax=\mathbf{0}$ with $k$ positive components. Then we can set $y_i=x_i$ for all positive components $i$ of $x$, and $y_i=0$ for all other components. This is a feasible solution to the linear program, and its objective value is $k$. Conversely, if $y$ is a feasible solution to the linear program with objective value $k$, then we can set $x_i=y_i$ for all positive components $i$ of $y$, and $x_i=0$ for all other components. This is a feasible solution to the system of linear equations $Ax=\mathbf{0}$ with $k$ positive components. Therefore, the linear program and the original problem are equivalent.

(a) To show that $S$ is convex, we need to show that for any $x, y \in S$ and any $\lambda \in [0,1]$, we have $\lambda x+(1-\lambda) y \in S$. Let $x, y \in S$ be arbitrary. Then we have $x^T A x+b^T x+c \leq 0$ and $y^T A y+b^T y+c \leq 0$. Now consider the point $\lambda x+(1-\lambda) y$. We have:

\begin{align*} &(\lambda x+(1-\lambda) y)^T A (\lambda x+(1-\lambda) y)+b^T (\lambda x+(1-\lambda) y)+c \ &=\lambda^2 x^T A x+\lambda(1-\lambda) x^T A y+(1-\lambda)^2 y^T A y+b^T \lambda x+b^T (1-\lambda) y+c \ &=\lambda(\lambda x^T A x+b^T x+c)+(1-\lambda)(y^T A y+b^T y+c)+\lambda(1-\lambda)(x^T A y+y^T A x)+\lambda b^T x+(1-\lambda) b^T y \ &\leq \lambda \cdot 0+(1-\lambda) \cdot 0+\lambda(1-\lambda)(x^T A y+y^T A x)+\lambda \cdot 0+(1-\lambda) \cdot 0 \ &=\lambda(1-\lambda)(x^T A y+y^T A x). \end{align*}

Since $A \succeq \mathbf{0}$, we have $x^T A y+y^T A x \geq 2 \sqrt{x^T A x y^T A y} \geq 0$. Therefore, we have $(\lambda x+(1-\lambda) y)^T A (\lambda x+(1-\lambda) y)+b^T (\lambda x+(1-\lambda) y)+c \leq 0$, so $\lambda x+(1-\lambda) y \in S$. Therefore, $S$ is convex.

The converse is not true. To see this, consider the set $S=\left{x \in \mathbb{R}^2: x_1 x_2 \leq 0\right}$. This set is convex, but the matrix $A=\begin{bmatrix} 0 & 1 \ 1 & 0 \end{bmatrix}$ is not positive semidefinite.

(b) The set $S=\left{X \in \mathcal{S}^n: \lambda_{\max }(X) \geq 1\right}$ is not convex. To see this, consider the matrices $X=\begin{bmatrix} 2 & 0 \ 0 & 0 \end{bmatrix}$ and $Y=\begin{bmatrix} 0 & 0 \ 0 & 2 \end{bmatrix}$, which both belong to $S$. However, the matrix $\frac{1}{2}X+\frac{1}{2}Y=\begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix}$ does not belong to $S$, since its largest eigenvalue is $1$. Therefore, $S$ is not convex.

MY-ASSIGNMENTEXPERT™可以为您提供UNIVERSITY OF ILLINOIS URBANA-CHAMPAIGN MATH2940 linear algebra线性代数课程的代写代考和辅导服务！ 请认准MY-ASSIGNMENTEXPERT™. MY-ASSIGNMENTEXPERT™为您的留学生涯保驾护航。