# Minimizing a variable over the intersection of simplex and linear constraints

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.

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$$.
• Almost tautological, but if $1^Tx = 1$ holds in the solution to the 2nd problem (more specifically, that there is at least one optimal $x$, such that it holds), then the first problem has the same solution as the 2nd.. The 2nd problem is a relaxation of the first, so I just stated the (tautological) condition such that the relaxation is tight. Mar 16 '20 at 16:39
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^*$$.