Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
1answer
44 views

Integer optimization problem

Suppose we are given $Av - x \ge 0$, for a given $n \times n$ matrix A and an $n\times 1$ vector $x$. Find an integer valued vector $v$ of size $n \times 1$ such that $\mathbf{1} \cdot v$ is minimized ...
3
votes
2answers
493 views

Optimisation problem choose x to minimize y

I have stumbled upon a sample maths question during my revision, and I have no idea how to solve it. Can anyone help or guide me along? Given a piece of rectangular paper of 11 cm by 8.5 cm. The ...
1
vote
1answer
74 views

Efficient MIP reformulation for binary integer problem

Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$ I want to reformulate this into an efficient mixed-integer programming (MIP) problem. ...
0
votes
0answers
271 views

Using maximum flow algorithm to check existence of a matrix

Using the maximum flow algorithm, I have to determine if there exists a $3\times 3$ matrix $P$ (such that all elements are $\geq 0$). I'm given: The maximum values of the row sums The column sums ...
1
vote
1answer
210 views

Sion's minimax theorem

Sion's minimax theorem is stated as: Let $X$ be a compact convex subset of a linear topological space and $Y$ a convex subset of a linear topological space. Let $f$ be a real-valued function on ...
2
votes
2answers
223 views

maximize log determinant subject to a linear constraint

Does anyone know any efficient method to solve the following problem? $ (\alpha,\beta) = \text{argmax} \log \det (\alpha K_1 + \beta K_2)$ s.t. $c_1 \alpha + c_2 \beta = c_3, \alpha\geq0, \beta\geq ...
2
votes
0answers
69 views

the dual of the dual is the primal?

Consider a convex optimization problem (call it $P$). Consider its dual (call it $D$). Is it true that the dual of $D$ is $P$? For linear programming, it is true. I'd just like to know under which ...
1
vote
1answer
352 views

Prove the A-G-M Inequality using Lagrange multipliers.

