More Optimization Problems

We write the problem first in its default form

Where

The dual problem is then

We draw the condition on paper

The solution is the line between (4,4) and (6, 0) with the maxiumum value of 12.

The system has a solution if and only if Phase 1 of the Simplex algorithm provides a solution. To achieve this, we introduce a variable \( x_5 \) for the third condition in order to bring the problem into normal form.

Then, we write our problem as a tableau

The pivot element is in the first row and first column since it has the smallest pivot.

We now look at the second column.

Case 1: \( \beta \geq 3 \) Then, the pivot is in the first row.

Thus we get

And hence

Thus, we are done and have found a solution with

Case 2: \( 2 \leq \beta \leq 3 \) Then, the pivot is in the second row.

Hence

And thus, we are done with the solution

a)
First, we determine the Hessian matrix of the function. The first derivative is

Thus, the Hessian matrix is

We determine whether the matrix is positive semidefinite and for which values by using the minors.

That is, the matrix is semidefinite, and therefore the function \( f \) is convex, if and only if \( a \geq 0 \) and \( ab \geq 4 \).

b) For the minimum value, \(\nabla f = 0\) has to be true

It follows that \( b = 0 \) and \( a = 3 \). Due to the condition \( ab \geq 4 \), the problem is not convex in this case.

For

this means that \( (1,1) \) is not a local minimum.

a)
The objective function is continuous. Furthermore, \( M \) is bounded because \( 0 < x^T B x \leq 1 \), and it is closed, thus compact. Since the objective function is continuous and the constraint set is compact, there exists a local solution (LSG).

b)
Since \( A \) has full rank, both \( A \) and \( A^T \) are bijective. Assume \( A B^{-1} A^T x = 0 \).
Let \( x A B^{-1} A^T x = (A^T x)^T B^{-1} (A^T x) = y^T B^{-1} y \). Then \( y^T B^{-1} y = 0 \) if and only if \( y = 0 \), because \( B^{-1} \) is positive definite.
It follows that \( x = 0 \). Thus, \( A B^{-1} A^T \) is bijective and, therefore, regular.

c)
The problem is convex because \( f(x) = c^T x \) and \( g(x) = x^T B x - 1 \) are convex, as \( B \) is symmetric and positive definite.

The Slater condition holds because:

• The rank of \( A \) is maximal.
• \( A x' = 0 \) and \( g(x') < 0 \), with \( x' = 0 \).

Thus, there is no duality gap, and a local solution (LSG) exists. We obtain this LSG using the Lagrange multiplier theorem, i.e.,

For the LSG to hold, the following must be true:

In particular, \( x^* \neq 0 \), because otherwise, \( u = 0 \) must hold due to the second condition, but then we would have \( c = 0 \) from the first condition, which is impossible according to the assumption, as it would then lie in the image of \( A^T \).

Thus, it follows that \( x^* = - \frac{1}{2} u B^{-1} (c + A^T v) \). Substituting this into \( A x^* = 0 \), we obtain the desired form.

d)
Solving for \( \alpha \) gives the solution.

a)
Let \((a_1), (a_2), (a_3)\) be any sequence in \(M\). Then, it holds that \(a_1 a_2 a_3 \to a^1 a^2 a^3 = 1\), and thus \(M\) is closed.
\(M\) is not bounded because \((t, 1/t, 0) \to (\infty, 0, 0)\).

b)
There is no maximum point because of the sequence \(a = (t, 1/t, 0) \in M\) and \(f(a) \to \infty\).
\(M\) is bounded from below because \(x_1, x_2, x_3 > 0\), and we can restrict ourselves to the set \(M = \{ f(x) < f(1, 1, 1) \}\). This set is closed and bounded, hence compact. Since \(f(x)\) is continuous, there exists a minimum point.

c)
The problem is differentiable because \(f(x)\) and \(g(x) = x_1 x_2 x_3 - 1\) are differentiable.

Let’s examine CQ1:

