Kendala yang melibatkan

16

Seharusnya

\begin{aligned} min A & v e c (U) \\ subject to U_{i, j} \leq maks {U_{saya, k}, U_{k, j}}, saya, j, k = 1, ..., n \end{aligned}

$\begin{align*} \min A &\mathrm{vec}(U) \\ &\text{subject to } U_{i,j} \leq \max\{U_{i,k}, U_{k,j}\}, \quad i,j,k = 1, \ldots, n \end{align*}$

di mana $U$ adalah simetris $n\times n$ matriks, dan $\mathrm{vec}(U)$ membentuk ulang $U$ menjadi vektor satu dimensi dengan $n^2$ entri.

Bagian dari program di atas yang memberi saya masalah adalah . (Membatasi solusi untuk matriks simetrik nonnegatif tampaknya mudah.) $\max\{⋅,⋅\}$

Terima kasih sebelumnya atas bantuan atau referensi!

optimization linear-programming N21
sumber

any reason why you can't add both constraints?

Aron Ahmadia

1

@AronAhmadia: He can't add both constraints because that would be equivalent to

U_{i, j} \leq min {U_{i, k}, U_{k, j}}

$U_{i,j} \leq \min\{U_{i,k}, U_{k,j}\}$ for all

i, j, k

$i, j, k$ . I don't think there is an LP reformulation of this problem, but there could be an MILP reformulation, even though that likely makes it more expensive to solve.

Geoff Oxberry

@ N21: Seberapa besar yang Anda harapkan

menjadi untuk masalah yang ingin Anda selesaikan?

n

$n$

Geoff Oxberry

@ Geoff: Terima kasih! Saya akhirnya berharap untuk memiliki

besar , tetapi saat ini saya paling khawatir untuk mendapatkan solusi awal dengan

kurang dari, katakanlah 100, atau bahkan 10.

n

$n$

n

$n$

N21

Terima kasih telah mengklarifikasi @GeoffOxberry, saya tidak sepenuhnya memikirkannya sebelum memposting.

Aron Ahmadia

14

Sunting: Mari kita coba penjelasan ini lagi, kali ini ketika saya lebih terjaga.

Ada tiga masalah besar dengan formulasi (dalam urutan keparahan):

Tidak ada reformulasi masalah yang jelas, halus, cembung, atau linier.
Ini bukan omong kosong.
Itu tidak harus cembung.

Tidak ada reformulasi yang mulus / cembung / linier

Pertama, tidak ada standar, reformulasi yang jelas dari setiap batasan . Saran Aron berlaku untuk batasan lebih umum , di mana batasan seperti digantikan oleh dua ketidaksetaraan setara berikut: $\max$ $\min$

U_{i j} \leq min_{k} {U_{i k}, U_{k j}}

$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$

U_{i j} \leq U_{i k}, \forall k

$U_{ij} \leq U_{ik}, \quad \forall k$

Formulasi ulang tidak ideal, setiapbatasan

telah diganti dengan

U_{i j} \leq U_{k j}, \forall k .

$U_{ij} \leq U_{kj}, \quad \forall k.$

min

$\min$

2 n

$2n$ batasan linier, tetapi ia mengubah program non-linear non-linear menjadi program linier, yang merupakan urutan besarnya lebih cepat untuk dipecahkan.

Wolfgang menunjukkan bahwa dimungkinkan (dia tidak menyertakan bukti) untuk merumuskan kembali batasan sehingga linear dan halus dengan menambahkan variabel kendur. Variabel slack perlu ditambahkan untuk setiap batasan dalam formulasi asli, yang berarti bahwa kami menambahkan kendala dalam reformulasi ini. Selain itu, setiap batasan diganti dengan (atau lebih) kendala linier. Pembunuh yang sebenarnya adalah bahwa ketidak-munduran dipindahkan dari batasan ke tujuan, sehingga formulasi Wolfgang masih menghasilkan program non-linear yang tidak. $\max$ $\max$ $n^2$ $\max$ $2n$

