3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Do you think I can easily find some conditions that imply this will always hold? $\endgroup$ – independentvariable Mar 16 at 16:21
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Mar 16 at 16:39
4
$\begingroup$

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^*$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.