Laminar Quadratic M-Convex Minimization

A laminar family means a nonempty family of subsets of {1, ... , n} such that

For a laminar family and a family of univariate discrete convex functions indexed by , the function defined by

is an M-convex function [1,2], where

Here we consider a quadratic laminar M-convex function:

for a laminar. In this web application, the laminar family is preset for each dimension. For example, = {{1},{2},{3}, {1,2}, {1,2,3}} in the 3-dimensional case.

You can choose the dimension n from 1 to 9.

dimension n = 1 2 3 4 5 6 7 8 9

You can also input parameters a_Y and b_Y in the ranges 0 < a_Y<100 and -100< b_Y< 100.

{1}	{2}	{3}
x({1})2+x({1})	x({2})2+x({2})	x({3})2+x({3})
x({1,2})2+x({1,2})
x({1,2,3})2+x({1,2,3})

You can also input an initial solution x:

	1	2	3
x

(Note: "Reset" button resets your inputs to default values.
An inappropriate input value will be replaced with a random number.)

---

This web application minimizes f(x) using ODICON.

[1] K. Murota (2001): "Discrete Convex Analysis---An Introduction (in Japanese)," Kyoritsu Publishing Company, Tokyo. Section 4.3.

[2] K. Murota (2003): "Discrete Convex Analysis," SIAM. Section 6.3.

---

Satoko Moriguchi, Nobuyuki Tsuchimura