Tidak ada reformulasi standar batasan dalam masalah minimisasi yang saya ketahui, setelah memeriksa buku teks pemrograman linier saya dan telah melakukan pencarian literatur. Itu tidak berarti bahwa reformulasi semacam itu tidak ada; itu hanya berarti saya belum menemukan itu. Jika saya harus menebak, saya akan mengatakan formulasi LP tidak ada. $\max$

Ketidaknyamanan

Dalam konteks ini, nonsmoothness berarti bahwa setidaknya salah satu fungsi dalam perumusan (tujuan atau kendala) tidak dua kali terus menerus dapat dibedakan. Fungsi nonsmooth dalam formulasi ini adalah fungsi . $\max$

Nonsmoothness adalah masalah besar karena:

itu segera membuat masalah Anda menjadi nonlinier
kebanyakan pemecah pemrograman nonlinear mengasumsikan dua kali fungsi yang dapat dibedakan secara kontinu

Karena fungsi-fungsi bahkan tidak pernah dapat dibedakan secara terus-menerus, Anda bahkan tidak dapat menggunakan metode gradient descent tradisional tanpa kesulitan. Algoritma pemrograman nonlinier non-linear lebih lambat dari pada yang halus. $\max$

Kemungkinan ketidaksesuaian

Masalah Anda bisa nonconvex, karena dalam "bentuk standar" untuk program nonlinier (yaitu, menyatakan semua kendala dalam bentuk ), kendala yang merepotkan dalam formulasi Anda adalah $\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$

U_{i j} - max_{k} {U_{i k}, U_{k j}} \leq 0, \forall i, j, k .

$U_{ij} - \max_{k}\{U_{ik}, U_{kj}\} \leq 0, \quad \forall i,j,k.$

Fungsi-fungsi ini cekung.

Bukti: Dalam hal ini, fungsinya dan keduanya cembung. Jumlah fungsi cembung adalah cembung, dan mengalikan fungsi cembung dengan -1 menghasilkan fungsi cekung. (QED.) $-U_{ij}$ $\max_{k}\{U_{ik}, U_{kj}\}$

Seperti yang ditunjukkan Tim, hanya karena nonconvex tidak berarti bahwa masalah Anda sebenarnya nonconvex, tetapi jika Anda mencoba menyelesaikan masalah optimisasi menjadi optimal global, Anda hanya dapat menjamin bahwa solver optimasi cembung akan mengembalikan global optimal jika masalah Anda cembung. Jika Anda benar-benar menginginkan global optimal, Anda harus menentukan apakah set yang layak adalah cembung (atau tidak). Dengan tidak adanya informasi seperti itu, Anda harus mengasumsikan bahwa masalah Anda mungkin nonconvex, dan menggunakan algoritma yang tidak bergantung pada informasi konveksitas. Meskipun demikian, ketidak-beresan dan kurangnya reformulasi yang baik adalah masalah yang jauh lebih besar. $\mathbf{g}$

Opsi untuk memecahkan masalah

Setuju untuk menemukan solusi yang layak. Dalam hal ini, lakukan apa yang dikatakan Aron, dan ganti dengan
$U_{i j} \leq max_{k} {U_{i k}, U_{k j}}, \forall i, j, k$ $U_{ij} \leq \max_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k$ yang kemudian dapat dinyatakan kembali sebagai dua ketidaksetaraan yang terpisah menggunakan reformulasi LP standar. Masalah yang dihasilkan akan menjadi pembatasan LP dari masalah yang ingin Anda pecahkan; itu harus menyelesaikan dengan cepat relatif terhadap masalah asli Anda, dan jika ia memiliki solusi, solusi itu akan layak untuk masalah asli Anda, dan nilai fungsi objektifnya akan menjadi batas bawah pada nilai fungsi objektif optimal dari masalah asli Anda. $U_{i j} \leq min_{k} {U_{i k}, U_{k j}}, \forall i, j, k,$ $U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\} , \quad \forall i,j,k,$
Coba keberuntungan Anda pada formulasi Anda seperti halnya dengan bundle solver untuk program nonsmooth. Saya tidak punya banyak pengalaman dengan jenis pemecah ini. (Seorang kolega saya menggunakannya dalam penelitiannya.) Mereka mungkin lambat, karena mereka tidak dapat menggunakan informasi turunan. (Saya pikir mereka menggunakan subgradien atau informasi gradien umum Clarke sebagai gantinya.) Ini juga tidak mungkin bahwa Anda akan dapat memecahkan contoh masalah besar dengan pemecah bundel.

