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)

2
votes
1answer
705 views

Optimizing integral functionals using Matlab

I am looking for some bibliography regarding solving integral optimization problems numerically (preferably using Matlab). I want to solve problems of the type $$ \min_{r \in A} \int_a^b ...
3
votes
3answers
179 views

Finding the minimum of $\frac pq + \frac rs$ for distinct integers $p, q, r, s$ from $\{1,2,3,4,5,\ldots,16,17\}$

Here is the question: Four distinct integers $p$, $q$, $r$ and $s$ are chosen from the set $\{1, 2, 3, 4, 5, \ldots, 16, 17\}$. The minimum possible value of $\frac pq + \frac rs$ can be written ...
0
votes
1answer
227 views

Maximizing the Determinant Function

Let $M_{n}$ denote the set of $n\times n$ real matrices. Let $c>0$ be a real number and denote by $X_1,X_2,...,X_n$ the lines of the matrix $X\in M_n$. Let $\|X_i\|$ denote the euclidian norm of ...
1
vote
1answer
228 views

Using Lagrange multipliers for restricted extrema

Consider the function $f(x,y) = x^2 + xy + y^2$ defined on the unit disc $D = \{(x,y) \mid x^2 + y^2 \leq 1\}$. I can not simplify the equations to the point where I find a constant for the lagrange ...
1
vote
0answers
44 views

Optimizing a matrix

input: $b_1,b_2,...,b_n$ positive integers. $a_1<a_2<...a_n$ positive integers output: positive integer I'm given $b_1$ columns of the form ...
0
votes
2answers
100 views

Minimizing The Cost

I have this exercise that I would like anyone to suggest the required steps in order to solve it A cylindrical can is to be made to hold $250 \pi\; cm^3$. Find the dimensions of the can that will ...
1
vote
1answer
39 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 ...
0
votes
1answer
66 views

Optimize the matrix of “mis-ties” by adding|subtracting a number to|from a whole row|column

Preface: There is a net of $N$ almost-straight paths on an aerial map. Some of them intersect with another. At the points of intersection there are possibly a "mis-tie", which is expressed as a ...
4
votes
2answers
684 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 ...
3
votes
2answers
157 views

Men on a boat problem

There is the usual question of some men on a boat- various men have various speeds, the boat has a capacity of 2 men, and the boat takes on the speed of the slowest man in the boat at any given time. ...
2
votes
1answer
531 views

Shortest distance between clothoid spline and point

Is there any way to analytically decide the shortest distance between a spline of clothoids and a point? Both lies in XY-plane. The clothoid spline has G2 continuity. The result should be used in ...
2
votes
1answer
181 views

How to find simple rational numbers close to the decimal representation

It is a simple practical question. I am reverse-engineering poorly documented calculations made by someone else. I frequently find a mysterious number 0.0329. I'm quite certain it is some kind of ...
2
votes
1answer
891 views

Show this function is convex.

Could someone point me in the right direction for proving the following? Given that $f:\mathbb{R}^n\rightarrow \mathbb{R}^m$ is an affine map given by $f(x)=A\mathbf{x}+\mathbf{b}$, ...
3
votes
0answers
88 views

Golden Section Search With Noisy Measurements

I'm using a modified golden section search (brents) to find the maximum / minimum of a function. The function is a real time measurement from a laser that is measuring the height of a single peak on a ...
2
votes
0answers
113 views

Lattice Reduction Problem: Minimizing the “Longest” Basis Vector