I’m trying to prove the Arithmetic-Geometric-Mean Inequality (A-G-M) using Lagrange multipliers. For positive real numbers $ x_{1},x_{2},\ldots,x_{n} $, we want to show that $$ (x_{1} x_{2} \cdots ...
0
votes
1answer
221 views

Necessary and enough condition for minimum of function

Let $F(x)=〈Ax,x〉+〈2b,x〉+c, x\in\mathbb R^n$, A is real, symmetric, regular and positive definite matrix, $a,b\in\mathbb R^n$, $c\in\mathbb R$ are fixed. What is necessary condition for local minimum ...
1
vote
0answers
65 views

Statistical significance test in polygaussian fitting, using Levenberg-Marquardt

I have a set of dihedral angle values that I have fitted using a polygaussian function via the Levenberg-Marquardt algorithm http://en.wikipedia.org/wiki/Levenberg-Marquardt. Specifically, the ...
0
votes
0answers
250 views

Gradient Descent with nonlinear constraint on Symmetric positive definite matrix space

I would like to find the stationary point $S_*$ (global minimum) that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex in Convexity of ...
2
votes
1answer
234 views

Optimization problem: find the optimal interval for a variable

I have 4 random variables. 3 of them are controllable variables and 1 is a measure of performance. On the side, I have some "best practices" that suggest some intervals for the 3 controllable ...
2
votes
2answers
59 views

What are the relations between these two minimizations

What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$ and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$ ?
1
vote
1answer
36 views

Convex sets and algebraic operations

If $A$ is convex set and $\alpha,\beta>0$, show that $(\alpha+\beta)Α=\alpha Α+\beta Α$. I tried to show that, but I am not sure if it was so simple. This is how I did it: $$(\alpha+\beta)Α := ...
4
votes
1answer
2k views

Maximum Modulus Exercise

Using the maximum modulus theorem in complex analysis, what is a good technique for finding the maximum of $|f(z)|$ on $|z|\le 1$, when $f(z)=z^2-3z+2$? Got some really nice answers below, so I ...
8
votes
6answers
858 views

Optimization problem (in linear algebra course!)

Let $a_1, a_2, \ldots, a_n$ be real numbers such that $a_1 + \cdots + a_n = 0$ and $a_1^2 + \cdots +a_n^2 = 1$. What is the maximum value of $a_1a_2 + a_2a_3 + \cdots + a_{n - 1}a_n + a_na_1$? I'd ...
1
vote
2answers
299 views

Maximize the product of linear functions

Suppose $f(x,y) = \prod_{i=1}^n (a_ix+b_iy)$ where $n$ is a constant larger than 500, and $a_i>0$, $b_i>0$ are known coefficient. There is only one global maximum. What's the most efficient ...
0
votes
1answer
102 views

Duality in linear programming

I saw the some theorem. If primal problem is unbounded then no feasible solutions for dual. If dual problem is unbounded then no feasible solutions for primal. Please help me to understand above ...
1
vote
0answers
44 views

Confusion related to complexity of least squares problem

I have this confusion about the time complexity of least squares problem. Suppose minimize $||Ax-b||^2$ Analytical solution = $x^* = (A^TA)^{-1}A^Tb$ computational time proportional to $n^2k$, $A ...
1
vote
1answer
124 views

Linear programming problem

Some additional information: In the next season the harvesting amount is estimated at 900 for farm A, 1200, 1500, 1800 for farm B,C and D respectively. In this scenario I'm asked to minimize the ...
1
vote
2answers
165 views

An optimization problem with regard to permutation function

So far I only meet optimization problems solved by searching for an optimal point in $\mathbb{R}^n$. But today I met with an optimization problem that asks me to search within a set of functions. My ...
8
votes
1answer
326 views

Minimizing Lagrangian with two functions

I read this problem where I have to minimize a functional $E[L]$ using calculus of variations, but I'm not sure what is the procedure to follow. The functional is the expected loss: $$E[L] = ...
0
votes
1answer
75 views

Cutting plane in IP system

I am doing branch-and-bound for 5 decision binary variables. so Decision would be 0 and 1. and I found sub-problem node Q with optimal value 5.4 (0.3, 0.2, 1, 0.5, 0.1) my IP constraints are ...
1
vote
0answers
59 views

Optimizing over norms of set of equations.

I have a set of N real-valued finite-dimensional vectors $\mathbf{v}_i$ and target norms $y_i$ and I am trying to find a linear transformation matrix $L$ such that the norm of the transformed vectors ...
1
vote
1answer
40 views

Approximation in $L^2$

Let $G$ be a domain assumed smooth enough. I want to show that the mean value $m$ is minimizing $ m \rightarrow \| f-m\|_{ L^2(G)} $ for $ f \in L^2(G)$. Is it unique? Is it allowed to derive under ...
1
vote
0answers
32 views

What's the most optimal container consisting of two spacial figures?

I asked myself this question as I was answering an optimization question where I had to figure out what three dimensional shape had the best volume-surface area ratio. Which I find to be a sqhere. It ...
4
votes
2answers
761 views

Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ...
10
votes
4answers
2k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
2
votes
1answer
323 views

Minimization of definite integral reduces to the minimization of a part of the integrand, why?

This post was edited following a comment that rightly stated that the original question was unsensible. The edited version follows. Why does the equation in the second line implicitly define the ...
2
votes
1answer
368 views

Preconditioning for an LBFGS

I am working on a high dimensional (N ~ 1000-60000) optimization problem which is currently solved with an LBFGS algorithm. I have experimented with different diagonal preconditioners as I know that ...
1
vote
1answer
58 views

minima of $\frac{(1-k)x\log(x^2-x)}{(1-k')(x-1)\log x^2}$

Can anyone help me in finding minima of $\frac{(1-k)x\log(x^2-x)}{(1-k')(x-1)\log x^2}$ where $k$ and $k'$, are constants. I found the differential but it was too big to be equated. ...
5
votes
1answer
105 views

Optimum product disassembly / assembly path

I have a store Σ, which contains products (denoted by latin mayuscules) and components (denoted by greek minuscules). A product consists of a set of components (but not more than one of each distinct ...
1
vote
1answer
74 views

Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex?

Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$ However I don't know if it is possible to find ...
2
votes
2answers
469 views

Linear optimization problem: Minimizing a linear function over an affine set.

The problem is as follows: Give an explicit solution of the linear optimization problem below. $$ \text{minimize}\ c^Tx \\ \text{subject to}\ Ax\ =\ b $$ No other information is given. My ...
1
vote
1answer
61 views

Find a decoupled explicit formula for a minimizer

Consider the energy $F(u,v) = \int^1_0((\frac{1}{4}(u')^2+(v')^2 +\frac{1}{2}(u-v+1)^2)dx$ for $C^1$ functions u and v on the interval (0,1) that satisfy the boundary conditions ...
3
votes
2answers
189 views

To minimise max bin sizes in two-level balls-and-bin problem

Basically we consider two levels of mapping (the first is called partition and second mapping strategy) of balls into bins. And try to find the best partition strategy (the first level of mapping) to ...
3
votes
2answers
107 views

Find the values of $x$, $y$ and $z$ minimizing $\frac{r^2x}{y+z}+\frac{s^2y}{x+z}+\frac{t^2z}{x+y}$

$$\frac{r^2x}{y+z}+\frac{s^2y}{x+z}+\frac{t^2z}{x+y}$$ $r$, $s$, $t$ are positive coefficients. Find the values of non-negative variables $x$, $y$ and $z$ so that the above expression is a minimum.
4
votes
2answers
96 views

Minimizing a functional

I am trying to follow this paper. In it they define a functional $$J(f) = \sum_{x \in \Omega} \psi (f(x) - u(x)) + \beta \sum_{x \in N_x} \phi(f(x) - f(y)), $$ where, for my purposes, $f$ and $u$ ...
4
votes
2answers
171 views

Finding an explicit expression for a minimizer

Suppose $f$ is a continuous function on the interval (0,1). We consider the energy functional $F(u) = \int^1_0\frac{1}{2}((u')^2+u^2)\,dx - \int^1_0fu\,dx$ which is well defined for continuously ...
1
vote
1answer
114 views

Modellering a Integer Linear Program

Warning; !! Long post !! Note; This is not a homework assignment, but rather an old exam question I'm trying to figure out. If you read on, you'll notice that I've put quite some work in on it ...
1
vote
1answer
155 views

Goofy problem: Optimal bet with nearly no knowledge

A year or so back, on the verge of falling asleep, I thought up this question: You have come to me ready to gamble. I have two envelopes on the table, one containing the amount of my bet, and one ...
1
vote
1answer
118 views

How to cast the “Numberdrum” problem mathematically

I came across the numberdrum problem in the Evening Standard, where the objective is to obtain a number in the centre using each of the numbers in the outer ring exactly once, along with the four ...
3
votes
2answers
1k views

Grad degree that mainly deals with probability/game theory/optimization?

I'm currently working but am going to take classes as a non-degree student to beef up the math part of my background. I've only taken calc 1-3, ODEs, linear algebra, logic, and decision theory so my ...
1
vote
2answers
276 views

Simple optimization problem - Box [closed]

"You're asked to design a box of volume 1m^3 with height 1/2m. What dimensions (length and width) will use the least material?
1
vote
1answer
315 views

Derivative inside an integral

Assume that I have an integral $$ I=\int_\Omega f(\omega)g(\omega)d\omega, $$ where $\Omega$ is a measure space and $\omega\in \Omega$. What is $$ \frac{\partial I}{\partial f(\omega)}? $$ i.e. I ...
3
votes
0answers
125 views

Binary optimization

Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows: There are ...
2
votes
1answer
52 views

Smooth Reformulation of NonSmooth Constraints

If I have something like : \begin{align} \min_x \max_i f_i(x) \end{align} I can reformulate this nonsmooth formulation as: $$\min_x z$$ $$z\geq f_i(x)$$ and I have a smooth formulation of the problem. ...
6
votes
1answer
1k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
4
votes
1answer
299 views

principal “pseudo eigenvector” of a real symmetric positive-semidefinite matrix

Let $A$ be a real symmetric positive-semidefinite matrix and suppose that $c>0$ is a sufficiently small number. I wonder if it is possible to solve the non-convex optimization $$\arg\max_u\ ...
2
votes
1answer
251 views

Maximizing the number of non-crossing lines between a number of points

Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross. Hoping for a polynomial time algorithm, I ...