Geoff Oxberry
sumber

1

Geoff, barang bagus; ini menyentuh poin utama dan menawarkan banyak wawasan dan saran yang membangun. Saya memilihnya. Tetapi Anda tampaknya memperlakukan nonconvexity sebagai sesuatu yang terpisah dari kenyataan bahwa, seperti yang Anda katakan, "tidak ada rumusan standar batasan max dalam masalah minimisasi yang saya ketahui". Tetapi pada kenyataannya, yang pertama justru mengapa yang terakhir tidak mungkin. Batasan non-cembung tidak dapat diekspresikan dalam pemrograman linier --- berhenti penuh! Ini adalah masalah non-cembung, dan harus diformulasikan ulang sebagai masalah bilangan bulat-bilangan bulat atau beberapa heuristik lain yang diterapkan.

Michael Grant

@MichaelGrant: Saya membuat argumen itu dalam revisi 1 dan 2 lebih dari setahun yang lalu, dan kemudian masuk ke dalam komentar panjang tentang pernyataan saya bahwa masalahnya adalah nonconvex. (Lihat jawaban Tim di bawah ini.) Seingat saya, pada saat itu, Tim berpendapat bahwa ketidaksetaraan

dengan

cekung tidak membuat set yang layak menjadi nonconvex. Saya tidak yakin mengapa, karena menurut definisi, program cembung harus dapat dinyatakan sedemikian sehingga

untuk

cembung. Aku bosan berdebat dengan Tim tentang hal itu; Saya harus mengembalikan beberapa hasil edit saya sebelumnya.

g (x) \leq 0

$\mathbf{g}(x) \leq \mathbf{0}$

g

$\mathbf{g}$

g (x) \leq 0

$\mathbf{g}(\mathbf{x}) \leq \mathbf{0}$

g

$\mathbf{g}$

Geoff Oxberry

1

Memang benar bahwa fungsi kendala non-cembung dapat menggambarkan set cembung (memang gagasan quasiconvexity mencakup sebagian besar kasus ini). Tetapi kenyataannya adalah bahwa

menggambarkan suatu set non-cembung di

. Jadi klaim Tim tidak relevan dengan masalah khusus ini. Dapat dibayangkan bahwa perpotongan dari set non-cembung pada akhirnya menjadi cembung, tetapi itu tidak mungkin terjadi.

x \leq max {y, z}

$x \le \max\{y,z\}$

(x, y, z)

$(x,y,z)$

Michael Grant

1

max {y, z}

$\max\{y,z\}$

3

$-\infty$ .

Let

U = (\begin{matrix} 1 & \dots & 1 \\ ⋮ & ⋮ \\ 1 & \dots & 1 \end{matrix}) .

$U=\left(\begin{matrix} 1&\cdots &1\\ \vdots & & \vdots\\1&\cdots&1\end{matrix}\right).$ Since

A \cdot vec (U)

$A\cdot\mbox{vec}(U)$ and your constraints are linear in

U

$U$ , any positive multiple

t

$t$ of

\pm U

$\pm U$ satisfies the constraints. Therefore,

min_{V} (A \cdot vec (V)) \leq m i n_{t} (A \cdot vec (t U)) = - \infty

