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
223 views

Functional minimization

Let $F(u) = -\int_0^1u\,dx$ and $H(u)= \int_0^1 \sqrt{1+(u')^2}\,dx-A$ for some $A \gt 1$. If we have to minimize $F(u)$ in $C^1$ such that on the interval $[0,1]\:, u(0)=u(1)=0$, subject to $H(u)=0$. ...
1
vote
1answer
53 views

Finding optimal recipe proportions

Is there a mathematical optimisation technique or algorithm that could, at least in principle, be applied to find optimal ingredient proportions for a given recipe using a minimal number of ...
2
votes
0answers
157 views

Optimization problem about large matrices

I'd like to solve the following optimization problem: Find non-negative scalar $a$, $b$, $c$ to minimize $\| (D-(aA+bB+cC+D^{-1})^{-1})y\|^2+2\operatorname{trace}((aA+bB+cC+D^{-1})^{-1})$ where ...
3
votes
1answer
140 views

Verification for maximum principle

Given optimal control problem $$ \dot x = f(t,x(t),u(t)), \quad x(0) = x_0,\\ J(u) = \int_0^T f^0(t,x(t),u(t))dt \to \min, $$ we can apply Pontryagin's maximum principle to get a necessary condition ...
-1
votes
1answer
128 views

Inverse transform sampling

I know the basic idea is to generate a random number from $U(0,1)$, find the inverse cumulative distribution function $F^{-1}$ and then take $x = F^{-1}(U)$. If you were plot a histogram of say 1000 ...
4
votes
1answer
122 views

References on constrained least square problems?

I have met some constrained least square problems, for example, my last post. I found that there are various methods for slightly different constraints, and still I often had little clue about how to ...
1
vote
0answers
51 views

Optimimal rotation using non-linear conjugate gradient

The problem I'd like to ask is the following : let $M_1$ and $M_2$ two rigid bodies with a quadratic constraint function $f$ attached to its grid points. $M_2$ is always kept static while $M_1$ can be ...
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 ...
1
vote
1answer
82 views

How to sample point from triangle where vertex is not in origin

This link http://mathworld.wolfram.com/TrianglePointPicking.html gives an overview of how to sample points from either a quadrilateral or triangle given one vertex is at the origin. The standard ...
2
votes
1answer
237 views

Simple resource for Lagrangian constrained optimization?

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
2
votes
2answers
146 views

optimality of quadratic programming problems

Suppose we have a general quadratic programming problem: \begin{align} \min_{x}\,\,&c^Tx+\frac{1}{2}x^TQx,\\ \mbox{s.t.}\,\,& Ax=b,\\ &x\geq0, \end{align} where $Q$ is positive ...
2
votes
5answers
327 views

How to minimize $\| y- Ax\|$ subject to $\|x\|=1$ and $x \geq 0$?

Given $y \in \mathbb R^n$ and $A \in \mathbb R^{n \times n}$, whis is some way for $$\min_x \| y- Ax\|$$ subject to $\|x\|=1$, and $x \geq 0$ (which means every components of $x$ is nonnegative)? ...
1
vote
0answers
68 views

Is this dynamic optimization?

I would like to know what I should know to understand this IMF paper. What kind of optimization is used to maximize the utility function on page 9 (number 1) subject to constraints (2) and (3)? The ...
3
votes
2answers
492 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
270 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
209 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
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 ...
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 ...
1
vote
1answer
52 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
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)Α := ...
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}$ ?
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 ...
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 ...
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 ...
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 ...
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
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
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 ...
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 ...
0
votes
2answers
141 views

Convexity of $\log \det(I+(P-\text{tr}(X))\cdot X)$

where $P-\text{tr}(X)>0$ and $X$ is a diagonal matrix with diagonal elements are $(x_1,x_2,\dots x_m)$
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
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 ...
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
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
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. ...
0
votes
1answer
349 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
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 ...
8
votes
1answer
403 views

Graph theory problem (edge-disjoint matchings)

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even ...
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 ...
3
votes
0answers
269 views

Optimizing non linear programs of two variables

The scenario is; We've got $n$ stationary 360$^{\circ}$ sensors in an confined area (each sensor is located at some arbitrary $\left(x,y\right) = \left(x_{n},y_{n}\right)$), once a unit $t$ enters ...
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 ...
2
votes
1answer
64 views

Optimal distribution of weighted votes

I'm working on a project for my university in wich the students can choose their preferred seminars for the next semester. My goal is it to allocate these weighted votes in an optimal way to the ...