DCP HOME

Laminar Quartic M-Convex Minimization

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

For a laminar family calT and a family of univariate discrete convex functions f_Y indexed by YinT, the function defined by def-laminar-conv

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

Here we consider a quartic laminar M-convex function:

objfunc-separable-quarticM

for a laminarcalT. In this web application, the laminar family is preset for each dimension. For example, calT = {{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 =

You can also input parameters aY and bY in the ranges 0 < aY<50 and -10< bY< 10.

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

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