$\min_V(A\cdot\mbox{vec}(V)) \le min_{t}(A\cdot \mbox{vec}(tU))=-\infty$ .

Deathbreath
sumber

Definitely a solution to the question as posed. My guess is that the OP is going to pose some nonnegativity constraint on

U

$U$ , in which case, the optimal objective function value may not be

- \infty

$-\infty$ .

Geoff Oxberry

@GeoffOxberry: True. Even with positivity constraints on

U

$U$ the answer is

\leq 0

$\le 0$ . The form as posed implies that it's really a matrix optimization question a la

2 tr ({\hat{A}}^{*} U) = ‖ \hat{A} - U ‖^{2} - ‖ \hat{A} ‖^{2} - ‖ U ‖^{2}

$2\mbox{tr}(\hat{A}^\ast U)=\|\hat{A}-U\|^2-\|\hat{A}\|^2-\|U\|^2$ .

Deathbreath

2

In order to formulate the constraints $f \le \max \{ f_1, f_2,...,f_n \}$ , we create $n$ binary variables, $b_i \in \{0,1\}$ , $1 \le i \le n$ . Let $M$ be the bound of variable $f$ , then we only need to add the following constraints:

1) $f \le f_i + (1-b_i) M, \forall i$

2) $\sum_i b_i = 1$

Normally, set $M := max_i f_i - min_i f_i$ if we can estimate the value of $f_i$ .

Kevin
sumber

1

Can't you introduce a slack variable? So to reformulate the constraint

x_{i} <= max (a_{i 1}, a_{i 2}, . . ., a_{i n})

$x_i <= \max(a_{i1}, a_{i2}, ..., a_{in})$ write it as follows:

x_{i} <= s_{i}

$x_i <= s_i$

s_{i} >= a_{i 1}

$s_i >= a_{i1}$

s_{i} >= a_{i 2}

$s_i >= a_{i2}$

. . .

$...$

s_{i} >= a_{i n}

$s_i >= a_{in}$ This will have an infeasible solution with respect to the original problem if you choose s=infinity. But I'm pretty sure you can show that if you add a term

c * max (s_{i} - max (a_{i}), 0)

$c*\max(s_i-\max(a_i), 0)$ to the objective function (i.e., you want to have

s_{i} - max (a_{i})

$s_i-\max(a_i)$ as small as possible, preferably zero) and

c

$c$ sufficiently large, then you'll get back a feasible solution if the original problem had feasible solutions with objective value less than infinity.

(A proof would go along the lines of showing that if $s_i>=\max(a_i)$ and if $x_i=s_i$ , then the solution is infeasible; in other words, $s_i-\max(a_i)$ is a measure of infeasibility wrt to the original problem. If the problem is stable, there should be a finite improvement in objective function value for a finite violation of feasibility. If you choose c to be larger than the ratio between change in objective value and violation of feasibility, then the modified objective function would grow for problems that go into the infeasible region.)

Wolfgang Bangerth
sumber

It's a good idea. Assuming your proof goes through, the issue then becomes moving the nonlinearity and nonsmoothness from the constraints into the objective, both of which are still undesirable qualities in a formulation.

Geoff Oxberry

I'm afraid this will not work. If the

a_{i j}

$a_{ij}$ quantities are variables, not constants, then your original constraint is not a convex set in

(x_{i}, a_{i 1}, a_{i 2}, . . ., a_{i n})

$(x_i,a_{i1},a_{i2},...,a_{in})$ . Your reformulated set of constraints, on the other hand, is a convex set in

(x_{i}, s_{i}, a_{i 1}, a_{i 2}, . . ., a_{i n})

$(x_i,s_i,a_{i1},a_{i2},...,a_{in})$ . The two sets of constraints cannot be equivalent.

Michael Grant

1

I can't find the comment button...

