\( \newcommand{\bm}[1]{\boldsymbol{#1}} \newcommand{\textm}[1]{\textsf{#1}} \newcommand{\textnormal}[1]{\textsf{#1}} \def\T{{\mkern-2mu\raise-1mu\mathsf{T}}} \newcommand{\R}{\mathbb{R}} % real numbers \newcommand{\E}{{\rm I\kern-.2em E}} \newcommand{\w}{\bm{w}} % bold w \newcommand{\bmu}{\bm{\mu}} % bold mu \newcommand{\bSigma}{\bm{\Sigma}} % bold mu \newcommand{\bigO}{O} %\mathcal{O} \renewcommand{\d}[1]{\operatorname{d}\!{#1}} \)

Exercises

Exercise B.1 (Euclidean norm approximation)

  1. Randomly generate the parameters \(\bm{A}\in\R^{10\times5}\) and \(\bm{b}\in\R^{10}\).
  2. Formulate a regression problem to approximate \(\bm{A}\bm{x} \approx \bm{b}\) based on the \(\ell_2\)-norm.
  3. Solve it directly with the least squares closed-form solution.
  4. Solve it using a modeling framework (e.g., CVX).
  5. Solve it invoking a QP solver.

Exercise B.2 (Manhattan norm approximation)

  1. Randomly generate the parameters \(\bm{A}\in\R^{10\times5}\) and \(\bm{b}\in\R^{10}\).
  2. Formulate a regression problem to approximate \(\bm{A}\bm{x} \approx \bm{b}\) based on the \(\ell_1\)-norm.
  3. Solve it using a modeling framework (e.g., CVX).
  4. Rewrite it as an LP and solve it invoking an LP solver.

Exercise B.3 (Chebyshev norm approximation)

  1. Randomly generate the parameters \(\bm{A}\in\R^{10\times5}\) and \(\bm{b}\in\R^{10}\).
  2. Formulate a regression problem to approximate \(\bm{A}\bm{x} \approx \bm{b}\) based on the \(\ell_\infty\)-norm.
  3. Solve it using a modeling framework (e.g., CVX).
  4. Rewrite it as an LP and solve it invoking an LP solver.

Exercise B.4 (Solving an LP) Consider the following LP: \[ \begin{array}{ll} \underset{x_1,x_2}{\textm{maximize}} & 3x_1 + x_2\\ \textm{subject to} & x_1 + 2x_2 \leq 4,\\ & 4x_1 + 2x_2 \leq 12,\\ & x_1, x_2 \geq 0. \end{array} \]

  1. Solve it using a modeling framework (e.g., CVX).
  2. Solve it by directly invoking an LP solver.
  3. Solve it by invoking a general-purpose nonlinear solver.
  4. Implement the projected gradient method to solve the problem.
  5. Implement the constrained Newton’s method to solve the problem.
  6. Implement the log-barrier interior-point method to solve the problem (use (1,1) as the initial point).
  7. Compare all the solutions and the computation time.

Exercise B.5 (Central path) Formulate the log-barrier problem corresponding to the LP in Exercise B.4 and plot the central path as the parameter \(t\) varies.

Exercise B.6 (Phase I method) Design a phase I method to find a feasible point for the LP in Exercise B.4, which can then be used as the starting point for the barrier method.

Exercise B.7 (Dual problem) Formulate the dual problem corresponding to the LP in Exercise B.4 and solve it using a solver of your choice.

Exercise B.8 (KKT conditions) Write down the Karush–Kuhn–Tucker (KKT) conditions for the LP in Exercise B.4 and discuss their role in determining the optimality of a solution.

Exercise B.9 (Solving a QP) Consider the following QP: \[ \begin{array}{ll} \underset{x_1,x_2}{\textm{maximize}} & x_1^2 + x_2^2\\ \textm{subject to} & x_1 + x_2 = 1,\\ & x_1 \geq 0, x_2 \geq 0. \end{array} \]

  1. Solve it using a modeling framework (e.g., CVX).
  2. Solve it by directly invoking a QP solver.
  3. Solve it by invoking a general-purpose nonlinear solver.
  4. Implement the projected gradient method to solve the problem.
  5. Implement the constrained Newton’s method to solve the problem.
  6. Implement the log-barrier interior-point method to solve the problem (use (0.5,0.5) as the initial point).
  7. Compare all the solutions and the computation time.

Exercise B.10 (Fractional programming) Consider the following fractional program: \[ \begin{array}{ll} \underset{\w}{\textm{maximize}} & \dfrac{\w^\T\bm{1}}{\sqrt{\w^\T\bSigma\w}}\\ \textm{subject to} & \bm{1}^\T\w=1, \quad \w\ge\bm{0}, \end{array} \] where \(\bSigma \succ \bm{0}\).

  1. Solve it with a general-purpose nonlinear solver.
  2. Solve it via bisection.
  3. Solve it via the Dinkelbach method as a sequence of SOCPs.
  4. Develop a modified algorithm that solves the problem as a sequence of QPs instead.
  5. Solve it via the Schaible transform method.
  6. Reformulate the problem as a minimization and then solve it via the Schaible transform method.
  7. Compare all the previous approaches in terms of the accuracy of the solution and the computation time.

Exercise B.11 (Soft-thresholding operator) Consider the following convex optimization problem: \[ \begin{array}{ll} \underset{x}{\textm{minimize}} & \frac{1}{2}\|\bm{a}x - \bm{b}\|_2^2 + \lambda|x|, \end{array} \] with \(\lambda\geq0\). Derive the solution and show that it can be written as \[ x = \frac{1}{\|\bm{a}\|_2^2} \mathcal{S}_\lambda\left(\bm{a}^\T\bm{b}\right), \] where \(\mathcal{S}_\lambda(\cdot)\) is the so-called soft-thresholding operator defined as \[\mathcal{S}_\lambda(u) = \textm{sign}(u)(|u| - \lambda)^+,\] with \(\textm{sign}(\cdot)\) denoting the sign function and \((\cdot)^+=\textm{max}(0,\cdot)\).

Exercise B.12 (\(\ell_2\)–\(\ell_1\)-norm minimization) Consider the following \(\ell_2\)–\(\ell_1\)-norm minimization problem (with \(\bm{A}\in\R^{10\times5}\) and \(\bm{b}\in\R^{10}\) randomly generated): \[ \begin{array}{ll} \underset{\bm{x}}{\textm{minimize}} & \frac{1}{2}\|\bm{A}\bm{x} - \bm{b}\|_2^2 + \lambda\|\bm{x}\|_1. \end{array} \]

  1. Solve it using a modeling framework (e.g., CVX).
  2. Rewrite the problem as a QP and solve it by invoking a QP solver.
  3. Solve it with an ad hoc LASSO solver.

Exercise B.13 (BCD for \(\ell_2\)–\(\ell_1\)-norm minimization) Solve the \(\ell_2\)–\(\ell_1\)-norm minimization problem in Exercise B.12 via BCD. Plot the convergence vs. iterations and CPU time.

Exercise B.14 (MM for \(\ell_2\)–\(\ell_1\)-norm minimization) Solve the \(\ell_2\)–\(\ell_1\)-norm minimization problem in Exercise B.12 via MM and its accelerated version. Plot the convergence vs. iterations and CPU time.

Exercise B.15 (SCA for \(\ell_2\)–\(\ell_1\)-norm minimization) Solve the \(\ell_2\)–\(\ell_1\)-norm minimization problem in Exercise B.12 via SCA. Plot the convergence vs. iterations and CPU time.

Exercise B.16 (ADMM for \(\ell_2\)–\(\ell_1\)-norm minimization) Solve the \(\ell_2\)–\(\ell_1\)-norm minimization problem in Exercise B.12 via ADMM. Plot the convergence vs. iterations and CPU time.