Minimizing a variable over the intersection of simplex and linear constraints

Question

I am solving:

\begin{align} \begin{array}{rll} y^* = \min & y & \\ \mathrm{s.t.} & a_i^\top x \leq y, & i=1,\ldots,m \\ & x \succeq 0,\ \mathbf{1}^\top x = 1. & \end{array} \end{align} My variables are $x \in \mathbb{R}^n$ and $y \in \mathbb{R}$. Notice that the second line of constraints define a unit $n$-dimensional simplex for $x$. Assume the minimum value is $y^*$. Under what conditions $y^*$ is still the optimal value of the following problem: \begin{align} \begin{array}{rll} y^{**} =\min & y & \\ \mathrm{s.t.} & a_i^\top x \leq y, & i=1,\ldots,m \\ & x \succeq 0,\ \mathbf{1}^\top x \leq 1. & \end{array} \end{align} Notice that only the $\mathbf{1}^\top x =1$ is changed to $\mathbf{1}^\top x \leq 1$.

Edit: I refined my question thanks to Mark L. Stone.

Answer 1

You can say it, but you'd be incorrect.

Consider the very simple counterexample, $n = m = 1, a_i = 1$. Then the solution to the first problem is $x^{*} = y^* = 1.$. And the solution to the second problem is $x^{**} = y^{**} = 0$.

Answer 2

To answer the revised question, $y^{**}=y^*$ if and only if $y^*\le 0$. Your original problem looks at all convex combinations of the columns of the $A$ matrix. The modified problem is equivalent to looking at all convex combinations of the columns of $\overline{A}$, where $\overline{A}$ is $A$ augmented by a column of zeros. So think of the second problem as using $\overline{A}$ (and raising the dimension of $x$ by one) while continuing to require the sum of the (expanded) $x$ vector to equal 1. Ask yourself how "diluting" a solution to the original problem by "mixing in" a zero vector could help.

For any $x$ feasible in the original problem and any $\lambda\in [0,1]$, $\left[\begin{array}{c}\lambda x\\1-\lambda\end{array}\right]$ is feasible in the modified problem. Let $x^*$ be optimal in the original problem, so that $Ax^*\le y^* e$ with $e=(1,\dots,1)^\prime$, and choose $\lambda = \frac{1}{2}$. Then $$\overline{A}\left[\begin{array}{c}\frac{1}{2} x^*\\1-\frac{1}{2}\end{array}\right]=\lambda Ax^* + (1-\lambda)0\le \lambda y^* e$$ in the revised problem, from which it follows that $y^{**} \le \lambda y^*$. So $$y^{**}=y^* \implies y^* \le \lambda y^* \implies y^* \le 0.$$ That's the necessity part.

Sufficiency can be proved by contradiction. Assume that $y^* \le 0$ and that $y^{**} \lt y^*$. Let $x^* = \left[\begin{array}{c}\hat{x}\\x_0\end{array}\right]$ be optimal in the modified problem, meaning $A\hat{x} + x_0 \cdot 0\le y^{**} e$. Since $y^{**} \lt y^* \le 0$, clearly $x_0 \lt 1$. In that case, $x=\frac{1}{1-x_0}\hat{x}$ is feasible in the original problem with $$Ax=\frac{1}{1-x_0}A\hat{x}\le \frac{1}{1-x_0} y^{**}e \lt \frac{1}{1-x_0}y^* e\le y^* e$$which contradicts the optimality of $y^*$.