As Geoff pointed out, it is a concave constraint function. However, it doesn't matter if the function itself is concave or not. Concave functions under linear constraints can be convex sets ( e.g. $log(x)<5$ ).

If it is a convex set, you could perform gradient descent on your objective function, using something like Dykstra's_projection_algorithm to project back onto the space of constraints.

Tim
sumber

Upvoted for the comment about concave functions; I should've thought more about my explanation. Projecting onto the feasible set is a possibility, though I'm not sure off the top of my head if you could apply those algorithms with nonsmooth constraints.

Geoff Oxberry

I'm not sure if they apply to non-smooth constraints. Also note, non-convex problems are only NP-hard if they have an NP number of possible solutions. If the number of possible solutions is in P, brute force exactly solves a non-convex optimization task. Lastly, the method cannot be formed as an LP, but this has nothing to do with the concave nature of the constraint. It's because the constraint is a non-linear function that also yeilds a non-linear (convex or not) constraint space. There are many convex constraints that also can't be solved using LPs. e.g.

x^{2} + y^{2} < 5

$x^2+y^2<5$

Tim

"Nonconvex problems are only NP-hard if they have an NP number of possible solutions." NP stands for "nondeterministic polynomial". I'm completely lost about what you're talking about. Secondly, I mentioned concavity because linear functions are concave and convex; the function isn't convex. Just because the function is nonsmooth and piecewise linear does not immediately exclude the possibility that an LP reformulation exists.

Geoff Oxberry

For instance,

U_{i j} \leq min_{k} {U_{i k}, U_{k j}}

$U_{ij} \leq \min_{k}\{U_{ik}, U_{kj}\}$ is "nonlinear" and can be reformulated as a pair of linear constraints, and thus, admits an LP reformulation. Finally, you're right, there are many constraints that can't be reformulated as linear constraints, such as smooth nonlinear constraints.

Geoff Oxberry

Sorry, had to short-hand the comment, so I used NP for non-polynomial, and P for polynonomial. The point was that non-convex optimization isn't always NP-hard. It's only NP-hard if the number of possible solutions is WORSE than polynomnial. Sorry for the confusion :) You're right about the reformulating as linear. You seemed to say "Consequently, there is no way to reformulate your program as a linear program," because of the non-convexity, I was just noting that its not related to convexity but linearity.

Tim

0

Are there more inequality constraints not being mentioned? As stated, the problem is to minimize a linear function over a cone, so the optimal value is always either $-\infty$ or $0$ .

Even with the constraint $U \ge 0$ , the problem reduces to a discrete decision problem. Think of the linear function $A$ as corresponding to positive/negative weights of the edges of the complete graph on $n$ vertices. If there is a graph of diameter 2 connecting all the vertices with the sum of its weights strictly negative, then the optimal value is $-\infty$ , otherwise the optimal value is $0$ .

A quick sketch on how to prove this. First note that if $a \le b \le c$ , then $c \le \max(a,b)$ implies $b=c$ . So then the inequalities imply that for every triple $i,j,k$ , exactly one of the following must be true:

$U_{ij} < U_{jk} = U_{ik}$
$U_{ik} < U_{jk} = U_{ij}$
$U_{jk} < U_{ik} = U_{ij}$
$U_{ij} = U_{jk} = U_{ik}$

So if you fix some threshold $t$ and form a graph $G(t)$ with an edge wherever $U_{ij}=t$ , then every 3 vertices must have exactly 0,2, or 3 edges connecting them. So if $U_{ij}=U_{j k}=t$ , then for every other vertex $\ell$ , we must have either $U_{j \ell}=t$ or $U_{i\ell}=U_{k\ell}=t$ . So if the graph $G(t)$ has any edges, it must be of diameter 2.

p.s.
sumber

Kendala yang melibatkan

Jawaban:

Tidak ada reformulasi yang mulus / cembung / linier

Ketidaknyamanan

Kemungkinan ketidaksesuaian

Opsi untuk memecahkan masalah