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)

9
votes
1answer
418 views

Largest rectangle in a convex polygon

What is the least $k > 0$ such that every convex polygon of area $k$ contains a rectangle of area 1? I can prove that $k \le 8$, but surely this can be improved. Let $\mathcal{C}$ be a convex ...
1
vote
1answer
62 views

An optimization problem

I need to prove the following result: Given a real sequence $a=(a_n)_{n\in\mathbb{Z}}$ and a number $A>0$ then $||a||_{1}\leq A$ if and only if there exists $b_n$ such that $-b_n\leq a_n\leq ...
4
votes
3answers
53 views

$\max_{\|x\|=1}f(x)=\max_{\|x\|\le 1} f(x)$

I'm reading the book "Matrix Analysis and Applied Linear Algebra". On page 450, eq(5.15.5), I think I found an error made by the author. So I post it here. If I'm wrong, please correct me. The ...
3
votes
2answers
62 views

What kind of optimization is this problem?

I'm not asking for a solution, I just need to know what type of optimization is this problem?. Find $\mathbf{q}$ that minimizes the following: $$\min_\mathbf{q}{|\mathbf{BXq|^2}}$$ $$\, \mbox{s.t}\ ...
4
votes
1answer
320 views

Maximizing distance between points

I asked a similar question on SciComp, but it is a little out of the domain, so I thought I'd give it a try here as well. Give n points, I would like to place them in a periodic box (periodic such ...
0
votes
0answers
95 views

Optmizing sum of two vectors

I apologize in advance for the title, but I don't know how to express exactly what I want to do. So, here's my problem: I have 66 vectors, each one with 8 values, those values can be positive or ...
0
votes
1answer
342 views

Minimizing a function using gradient (example from Wikipedia)

