京都大学 情報学研究科 数理工学専攻 2023年8月実施 凸最適化

Author

Casablanca

Description

日本語版

English Version

Let , where the superscript denotes transposition. Consider the following linear programming problem P:

where the decision variable of problem P is the vector .

Answer the following questions (i) and (ii)

(i) write out a dual problem of problem P.

(ii) Show that problem P has an optimal solution.

Let be the set of optimal solutions of problem P.

Answer the following quetions (iii) and (iv).

(iii) Show that is a convex set.

(iv) Suppose that and . Consider the following optimization problem Q:

where the decision variable of problem Q is the vector . Obtain an optimal solution of problem Q by using Karush-Kuhn-Tucker conditions.

Kai

(i)

We have Lagrangian: .

Obtain Lagrange dual function: .

Then we write the dual problem D:

(ii)

Since , the optimal value of dual problem D satisfies: then the linear programming is bounded, thus has an optimal solution.

(iii)

For any , we know that for any which satisfies the constraints of P,

for ,

c^\top (\theta y_1 + (1-\theta)y_2) = \theta c^\top y_1 + (1-\theta)c^\top y_2 \leq c^\top \widetilde{y}

\begin{aligned} Q:&\text{Minimize} &\frac{1}{2} x^\top x - c^\top x \ &\text{subject to} &x \succeq \mathbf{0}, \mathbf{1}^\top x = 1 \ \end{aligned}

\text{KKT-conditions: } \left{ \begin{aligned} x - c - \lambda - \mu \mathbf{1} &= 0 \ \lambda \succeq 0, -\lambda^\top x &=0 \ x &\succeq 0\ \mathbf{1}^\top x &= 1 \end{aligned} \right.

x^* = [\frac{1}{n} , \frac{1}{n}, \ldots , \frac{1}{n}]^\top , \lambda = \mathbf{0}, \mu = [\frac{1}{n} - c_1, \frac{1}{n} - c_1, \ldots, \frac{1}{n} - c_1]^\top