Suppose we have a basis for an integer lattice formed by the vectors $\vec v_1, \vec v_2, \ldots,\vec v_n$. Then let $A$ be the augmented matrix $( \vec v_1| \space \vec v_2| \cdots |\space \vec ...
1
vote
2answers
283 views

Did I minimize the cost correctly?

I have a word problem that reads as so A farmer wants to fence a rectangular part of his land (30,000 square feet). The fenced area is to have one border shared with a neighbor which he wishes to be ...
4
votes
2answers
395 views

Analog of Simplex Method for Quadratic Programming

It happened so I need to work with an algorithm for solving QP problems. The main issue here is that I can't find any references to this algorithms (at least no references in sources in english). ...
0
votes
0answers
210 views

closed form of a linear program

I have a linear program: $\min. L(b_{ij})=\sum_i\sum_j w_{ij} b_{ij}$ subject to $\ 2 \leq \sum_j b_{ij} \leq 3 \ \ \ \forall i$ $ \sum_i b_{ij} = 1 \ \ \ \forall j$ $0\leq b_{ij}\leq1$ ...
1
vote
0answers
146 views

A simple problem in two dimensional optimization

I have the following problem: given $$f_1=\frac{-12d_1}{\pi d_2-12}$$ and: $$f_2=\frac{\pi d_1d_2}{\pi(d_1+d_2)-12}$$ I need to find the maximum of the following function: $$F(d_1,d_2)=|f_1|+|f_2|$$ ...
3
votes
0answers
74 views

Optimizations for Travelling Salesman Problem

I have to design a branch-and bound algorithm that solves the optimal tour of a graph on the cartesian plane every time. I have been given the hint that identifying hopeless branches earlier in the ...
1
vote
1answer
58 views

Check the convexity of a function

How can we check the convexity of a set ? $S = \{(x,y) \in \mathbb{R}: x-y²\le y \le x+y²\}$
2
votes
3answers
120 views

Dual of a Linear Program

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ ...
1
vote
1answer
139 views

Linear programming - task formulation

I have a question concerning the formulation of a linear programmign task. I am trying fo find $x^* \in argmax_{x \in R^n}\{ a_1x_1 + a_2x_2, a_2x_2 + a_3x_3 + a_4x_a, a_4x_4 + a_5x_5 \}$, subject to ...
4
votes
2answers
1k views

What are the advantages of dual of a problem

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
2
votes
1answer
69 views

Maximalization of a cubic puzzle

What is the maximal volume of a post package of length $L$, width $W$ and height $H$, subject to the following restrictions: $L+W+H \leq 90 $ $L \leq 60$, $W \leq 60$, $H \leq 60$ Intuitively I ...
11
votes
3answers
417 views

Combinatorial optimization - improve performance

I am writing a program to solve a combinatorial optimization problem. I have been working on an algorithm that gets the desired results, but I am having difficulties getting the algorithm to perform ...
-1
votes
1answer
425 views

Area optimization problem

An iron wire $3$ meters long is cut in two. We form a square with the first piece and an equilateral triangle with the second. How must it be cut for the total area of these two figures to be maximized? ...
3
votes
1answer
115 views

Proof that $E_n = \int_0^1 \left| \ln t - P_n(t) \right|\mathrm{d}t = 1/(n+1)^2$

Assume one wants to minimize the distance between $f(x)=\ln x$ and $P_n(t)$ where $P_n$ denotes a polynomial of degree $n$. Etc $P_1 = ax 0+ b$. One way to judge whether the polynomial is a good ...
2
votes
2answers
82 views

A Quadratic Problem (which looks very simple)

This arises as a part of my work. \begin{align} \min_{x^{H}x=1}~&x^{H}A_1x \\ subject~to~&x^{H}A_2x=0 \end{align} $A_1$ and $A_2$ are $N\times N$ hermitian matrices and $x$ is a unit norm ...
3
votes
4answers
481 views

Finding minimal cost edge cover for a bipartie graph

I have got two sets of elements and a pruned graph of bipartie edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
0
votes
3answers
99 views

Show that exactly one of the equations has a solution.

Show that exactly one of: \begin{cases} B^Tv = 0\\ d^Tv = 1 \end{cases} or $$Bu=d$$ has a solution. I tried with Farkas lemma, but I run into trouble.
0
votes
0answers
48 views

Vector operation resulting in all products of consecutive subsequences

I am wondering if the following vector operation is known/studied, or alternatively if it can be simplified somehow into matrix multiplications: $A_{ij}=\prod_{k=i}^{k=j}{x_k}$ $x$ is a vector and ...
2
votes
1answer
80 views

about convexification

Let $f: \mathbb{R}^{n} \rightarrow \overline {\mathbb{R}}$. Called conjugate in the sense of Young-Fenchel of $f$, the following function: $$f^{*}(x^{*})=Sup\lbrace \langle x,x^{*}\rangle -f(x) : x ...
3
votes
1answer
474 views

Simple explanation of Comb inequalities in TSP

A comb can be defined by a handle $H$ and a number of teeths $T_1,T_2,\dots,T_t$ such that: $H,T_1,T_2,\dots,T_t \subseteq V$ $T_j \setminus H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$ $T_j ...
0
votes
1answer
51 views

Feasibility of a given set of Quadratic Forms

This arises as a part of my work. Given a positive number $t$, two hermitian matrices $P_1$ and $P_2$, I am interested in knowing if a unit norm vector $z$ exists such that \begin{align} ...
2
votes
1answer
65 views

Minimization under condition

I have to minimize $x^Tx$ under condition $a^Tx = 1$. Whats the geometric meanign of this task? I think that the meaning is to find minimal vector $x$ thats is perpendicular to given vector $a$, but ...
1
vote
1answer
179 views

How to simplify geodetic distance formula?

Question is also related to programming, but maybe I can solve it here. I am using distance calculation using Haversine method(probably it's not important, but I will post the function): ...
1
vote
1answer
91 views

Car travelling with lowest fuel

Suppose a car's fuel tank can carry at most 500 unit fuel, but it need to travel from A to B where the distance between them is 1000 km. Suppose that the fuel consumption rate is 1 unit/km, and ...
2
votes
0answers
146 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
2
votes
3answers
4k views

Optimization of the Area of a rectangle with regards to an Ellipse

The actual problem reads: Find the area of the largest rectangle that can be inscribed in the ellipse $$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$$ I got as far as coming up with the equation for the ...
0
votes
2answers
272 views

Convex function from Hessian

Am I correct to say that the following function is convex? $$\begin{align} & f(x,y)=-\sqrt{xy} \\ & x>0,y>0 \\ \end{align}$$ After computing the Hessian: $$ Hf =\left[ \begin ...
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 ...
0
votes
0answers
219 views

Commutativity of inf and sup

Under which conditions on the potential $\Pi(u,p)$ does the following hold? $$ \inf_{u} \sup_{p} \Pi(u,p) = \sup_{p}\inf_{u} \Pi(u,p)$$ It is obvious that both expressions have the same stationary ...
0
votes
1answer
115 views

What does RMSD mean?

Normally a rigid superposition which minimizes the RMSD is performed, and this minimum is returned. Given two sets of points and , the RMSD is defined as follows: $$\begin{align*} ...
0
votes
2answers
119 views

Minimum distance problem

Find the coordinates of the point in the graph of $f(x)=2x^2+3$ that is closer to the point $(5,-1)$ To start off, I found the first order derivative of the function so I could get the slope of ...
2
votes
3answers
292 views

Epigraph of a function.

I hope you can give me some suggestions on convex functions. the function $f:(0,\infty)\rightarrow \mathbb{R}$ given by $f(x)=\dfrac{1}{x}$ is convex and continuous, but its epigraph is closed in ...
2
votes
0answers
45 views

Graph of a set homeomorphic

I would like to please guide me on this question: Let $S_+$ denote the set of semi positive definite matrices in $\mathbb{R}^{2\times 2}$ is known that $S_+\subseteq Sym \simeq\mathbb{R}^{3}$,wherein ...
1
vote
0answers
47 views

General properties of an optimal solution of a convex program

How do we seek certain properties for a solution of a convex minimization problem. For example we want to make sure if the below objective has a symmetric optimal solution: \begin{equation} \min_X ...
0
votes
2answers
50 views

Maximising an expression

We are to maximise $x^{2}y-y^{2}x$, where $x,y \in [0,1]$. I've tried using AM-GM to find another (easier to maximise) expression, which gave me $xy(x-y) \le \frac{1}{2}(x^{2}+y^{2}) (x-y)$ but that ...
2
votes
0answers
77 views

Spectral/ Eigen-Value solution with a linear constraint?

Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...