This example is from Wikipedia (http://en.wikipedia.org/wiki/Gradient): The gradient of function $f(x,y,z)=2x+3y^2-sin(z)$ is $\nabla f= \frac{\partial f}{\partial x} i + \frac{\partial f}{\partial ...
1
vote
1answer
71 views

Tricky algebra for minimization

Find the local minimum for $f(x, y) = 2x^4 + y^2 - 4xy + 5y,\:x,y \in \mathbb{R}$ find the local minimum. Okay this seems easy enough, the necessary condition dictates that candidates are of the form ...
0
votes
1answer
270 views

Lipschitz constant for optimization of multivariate function

I intend to implement an optimization algorithm which requires the computation of the Lipschitz constant. My function is a multivariate function with more than 50 variables. I am wondering whether ...
1
vote
1answer
366 views

Show that the infimum is convex

Let f be bounded convex function on a convex subset $A\times B \in \mathbb{R^m}\times\mathbb{R^n}$. Define $g(x)=\inf{f(x,y):y\in B}$ Show that g is convex on $A$. Okay, let $x = (x_1,x_2), ...
0
votes
1answer
281 views

If $f$ is strictly convex in a convex set, show it has no more than 1 minimum

Suppouse $A \in \mathbb{R^n}$ is convex. If $f:A\to\mathbb{R^n}$ is strictly convex, show that the set of minimizers if either a singleton or empty. Ok, Suppose there exist more than one minimizer, ...
2
votes
0answers
41 views

maximal m-elements of the matrix inversion

Suppose the $n\times n$ matrix $A$ is invertible, and all its elements are between 0 and 1. The existing matrix inversion operation of $A^{-1}$ will take $O(n^3)$ time. Now I just want to find the ...
1
vote
1answer
361 views

How would you solve a Tikhonov Regularized Least Squares problem with nonnegative constraints?

For a Tikhonov Regularized Least Squares problem with nonnegative constraints, what are some methods that solve it? Are methods solving a Least Squares problem with nonnegative constraints and the ...
2
votes
2answers
149 views

Are there constraint problem calculators?

So I just remembered Lincoln Logs exist, so I found ten giant sets of them on ebay for Buy It Now, and I'm trying to decide what combination of purchases gives me the most logs for the least money if ...
1
vote
2answers
126 views

Is $y=x+\frac{1}{x}$ a hyperbola?

How do we confirm or disprove that? And is there a name for this kind of function? $$f(x)=c(x-a)+\frac{d}{x-a}+b$$ If we restrict that $x-a>0$ and $c,d>0$, an observation is that the minimum ...
6
votes
1answer
968 views

Why are additional constraint and penalty term equivalent in ridge regression?

Tikhonov regularization (or ridge regression) adds a constraint that $\|\beta\|^2$, the $L^2$-norm of the parameter vector, is not greater than a given value (say $c$). Equivalently, it may solve ...
1
vote
2answers
252 views

Max and min value of $7x+8y$ in a given half-plane limited by straight lines?

So, there are four inequalities: $$\begin{eqnarray*} y &\geq &-3x+15; \\ y &\leq &-11/3x+56/3; \\ x &\geq &0; \\ y &\geq &0. \end{eqnarray*}$$ If we draw all those ...
5
votes
0answers
74 views

$\int_{-\infty}^{+\infty}\left|f(g(t))-f(h(g(t)))\right| \,dt=0$ How to find $f$?

Let $h,g$ be given entire functions. Consider $$\int_{-\infty}^{+\infty}|f(g(t))-f(h(g(t)))|\, dt=0,$$ where $|\cdot|$ means modulus. How do I find non-polynomial analytic solutions for $f\,$? ...
3
votes
5answers
58 views

Why is my procedure misleading?

Max: $ z = 10( x_1 + x_2)$ subject to constraints: $$ 2x_1 + 5x_2 \leq 16 $$ $$ 6x_1 + 5x_2 \leq 30 $$ $$ x_1, x_2 \in \mathbb{Z^+} $$ I have the Integer Programming ...
2
votes
0answers
91 views

Is there a generalization of eigenvalues/eigenvectors to $L^p$ for $p\neq2$?

Given symmetric positive definite $m\times m$ matrix $\Sigma$, $1 \le p,$ and constant $c > 0$, consider the solution to the optimization problem: $$ \min_{v : \left\|v\right\|_p \ge c} ...
0
votes
2answers
31 views

Change $\inf$ order

Is it true that if $f: X \rightarrow \mathbb{R}$ and $g : X \times Y \rightarrow \mathbb{R}$ then $$ \inf_{x \in X} \left( f(x) - \inf_{y \in Y} g(x,y) \right) = \inf_{x \in X} \sup_{y \in Y} \left( ...
1
vote
1answer
51 views

Maximizing a variable sum

I am analysing the worst case scenenario for an algorithm. It reduces to show that the following function is maximun when $a_1 =c , a_i=0, i\geq 2$ $$ \max \sum_{i=1}^n (n+1-i)\times a_i $$ subject ...
0
votes
0answers
31 views

Please help with the LP formulation

I would like to formulate the following constraints as a Linear constraint $|x_1-y_1| + |x_2-y_2| + |x_3-y_3| > |\sum_{i=1}^nx_i- \sum_{i=1}^ny_i|$ $ \bf{x,y} \in \bf{R}^n $ Basically I am ...
0
votes
3answers
78 views

Optimization problem with range of variables

I have a simple optimization problem. The objective function consists of $4$ variables, say $a,b,c$ and $d$. So the objective function $y=f(a,b,c,d)$ is a linear function of $a,b,c,d$. The ...
1
vote
3answers
747 views

Proof that maximizing a function is equivalent to minimizing its negative

The statement that maximizing a function over its argument is equivalent to minimizing that function over the same argument with a sign change seems to be accepted as trivial wherever I look (MSE, ...
0
votes
1answer
216 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
52 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
156 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
134 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
126 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
120 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
49 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
80 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
224 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
137 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
319 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
387 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
69 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
212 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 ...
0
votes
1answer
181 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
67 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
312 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
213 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
241 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
35 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
1k 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 ...