• \(\text{Rank}(h) = n\), which is satisfied since we do not have an \(h\) function.
• \(g(x) + u g'(x) < 0\), which is satisfied for \(x = 0\).

This means we can apply the Lagrange Multiplier Theorem. We first form the Lagrangian function:

The LSG (local solution) is a KKT point, for which the following conditions hold:

Multiply the first equation by \(x_1\), the second by \(x_2\), and the third by \(x_3\), then we obtain \(x_1 x_2 x_3 = 1\).

Thus, \(x^* = -u(1, 1/2, 1/4)\). The constraint \(x_1 x_2 x_3 = 1\) gives us \(u = -2\), and therefore \(f(x^*) = 6\).

The given statement is incorrect. Consider the following counterexample:

Then we have \( f(x) \geq 0 \). Furthermore, from \( h(x) = x - 1 = 0 \), we get \( x = 1 \), but the constraint \( g(x) \leq 0 \) requires \( x \leq 0 \), leading to a contradiction.

Another counterexample is:

Here, \( f(x) \geq 0 \) and has no solution because as \( x \to -\infty \), \( f(x) \to 0 \). This means we can always find a better \( x \), preventing the existence of an optimal solution.

The optimization problem is formulated as:

subject to:

In standard form, we convert the inequalities into equalities by introducing slack variables \( c_1 \) and \( c_2 \):

subject to:

We first convert the problem into standard form by introducing unrestricted-sign variables:

Additionally, we introduce slack variables \( x_3 \) and \( x_4 \). This gives us the following problem:

subject to:

Now, we construct the Simplex tableau:

Since the second-to-last column does not contain a unit vector, we begin Phase 1 of the Simplex algorithm, applied to this specific column.

Phase 1 of the Simplex algorithm is now complete, and we can proceed to Phase 2. However, as we can see, Phase 2 is already finished since all entries in the corresponding row are non-negative.

Thus, our solution is:

This means our final solution is:

with an optimal function value:

First, let’s consider the objective function \( f \) and form its Hessian matrix \( H_f \):

Next, we look at the minors to determine definiteness:

Since all minors are 0, our function is semi-positive definite, and thus convex.

Next, we examine the constraints \( g_1(x) = -3 x_1 + 2 e^{x_2} + 10 \) and \( g_2(x) = -x_2 \). We compute their derivatives:

Now, we check their minors:

Since all minors are 0, the functions are semi-positive definite and thus convex.

Since both the objective function and the constraints are convex, our problem is convex.

The Slater condition is satisfied because we don’t have a constraint of the form \( Ax = b \). Therefore, the first condition is fulfilled. Additionally, for the point \( (x_1, x_2) = (10, 1) \), we have:

Since both inequality constraints are strictly satisfied at \( (10, 1) \), the Slater condition is fulfilled.

First, we set up the Lagrangian function:

Now, we seek \( F(u) \), which involves finding where \( L \) attains its infimum. To do this, we solve for the derivatives:

From (1), we get \( \frac{1}{3} u_1 = x_1 \). From (2), we get:

Now, we substitute our result into the Lagrangian function:

Furthermore, we have the restriction that \( F(u) \) must be greater than \(-\infty\), meaning we need to check for which \( u_i \) this condition is satisfied.

It must be that \( u_2 \geq 0 \), because otherwise, as \( u_2 \to -\infty \), we would also have \( F(u) \to -\infty \). Similarly, \( u_1 = \frac{1}{3} \) must hold. Thus, we obtain:

Thus, the dual problem is:

Since the Slater condition is satisfied, the strong duality theorem holds, and therefore \( \max(F) = \min(f) \).

Now, we examine the derivative of \( F(u) \):

Next, we solve:

Thus, the maximum of \( F \) occurs at the point \( u_1 = \frac{1}{3}, u_2 = \frac{5}{3} \), with \( F(u_2) = 5 \).

The CQ1 condition is satisfied, because we don’t have \( Ax = b \), which satisfies the first condition. Additionally, with \( z = 0 \) and \( h'(x) z = 0 \), the second condition is fulfilled.

Now, we formulate the Lagrangian function:

For the KKT points, we have the following conditions:

From (1), we get:

Next, from (2), by substitution, we get:

Substituting into (3), we get:

In the above equation, we can substitute (4) and (5):

Thus, we find the solution \( x_3 \in \{1, -1\} \). With (5) and then (4), we obtain the KKT points \( (2, -1, 1, -2, 0) \) and \( (0, -1, -1, 2, -4) \).

According to the necessary second-order optimization condition, \( f \) does not have a local minimum at a point if the second derivative at this point is not positive definite.

The Hessian matrix is:

Now, we examine the principal minors to check for definiteness:

Since the second minor is negative, \( H_f \) is not positive definite, and thus the point is not a local minimum.

Let \( E \) be the set of vertices that are the minima, and let \( x_i \) represent these minima.

The convex hull of this set is given by:

Let \( x^* \in \text{conv}(E) \). Then:

Thus, \( x^* \) is a minimum of \( f \).

We first introduce the sign-restricted variables \(x^{+}, x^{-} \geq 0\) and write \(x = x^{+} - x^{-}\). By further introducing the slack variable \(z \in \mathbb{R}^{n_2}\), we find that the system \(Ax \leq b\) is equivalent to the linear system of equations:

Applying Farkas’ Lemma to (5) now states that either (and exclusively) the system (5) or the system

has a solution. The system (6) is, in turn, equivalent to the system

With this the theorem has been shown.

The dual problem to \((P)\) is given by

Farkas’ Lemma states that exactly one of the following statements is always true:

1. \( Ax \leq b, \quad x \geq 0 \)
2. \( A^T y \leq 0, \quad b^T y > 0 \)

To bring the problem into standard form, we introduce sign-restrictive variables \( x_3 = x_3^+ - x_3^- \) with \( x_3^+, x_3^- \geq 0 \).
Additionally, we introduce a slack variable \( x_4 \).

The problem then becomes:

Rewriting in matrix form:

where

with

Projection Theorem

Let \(\emptyset \neq M \subset \mathbb{R}^n\) be a closed and convex set. For any \(x \in \mathbb{R}^n\), there exists a unique \(x^* \in M\) such that

This means that \(x^*\) is the closest point in \(M\) to \(x\), and the second condition ensures that the vector \(x - x^*\) is orthogonal to the set \(M\) in a generalized sense.

The strategy sets for players \( P_1 \) and \( P_2 \) in a two-player matrix game are given as:

and

The expected payoff for the matrix game with payoff matrix \( A \) is given by:

A matrix game with players \( P_1 \) and \( P_2 \) is in Nash equilibrium if and only if the following condition holds:

A matrix game is fair if the expected payoff is 0:

This means that, on average, neither player has an advantage.

On the left is the polar cone and on the right the original set.

Let \( \lambda \in (0,1) \) and \( x_1, x_2 \in M^\circ \) arbitrarily fixed. Then it holds that

Thus, \( M^\circ \) is convex.

Since \( 0 \in C \) and the convex projection is unique, it follows that

Thus, for all \( y \in M \), it holds that \( x^T y \leq 0 \), so \( x \in C^\circ \).

Pivot rule according to Bland:

1. First, find the first column whose first entry is negative, i.e., \( i := \min\{ i : c_i \leq 0 \} \)
2. If all \( a_{ij} < 0 \), then \( \inf(P) = -\infty \)
3. Then, find the row whose quotient with the \( b \)-vector is the smallest, i.e., \( j := \min\{ j : b_j / a_{ij} \} \)
4. Our pivot is then \( a_{ij} \)

First, we bring our problem into standard form by introducing slack variables \( s_1, s_2, s_3 \) for each constraint. We can directly start with Phase 2 of the Simplex algorithm and thus obtain the following tableau:

Thus, we are done and have the optimal solution \( x^* = (0, 4, 2) \) with \( f(x^*) = -20 \).

We first set up the Lagrange function:

We then obtain the following conditions for the KKT points:

Case 1 (u = 0): Substituting into (1), we get:

From (4), we then have \(x_2^2 \leq 1\), i.e., \(x_2 \in [-1, 1]\), and thus we obtain the KKT points \(((0, x_2), 0)\).

Case 2 \(u > 0\): From (2), we obtain \(x_2 = 0\), and from (3) we get \(1 = x_1^2\), so \(x_1 = \pm 1\). Substituting \( \pm 1 \) into (1):

This leads to a contradiction because \(\exp\left(-\frac{1}{2}\right)\) is not negative and cannot equal \(-\infty\). Therefore, there are no KKT points in this case.

We calculate the derivative of \(g\):

We substitute the KKT points we found:

This is linearly independent for all points and thus CQ2 is satisfied.

To check if the second-order necessary condition is satisfied, we need to verify if \(f\) is positive definite.

That is, we first calculate the Hessian matrix of \(f\):

We now look at the minors to check definiteness:

These are positive for the point \(((0, x_2), 0)\) with \(x_2 \in [-1, 1]\).

Let \( x_1, x_2 \in M^* \) be two solutions and let \( \lambda \in (0,1) \). Since \( x_1 \) and \( x_2 \) are both minima, we have \( f(x_1) = f(x_2) \), and thus:

Therefore, \( M^* \) is convex.

Since \( M \) is a polytope, it has a finite number of vertices. Let \( c^* = \arg\max_{c \in V} f(c) \), and suppose \( \sum \lambda_k = 1 \). Then, for every \( x \in M \), we have:

Thus, the global maximum is attained at \( c^* \).

The Slater condition states:

1. \( \operatorname{rank}(A) = n \leq m \).
2. There exists \( x' \in \mathbb{R}^n \) such that \( g(x') \leq 0 \) and \( Ax' = b \).

The dual problem is given by

where

If both (P) and (D) are feasible and the Slater condition holds, then:

1. (P) is solvable \( \iff \) (D) is solvable.
2. Complementary slackness holds: \( u g(x^*) = 0 \).
3. The strong duality property holds:

There is a theorem stating that an optimization problem has a solution if \( f \) is continuous and \( M \) is closed and bounded.

Since \( f \) is convex, it is also continuous. However, boundedness is missing, meaning there must exist a constant \( c \) such that

For example, \( [1,1] \) is bounded, but \( (-\infty, 0] \) is not. Since \( M \) is not necessarily bounded, the theorem does not apply.

Counterexample:

Let \( f(x) = e^x \) and \( M = \mathbb{R} \). Then, there is no solution because we can always find an \( x \) where \( f(x) \) is smaller.

We have the standard form:

with

where \( x_4, x_5, x_6 \) are slack variables.

First, we convert the problem into standard form. To do this, we introduce sign-independent variables, \( x_2 = x_2^+ - x_2^- \), and slack variables \( s_1, s_2 \).

Thus, we get the tableau.

We cannot immediately read off a basic solution because the second-to-last column is not a unit vector, so we start with phase 1 of the simplex algorithm applied to the first row.

Since the first row is positive, we are finished with phase 1 and can move on to phase 2 of the simplex algorithm.

Thus, we are finished with phase 2 of the simplex algorithm, and the solution is \( x^* = (0, 3) \) with \( f(x^*) = 3 \).

We examine the derivatives of \( f(x) \) and \( g(x) = -x_2 + e^{-x_1} + 1 \):

The Hessian matrices are:

We consider the minors of the Hessian matrices:

Since the minors of \( H_f \) and \( H_g \) are positive, both matrices are positive semi-definite, implying that \( f(x) \) and \( g(x) \) are convex.

First, we set up the Lagrange function:

Now, we seek the infimum for \( x \) of this function:

From equation (2), we get \( u = 2x_2 - 2 \implies x_2 = (u - 2)/2 \). From equation (1), we get \( 2e^{2x_1} = ue^{-x_1} \implies 2e^{3x_1} = u \implies x_1 = \ln(u/2)/3 \).

Thus, we have:

Thus, we obtain the dual problem:

We are looking for the point \( u \geq 0 \) where \( F'(u) = 0 \):

With \( F(2) = 2 > 0 = F(0) \) and \( \lim_{u \to \infty} F(u) = -\infty \), the function \( F \) attains its maximum there.

We write \( M \) in the form:

The CQ1/MFB condition is satisfied if there exists a \( z' \in \mathbb{R}^2 \) such that \( h(x) + h'(x)z < 0 \). It holds that \( h'(x) = (3x_1^2, -2(4 - x_1)x_2) \), and thus, we have the condition:

or

For \( x = 0 \), we have \( h(0) = 0 \), so the condition is not satisfied for this point.

Now, let \( x \in M \setminus \{0\} \), then \( x_1 < 4 \), because \( h(x) > 0 \) for \( x \geq 4 \). If \( x_1^2 \neq 0 \), set \( z_1 = -|x_1| \). If \( x_2 \neq 0 \), set \( z_2 = -|x_2| \). Then one of the two terms on the left-hand side of the inequality is strictly smaller than zero, and the other is at least smaller or equal to zero. Therefore, CQ1 is satisfied.

The Lagrange function is:

The KKT conditions are:

Case 1 (\( u = 0 \)): From (1), we get \( x_1 = 6 \) and from (2), \( x_2 = 0 \), so \( x = (6, 0) \), but this point is not in \( M \).

Case 2 (\( x_2 = 0 \)): Here, \( u \neq 0 \), and from (3), we get \( x_1 = 0 \). Substituting into (1) leads to a contradiction.

Case 3 (\( x_2 \neq 0 \)): From (2), we obtain:

Substituting this into (1), we get:

Now, we multiply (4) by the factor \( 4 - x_1 \) and substitute the expression from (3):

This implies \( x_2 = 2 \) or \( x_1 = 6 \). Since we established that \( x_1 < 4 \), we must have \( x_1 = 2 \). Therefore, \( x_2 = \pm 2 \) and \( u = \frac{1}{2} \).

Thus, the KKT points are \( ((2, 2), \frac{1}{2}) \) and \( ((2, -2), \frac{1}{2}) \).

Since \( CQ1/MFB \) holds, we can apply the Lagrange theorem, meaning the KKT points are possible solutions. We have:

Thus, \( x^1 = (2,2) \) and \( x^2 = (2,-2) \) are the solutions to the optimization problem, with an objective function value of 20.

First, we show that the vector \( b \) has at least one negative coordinate. By definition, we have

Since \( b \in \mathbb{R}^n \setminus Q \), there exists an index \( \mu \in \{1, \dots, n\} \) such that \( b_\mu < 0 \).

The second step is to show that the linear system \( A^T x = b \) has no solution \( x \in \mathbb{R}_{\geq 0}^m \). Since all coefficients of \( A \) are non-negative, it follows that \( A^T x \geq 0 \) for all \( x \in \mathbb{R}_{\geq 0}^m \). However, as we just established, \( b \notin \mathbb{R}_{\geq 0}^n \). Thus, the set

is empty.

The claim now follows from Farkas’ Lemma, which states that the set

is non-empty. This is equivalent to the existence of the required vector \( y \).

First, assume that \( b \in \mathbb{R}_{\geq 0}^n \setminus \{0\} \). Since \( b \notin Q \), we have \( b \neq 0 \). In this case, we choose \( a = -b \in \mathbb{R}_{\leq 0}^n \setminus \{0\} \). It follows directly that

and

If this is not the case, then there exists an index \( v \) such that \( b_v > 0 \). Define

Then we obtain

which implies \( b \notin H \). Moreover, for \( x \geq 0 \), we have

which shows that \( x \in H \).

Since the logarithm function is continuous and monotonic, we can consider \( \log(f(x)) \) instead of \( f(x) \). Define \( y_j = \log(x_j) \), so that:

Expanding the logarithms:

Now, we apply \( \log() \) to the constraints:

Thus, we obtain the following linear optimization problem:

Let \( x' \) be an optimal solution to \( (P) \), meaning that for all \( x \), we have \( f(x') \leq f(x) \). This implies that for all \( y \), we get \( g(y') \leq g(y) \), proving the equivalence of the two optimization problems.

The standard form of the problem is:

where:

Here, we use:

• \( y_1 = y_1^+ - y_1^- \),
• \( y_2 = y_2^+ - y_2^- \),

where \( y_1^+, y_1^-, y_2^+, y_2^- \geq 0 \), and
\( y_6, y_7 \geq 0 \) are slack variables for the constraints.

We first transform the problem into standard form:

with the slack variables \( s_1, s_2, s_3 \geq 0 \).

The initial tableau is:

We can proceed directly with Phase 2 of the simplex algorithm:

Thus, Phase 2 is complete, and the optimal solution is:

Let \( g(x) = - x_1 - x_2 + 1 \), and let’s look at the derivatives:

The second derivatives are:

We examine the determinants of the principal minors to determine the definiteness:

As we can see, \( g(x) \) is semi-positive definite, and therefore convex. Furthermore, the first principal minor of \( f(x) \) is also positive, so it remains to check the second principal minor of \( f(x) \):

which is true. Therefore, \( f(x) \) is semi-positive definite and thus convex. Since both \( f(x) \) and \( g(x) \) are convex, the optimization problem is convex.

First, we determine the Lagrangian function:

The objective function is:

This means we need to determine the infimum of the Lagrangian function.

Case 1: \( u \leq 0 \) This leads to a contradiction from equation (1).

Case 2: \( u > 0 \) From equation (1), we obtain:

Substituting this into equation (2) gives:

Substituting \( x_2 = \frac{1}{2} \) into equation (1):

Taking the natural logarithm:

Thus, the point

minimizes the function. Substituting this into \( L(x, u) \) gives:

Thus, the dual problem is:

We examine the critical points of \( F \):

It holds that \( F(e^{3/4}) = e^{3/4} > 0 \), and since \(\lim\limits_{u \to \infty} F(u) = -\infty\), it is, in particular, a global maximum.

The saddle point theorem states that if we have \( x^* \) and \( u^* \) such that

then this is a solution.

In (b), we have already determined \( x^* \) with \( x_2 = \frac{1}{2} \) and \( x_1 = \log(u^*) - \frac{1}{4} = \frac{1}{2} \), and in (c), we found \( u^* = \frac{1}{2} \). Furthermore,

satisfies the inequality chain of the saddle point theorem. Thus, \( x^* \) is a solution to the convex optimization problem.

The problem is given by

with

Since \( f \) is continuous and \( M \) is closed, and since \( (-1, 0) \in M \), the set \( M \) is non-empty. However, \( M \) is not bounded. We can instead restrict ourselves to the set

which is bounded. This restriction is valid because \( f > 1 \) on \( M \setminus M' \) and \( f \leq 1 \) on \( M' \), meaning that the points in \( M' \) are the only possible minimizers.

Since the set \( M' \) is closed and bounded, it is compact. Moreover, since \( f \) is continuous, a solution exists.

We have

We seek all \( (x, y) \) for which there exist \( z_1, z_2 \) such that

That is,

Case 1: \( y \neq 0 \)

Choose \( z_1 = 0 \) and \( z_2 \) such that

Case 2: \( y = 0 \)

Note that

for all \( x \). Thus, MFCQ (Mangasarian-Fromovitz constraint qualification) holds if

Overall, MFCQ is satisfied for all \( (x, y) \in M \).

The KKT conditions are:

From (2), we obtain \( y = 0 \) or \( u = 1 \).

Case 1: \( u = 0 \)
From the first two conditions, we get the point \( (0, 0) \).

Case 2: \( y = 0 \)
From (3), we get \( x = -1 \), and from (1), we get \( u = 1 \).

Case 3: \( u = 1 \)
Substituting into (1) gives:

Applying the quadratic formula:

Substituting into (3), we obtain the KKT points:

We check the KKT points for minimality. First, the point \( (0, 0) \) is not in \( M \). Next,

Thus, the two sought points are \( \left( -\frac{1}{3}, -\frac{2}{3}\sqrt{\frac{5}{3}} \right) \) and \( \left( -\frac{1}{3}, \frac{2}{3}\sqrt{\frac{5}{3}} \right) \).

(i) Let \( z_n \in K_1 - K_2 \) be an arbitrary sequence with \( z_n \to z \) as \( n \to \infty \).
Write \( z_n = x_n - y_n \), where \( x_n \in K_1 \) and \( y_n \in K_2 \).
Since \( K_1 \) is compact and therefore closed, there exists a subsequence \( x_n \to x \in K_1 \).
Furthermore, since \( z_n \) and \( x_n \) converge, it follows that \( y_n \to y \in K_2 \).
Thus, we have

and since \( x \in K_1 \) and \( y \in K_2 \), it follows that \( z \in K_1 - K_2 \). Therefore, \( K_1 - K_2 \) is closed.

(ii) This follows from the separation theorem, which states that if a set is non-empty, closed, and convex, then there exists a hyperplane that strictly separates the sets.
By assumption, the set \( K_1 \cap K_2 = \emptyset \) is non-empty and closed, and \( K_1 \) and \( K_2 \) are convex.
Therefore, a separating hyperplane exists.
I leave the proof of convexity to the reader.

To show that \( f(x^*) \leq f(x) \), we first note that

Rewriting this expression:

Thus, we can express \( f(x) \) as:

Further,

Thus, \( x^* \) is a minimum.

\( (I) \implies (II) \)
Since \( x \neq 0 \), there exists at least one component \( x_i > 0 \). This implies that

Now, define

This ensures that

Thus, \( x' \) is a feasible solution to \( (II) \).

\( (II) \implies (I) \)
If \( x \) is a solution to \( (II) \), then by definition \( x \neq 0 \), since

and \( x \geq 0 \). Therefore, \( x \) also satisfies \( (I) \).

From part (a), we know that (I) is equivalent to (II), so we can consider problem (II) instead.

We formulate the following primal problem:

The corresponding dual problem is given by

We observe that problem (D) is always feasible, since \( y' = 0 \) is in \( N \).

“\(\implies\)”

If problem (II) has a solution, then problem (P) is feasible. By the strong duality theorem, this implies that (D) is also feasible, and we have

Assumption: Suppose there exists a \( y = (y_1, \dots, y_m)^\top \) such that

Then we can choose \( y_{m+1} > 0 \) such that

Thus,

and we obtain

which contradicts the fact that \( \max(D) = 0 \).

“\(\impliedby\)”

If (II) has no solution, then problem (P) is infeasible. By the strong duality theorem, this implies that

Thus, we can choose

such that

Then we have

This implies

Thus, there exists some \( y \in \mathbb{R}^m \) such that

True, because for \( x, y \in M_N = \{ x \in \mathbb{R}^n : Ax = b \} \) and \( \lambda \in [0, 1] \), we have:

and

The function \( f(x, y) \) and the constraint function \( g(x, y) = x^2 + e^y - 3 \) are convex, so this is a convex optimization problem.

Slater’s condition is satisfied since \( g(0,0) < 0 \).

Now, we define the Lagrangian function:

The necessary conditions for the KKT points are:

From (1), we obtain \( x = -\frac{1}{2u} \), and from (2), \( y = \ln(-\frac{1}{u}) \), which implies \( u < 0 \). However, since \( u \) must be \( u \geq 0 \), no KKT points exist, meaning there is no maximum for \(F\) or minimum for \( f \).

Substituting into (3) results in:

Using the quadratic formula:

This gives the two solutions:

For \( u_2 \), we get \( x_2 = 2 \), and with \( y = \ln(-1/2) \), this is not a valid point.

For \( u_1 \), we obtain \( x = -3 \) and \( y = \ln(1/3) \), which is an extremal point of \( f \).

Since \( M \) is bounded above and closed, the set \( M' = \{(x, y) \in M \mid f(x, y) > 0\} \) is compact. Since \( f \) is continuous, there must be a maximum of \( f \) at \( (-3, \ln(1/3)) \).

Warning: There is a miscalculation here—the correct solution should be \( (1, \ln(2)) \), but the general principle is correct.

The dual problem is given by

subject to

We plot the inequalities:

This gives us the solution \( (4,3) \) for the dual problem, with \( F(4,3) = 7 \).

By the strong duality theorem, we have:

Thus,

Furthermore, the equilibrium condition holds:

From this, we obtain \( x_3^* = x_4^* = 0 \). Using these values, we can determine \( x_1^* \) and \( x_2^* \) by solving the system of equations.

The resulting solution is:

“\( \subseteq \)”

By the definition of the polar cone, we have:

Since \( K = \text{cone} \{ x^{(1)}, \dots, x^{(m)} \} \), every element \( x \in K \) can be written as:

Thus, if \( y \in K^P \), then for all such \( x \):

Since \( \lambda_i \geq 0 \), this implies \( y^\top x^{(i)} \leq 0 \) for all \( i \), proving:

“\( \supseteq \)”

Now, assume \( y \in \mathbb{R}^n \) satisfies:

For any \( x \in K \), we write \( x \) as a conic combination:

Applying the given inequality:

Since each \( \lambda_i \geq 0 \) and \( y^\top x^{(i)} \leq 0 \), it follows that:

Thus, \( y \in K^P \), completing the proof.

Remember: Statement of Farkas’ Lemma

Farkas’ Lemma states that for a matrix \( A \), exactly one of the following holds for any \( x \in \mathbb{R}^n \):

1. \( \exists \lambda \in \mathbb{R}^m, \lambda \geq 0 \) such that \( A \lambda = x \), or
2. \( \exists y \in \mathbb{R}^n \) such that \( y^\top x \geq 0 \) and \( A^\top y \leq 0 \).

Let \( x \in K \):

Thus, we conclude that \( (K^P)^P = K \).

The payoff matrix \( A \) is skew-symmetric, meaning:

Since in a two-player zero-sum game, skew-symmetry implies that the expected payoff is always zero for optimal mixed strategies, the game is fair.

We need to show that \( (x^*, y^*) \) is a saddle point for the function:

That is, we must verify:

Since the rows and columns of \( A \) sum to zero, we have:

This means:

Thus, the saddle point equation holds, proving that \( (x^*, y^*) \) is indeed a saddle point.

We show that no pure strategy is optimal for either player.

Suppose Player 1 chooses a pure strategy indexed by \( p \) (\( p \in \{1, \dots, 5\} \)).
Then Player 2 can always find a pure counter-strategy \( q = q(p) \) such that:

The same reasoning holds in reverse: Player 2 choosing a pure strategy allows Player 1 to counter with a pure strategy ensuring a win.

Since both players can always counter any pure strategy of their opponent, no pure strategy is optimal.

Let Max be Player 1 and Mara be Player 2, and let the payoff matrix \( A = (a_{ij}) \) represent the temperature at the intersection of the \(i\)-th trail and the \(j\)-th stream.

Max wants to minimize the maximum temperature across all streams, so the objective is:

Mara, on the other hand, wants to maximize the minimum temperature across all trails, so the objective is:

One could calculate the mean or median of the temperatures (from the matrix) as a fair outcome for the matrix game:

Where \( \bar{a} \) represents the average temperature, and the sum \( \sum a_j \) is taken over all elements in the matrix \( A \).

Saddle-Point Game: A game with payoff matrix \( A \) is called a saddle-point game if the smallest maximum column entry and the largest minimum row entry coincide. For every saddle-point game, there are optimal pure strategies \( x^* = e_j \) and \( y^* = e_i \) (see Theorem 4.12).

Verification of the criterion:

This shows that it is indeed a saddle-point game.

By Theorem 4.12, Player 1 should choose the column \( j_0 \) where the maximum is minimized, and similarly for Player 2:

Thus, the optimal strategies are \( x^* = e_3 \) and \( y^* = e_4 \). Therefore, Mara and Max should camp at the ford “Hirschung/Moskitobach.”

We consider the problem:

Maximize \( r \) subject to \( B_r(z) \subset M = \{x : Ax \leq b\} \).

We now rewrite the constraints as follows:

Since \( a_k^\top y \leq |a_k| |y| \) and equality holds for \( y = a_k \frac{|y|}{|a_k|} \), we obtain:

We use the result from Task 46. To calculate the triangle as a polyhedron, we have:

with

The minimization problem is:

Now we can apply Phase 2 directly:

We choose the pivot \( a_{13} = 1 \).

Now we can continue the Simplex algorithm.

The result is: